graphs graph is way of representing relationships that exist between pairs of objects that isa graph is set of objectscalled verticestogether with collection of pairwise connections between themcalled edges graphs have applications in modeling many domainsincluding mappingtransportationcomputer networksand electrical engineering by the waythis notion of "graphshould not be confused with bar charts and function plotsas these kinds of "graphsare unrelated to the topic of this viewed abstractlya graph is simply set of vertices and collection of pairs of vertices from called edges thusa graph is way of representing connections or relationships between pairs of objects from some set incidentallysome books use different terminology for graphs and refer to what we call vertices as nodes and what we call edges as arcs we use the terms "verticesand "edges edges in graph are either directed or undirected an edge (uvis said to be directed from to if the pair (uvis orderedwith preceding an edge (uvis said to be undirected if the pair (uvis not ordered undirected edges are sometimes denoted with set notationas {uv}but for simplicity we use the pair notation (uv)noting that in the undirected case (uvis the same as (vugraphs are typically visualized by drawing the vertices as ovals or rectangles and the edges as segments or curves connecting pairs of ovals and rectangles the following are some examples of directed and undirected graphs example we can visualize collaborations among the researchers of certain discipline by constructing graph whose vertices are associated with the researchers themselvesand whose edges connect pairs of vertices associated with researchers who have coauthored paper or book (see figure such edges are undirected because coauthorship is symmetric relationthat isif has coauthored something with bthen necessarily has coauthored something with snoeyink garg goldwasser goodrich tamassia tollis vitter preparata chiang figure graph of coauthorship among some authors