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}
image source
- For example, take a look at the following graph:
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
- 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:
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?
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:
- 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?
- 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.
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: - connected or disconnected
- cyclic or acyclic
- directed or undirected
Graph A: 
Image source.
Graph B: 
Image source.
Graph C:
Graph D:
Image source.
Applications of Graph TheoryWriting 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.
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:
 Image source.Wrap Up - With your partner, answer the questions from today's learning objectives.
~See You Next Class!~
|
