Learning Objectives
  • What is a Graph?
  • What are some real world applications of Graphs?
  • What are two ways to represent a Graph?
  • What is a vertex and what is an edge?
  • What is an origin and what is a terminus or destination?
  • Can a vertex be connected to itself by an edge?
  • What is the degree of a vertex?
  • What does it mean to be an adjacent vertex?
  • How is a directed Graph different from an undirected Graph?
  • What is a path?
  • What is a cycle?
  • What is a parallel edge?
  • What is a DAG?
  • What is Tree?
  • How would you represent the Graph ADT as a data structure?

Announcements

  • Midterm 2 next class
    • Trees, Binary Trees, BSTs
    • Hash Tables
    • Heaps
  • Return Quiz 6 today
  • Project Report 3 and Peer Evaluation 1 due
  • No more labs - work on your course project!
  • Women in Computer Science Club meeting tomorrow!
    • 1:00-2:00pm in ATC 202
    • San Jose Public Library representative
    • Teach basic coding skills to elementary and middle school students using curriculum from Google CS First
    • Also: pre-meeting at 12:30 about attending Women in Tech conference this weekend


Review Questions

With a partner, trace the below heap algorithms:

  • Trace each step of the buildMaxHeap operation (diagram and array) on the following:

                       

       A = [4, 9, 7, 18, 2, 3]


  • Trace heapInsert on the below Max Heap and the value 35. Show diagram and array at each step below:

                       

        A = [21, 11, 13, 2, 9]



  • Trace heapSort on the following heap. Show diagram and array at each step below:

                       

       A = [100, 90, 80, 70]


  • What is the Big-O run-time of heap sort?
  • Why is it more efficient to call build heap than it is to call heap insert one-by-one to insert n elements into a heap?


Introduction to Graphs

  • Today we are going to learn about the Graph ADT
  • These graphs are not the same as the graphs that you learned about in Algebra and Calculus.
  • Instead, there is a whole field of study known as Graph Theory which deals with the pairwise relationship between objects.
  • In other words, we will be looking at the connected pairs of objects to see how these objects relate to each other.


Applications of Graph Theory

  • Modeling transportation networks, such as highways and flight paths.
  • Representing relationships between components in electronic circuits
  • Computer networks: LAN, Internet, Web
  • Representing dependency of tables in databases
  • We will watch a video about one Graph application at the end of class.


Graph Definition

  • We can define a graph as a set (or collection) of vertices (the nexus points) and edges (the lines connecting the vertices together). G= {V,E}

http://mathinsight.org/media/image/image/small_undirected_network_labeled.png

image source


  • For example, take a look at the following graph:

Asymmetric 7-vertex graph satisfying P<sub>1</sub>

Image source.

  • Using set theory, we can define this Graph like so:
V(G) = { 1, 2, 3, 4, 5, 6, 7}
E(G) = {15, 17, 57, 45, 46, 67, 27, 26, 23, 34}
  • V(G) is called the vertex set. It is an un-ordered list of all the vertices in the Graph.
  • E(G) is called the edge set. It is an un-ordered list of all the edges in the Graph.
  • These two components are what define the graph.
  • There are two other ways to define graphs, not involving sets
    • We will learn about one of these at the end of class today.


