Introduction to Graphs

Table of Contents

1 Reading

Read Bailey sections 16.1 and 16.2.

2 Video

Here is a video lecture for today's lesson.

The video contains sections on

  1. Defining a graph (0:18)
  2. Examples of graphs (2:02)
  3. Is a graph an ADT? (3:08)
  4. Undirected graph (4:20)
  5. Directed graph (8:23)
  6. Other notation (11:21)
  7. Graph examples (17:43)
  8. Trees as graphs (28:24)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=71129df5-d1d0-41ac-a480-acd701859877

3 Defining a Graph

  • A graph is a formalism for representing relationships among items
  • Very general definition because very general concept
  • A graph is a pair: \(G = (V,E)\)
    • A set of vertices, also known as nodes: \(V = \{v_1 ,v_2 , \dots, v_n\}\)
    • A set of edges \(E = \{e_1 , e_2 , \dots, e_m\}\)
    • Each edge \(e_i\) is a pair of vertices \((v_j ,v_k)\)
      • An edge connects the vertices

3.1 Examples

For each, what are the vertices and what are the edges?

  • Web pages with links
    • pages are vertices, embedded links the edges
  • Methods in a program that call each other
    • methods are vertices, calls are edges
  • Road maps (e.g., Google maps)
    • locations are vertices, streets/highways are edges
  • Airline routes
    • locations are vertices, flights are edges
  • Family trees
    • people are vertices, relationships are edges
  • Course pre-requisites
    • courses are vertices, pre-reqs are edges

graph-transport.png

graph-social.png

graph-protein.png

3.2 Is Graph and ADT?

  • Can think of graphs as an ADT with operations like isEdge(v1, v2) to check if there's an edge between two vertexes
  • But it is unclear what the standard operations are
  • Instead we tend to develop algorithms over graphs and then use data structures that are efficient for those algorithms
  • Many important problems can be solved by:
    • Formulating them in terms of graphs
    • Applying a standard graph algorithm
  • To make the formulation easy and standard, we have a lot of standard terminology about graphs

4 Terminology

4.1 Undirected Graphs

  • In undirected graphs, edges have no specific direction
    • Edges are always two-way
  • Only one of these edges needs to be in the set \(E\) (the other is implicit)
  • Degree of a vertex: number of edges containing that vertex
    • Put another way: the number of adjacent vertices
  • A path is a sequence of vertices connected by edges, with no repeated edges
    • Two vertices are connected if there is a path between them
    • A graph is connected when there is a path between every two vertices
  • A cycle is a path (with at least 1 edge) who first and last vertices are the same
    • i.e., a loop
    • A graph can by cyclic (is has cycles) or acyclic (it doesn't have cycles)

graph-terms.png

4.2 Directed Graphs

  • In directed graphs (sometimes called digraphs), edges have a direction
  • Thus, just because the edge \((u,v)\) is in the graph doesn't mean that \((v,u)\) is in the graph.
  • Call \(u\) the source and \(v\) the destination
  • In-degree of a vertex: number of in-bound edges (i.e., edges where the vertex is the destination)
  • Out-degree of a vertex: number of out-bound edges (i.e., edges where the vertex is the source)
  • Directed graphs can have paths and cycles as well
    • Vertex \(w\) is reachable from vertex \(v\) if there is a directed path from \(v\) to \(w\)

digraph-terms.png

4.3 Other Notation

  • A node can have a degree / in-degree / out-degree of zero
  • A graph does not have to be connected
    • Even if every node has non-zero degree
  • For a graph \(G = (V,E)\):
    • \(|V|\) is the number of vertices
    • \(|E|\) is the number of edges
    • Minimum edges? \(0\)
    • Maximum for undirected? \(\frac{|V||V+1|}{2}\), which is \(O(|V|^2)\)
    • Maximum for directed? \(|V|^2 - |V|\), which is \(O(|V|^2)\)
      • (unless vertices can have self-edges, in which case it is \(|V|^2\))
  • If \((u,v)\) is in \(E\)
    • Then \(v\) is a neighbor of \(u\), i.e., \(v\) is adjacent to \(u\)
    • Order matters for directed edges
    • \(u\) is not adjacent to \(v\) unless \((v,u)\) is in \(E\)

5 Weighted Graphs

  • In a weighted graph, each edge has a weight a.k.a. cost
  • Typically numeric (most examples use ints)
  • Separate from whether graph is directed
  • Some graphs allow negative weights; many do not

graph-weighted.png

6 Examples Again

Which would use directed edges?

  • Web pages with links
  • Methods in a program that call each other
  • Road maps (e.g., Google maps)
    • one-way streets
  • Airline routes
    • possible but unlikely, at least in passenger travel (airlines generally want their planes to fly back from wherever they go)
  • Course pre-requisites

Which would have self-edges?

  • Web pages with links
    • link to another part of the same page
  • Methods in a program that call each other
    • recursion!

Which would be connected?

  • Road maps (e.g., Google maps)
  • Family trees

Which could have 0-degree nodes?

  • Web pages with links
  • Facebook friends
  • Methods in a program that call each other
  • Road maps (e.g., Google maps)
  • Airline routes
  • Course pre-requisites

Which would have weighted edges?

  • Road maps (e.g., Google maps)
    • distance, travel time
  • Airline routes
    • distance, travel time, airfare

7 Are Trees Graphs?

  • When talking about graphs, we say a tree is a graph that is:
    • Undirected
    • Acyclic
    • Connected
  • So all trees are graphs, but not all graphs are trees

  • An example:

    graph-tree.png

  • How does this relate to the trees we know and love?
  • We are more accustomed to rooted trees where:
    • We identify a unique root
    • We think of edges as directed: parent to children
    • Every rooted tree is a directed acyclic graph (DAG)
  • Given a tree, picking a root gives a unique rooted tree
    • The tree is just drawn differently and with directed edges

graph-tree-root1.png

graph-tree-root2.png

8 Practice Problems1

  1. What is the difference between an undirected graph and a directed graph?
  2. What is the difference between a graph and a tree?
  3. For each of the following, consider how you might represent it as a graph. What would be the vertices and what would be the edges?
    1. infectious disease
    2. a criminal conspiracy
    3. a city's water system
    4. people texting each other
    5. international diplomacy
    6. the floor plan of a house
  4. Which of these graphs is best modeled as a directed graph?
    1. Facebook: vertex = person; edge = friendship.
    2. Web: vertex = web page; edge = URL link.
    3. Internet: vertex = router; edge = fiber optic cable.
    4. Molecule: vertex = atom; edge = chemical bond.
  5. Review the new terms from this lesson: graph, edge, vertex, directed, undirected, degree, in-degree, out-degree, path, connected, cycle, cyclic, acyclic, adjacent vertex, weighted graph

9 Learning Block

Footnotes:

1

Solutions:

  1. A tree does not have cycles; a graph can. All trees are graphs, but not all graphs are trees.
  2. An directed graph has oriented edges—edges that establish a potentially one-way relation between vertices. The edges of an undirected graph establish a symmetric relationship.
    1. vertexes = people, edges = disease transmission
    2. vertexes = suspected conspirators or evidence, edges = possible connections (think red string board)
    3. vertexes = water sources or points of consumption, edges = pipes
    4. vertexes = cell phones, edges = texts
    5. vertexes = nations, edges = alliances
    6. vertexes = rooms, edges = doors, hallways, stairs
  4. The web would be best modeled as a directed graph because one web page linking to another doesn't mean the linked page links back