Vertices

  • A vertex (plural vertices) or node is the fundamental unit of which graphs are formed.
  • At its most basic, a graph can be defined as a single vertex with no edges.
  • The below is considered a valid graph (no it's not an M&M), although no edges are present:
  • In addition, vertices also have a degree. The degree of a vertex is the number of edges that are coming from it (incident upon it).
  • The degree of the above vertex is 0.
  • What is the degree of vertex 6 above?


  • Below is an image of a graph which is labeled with the degrees of each vertex:

Image source.


Edges
  • An edge is defined by the vertices between it, as a pair (u, v).
  • u and v are both vertices in the graph, with the edge lying between them.
  • The vertex u is called the origin, the vertex that the edge is coming from.
  • The vertex v is called the destination or terminus, the vertex that the edge is coming to.
  • The above is an example of a directed edge
  • A directed edge is a pair of ordered vertices.
  • In other words, u is always the origin and v is always the destination.
  • When we draw a directed edge, we represent it with an arrow. The arrow is coming from the origin and pointing to the destination vertex.
  • Below is an example of an undirected edge.
  • Note that there is no arrow connecting the two.
  • An undirected edge is an unordered pair of vertices (u,v), where either u or v could be the origin.


Directed and Undirected Graphs
  • Graphs themselves can be directed or undirected.
  • Directed graph: all edges are directed.
  • The following is an example of a directed graph:

Image source.

  • Undirected graph: all edges are undirected.

Image source.


Adjacency

  • When an edge connects two vertices, the vertices are said to be adjacent to each other.
  • Any edge that connects two adjacent vertices is said to be incident on those vertices.
  • Two edges are said to be adjacent if they share a common vertex.

Review
With a partner answer the following questions:
  • In the undirected graph above, which vertices are adjacent?
  • Give two examples of adjacent edges.


Self Loops and Parallel Edges

  • A self loop occurs when a vertex is adjacent to itself.
  • For example, vertex 4 in the graph below contains a self loop:

images/lecture15/digraph.png

Image source.

  • Parallel edges occur when two vertices are adjacent to each other - twice. In other words, there is a loop from one vertex to another.
  • Parallel edges can be seen in the graph below between vertices 1 and 8 and also between vertices 6 and 8.
  • Can you also spot the self loops?

Connected and Disconnected Graphs

  • Look at the following image below. Does it meet our definition of a graph?

Cut Vertices without e

Image source

  • It turns out the answer is yes.
  • The above is called a disconnected graph.
  • A disconnected graph is one in which there is no simple path to all the vertices in the graph.
  • We can define a path as any route through a graph from vertex to vertex along edges, where no vertex along this route is repeated.
  • For example, there are two paths from vertex b to vertex a above: b-c-d-a and b-a.
  • However, there is no path from g to a or from h to d. Thus, our graph above is disconnected.
  • A connected graph is one in which there is a path to every vertex in the graph.
  • For example, the below graph is connected:

Cut Vertex
  • Notice that there is a path from every vertex to every vertex in the above graph.
  • A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
    • For example, the below graph is weakly connected:
    image source
  • If a graph is disconnected, it is considered to be composed of connected components.
  • For example, the below graph contains 2 connected components:

Cyclic and Acyclic Graphs

  • A cyclic graph is one which contains a cycle.
  • A cycle consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph.
  • Inside a cycle, there should be no repetition of vertices, except the first vertex, which is also the last vertex.
  • In the below graph, H-D-G-H is a cycle.
  • Can you see any others?


https://upload.wikimedia.org/wikipedia/commons/e/e7/Graph_cycle.gif

  • In a directed graph, a cycle must follow the edges from origin to destination vertex.
  • For example, the following graph contains the cycle B-C-E-D-B:

Image source.

  • However, the below graph is considered to be acyclic, meaning that it contains no cycles.

Image source.

Directed Acyclic Graphs (DAGs)

  • A directed acyclic graph, a.k.a. a DAG, is a special type of graph.
  • Among other applications, DAGs are useful in scheduling, when there are a collection of tasks that must be ordered into a sequence, but are subject to constraints that certain tasks must be performed earlier than others.
  • Given the images below, which one is a DAG and which one is not?


                              

Image source.



Trees Revisited

  • A tree is a graph that is both connected and acyclic.
  • Below is an example of a tree.

Tree graph.svg

Image source.

  • In graph theory, we usually consider all trees to be undirected. However, computer science, unlike applied math, allows for trees with directed edges, thus complicating our definition.
  • A directed tree is a directed graph which would be a tree if the directions on the edges were ignored.


Review Activity

With a partner, decide whether the following Graphs are:

  1. connected or disconnected
  2. cyclic or acyclic
  3. directed or undirected

Graph A:

depth-first search example, pic. 1

Image source.


Graph B:

https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Directed_acyclic_graph_2.svg/305px-Directed_acyclic_graph_2.svg.png

Image source.


Graph C:


Graph D:


The carbon tree of isooctane

Image source.


Applications of Graph Theory

Writing a Graph Data Structure

  • Let's start to think programmatically about how we will represent a Graph as a data structure.
  • As we know, a Graph is simply a set of vertices and edges.
  • The vertices can be written as a vertex set and the edges as an edge set.
  • We saw an example an example of a vertex and edge set at the beginning of class.

    Asymmetric 7-vertex graph satisfying P<sub>1</sub>

    
    Vertex and Edge Sets for Graph G:   

    V(G)
= { 1, 2, 3, 4, 5, 6, 7}

           E(G) = {15, 17, 57, 45, 46, 67, 27, 26, 23, 34}

Adjacency Lists

  • In addition to using sets, there is another way to represent a Graph using what are called adjacency lists.
  • An adjacency list representation of a graph is a collection of unordered lists, one for each vertex in the graph.
  • Each list contains the set of adjacent vertices to that vertex.
  • For example, I could represent the above Graph G using an adjacency list like so:

1: 5, 7

2: 3, 6, 7

3: 2, 4, 6

4: 3, 5, 6

5: 1, 4, 7

6: 2, 3, 4, 7

7: 1, 2, 5, 6


Group Activity

With a partner, write out the adjacency list for the following Graphs:

  • How is the adjacency list different when the Graph is directed vs undirected?

Graph G1:


Image source.


Graph G2:




Adjacency Lists and the Graph Data Structure
  • Using the adjacency list representation of a Graph makes it easy to represent a Graph in code.
  • We can use an array (or vector) of linked lists.
  • Each index of the array represents one vertex in our Graph.
  • The array at this location represents the adjacency list for that Graph.
  • We can see this representation as the depiction below:

images/lecture15/adjlistexample.png
Image source.


Wrap Up
  • With your partner, answer the questions from today's learning objectives.


~See You Next Class!~