This is an old revision of the document!
Table of Contents
Chapter 3
This chapter introduces basic graph definitions and algorithms.
Section 1: Basic Definitions and Applications
A graph consists of a collection of nodes (V) and edges (E). Directed graphs have “one-way” edges to indicate asymmetric relationships while undirected graphs have “two-way” edges to indicate symmetric relationships. Some examples of graphs include transportation, communication, information and social networks.
A path in a graph is a sequence of nodes where each consecutive pair is connected by an edge. A path is simple if all the vertices are distinct. A path is a cycle if the first and last node are the same. We say a graph is connected if there is a path from one node to every other. The distance from one node to another is the length of the shortest path between them, measured in number of edges.
A graph is a tree if it is connected and does not contain a cycle. Trees represent hierarchies.
Theorem: Any two of the following imply the third (i) G is connected, (ii) G does not contain a cycle, (iii) G has n-1 edges
Readability: 8
Section 2: Graph Connectivity and Traversal
In this section, we want to determine if there is a path from node s to node t. One way to do this is using Breadth First Search (BFS). In BFS we find all the nodes connected to a given layer before moving on. If we start at s, we know there is a path to t if t is in some layer j and that in this case, the distance from s to t is j. We also know BFS produces a BFS tree, rooted at s and that if two nodes are connected by an edge, they will be at most one layer apart in the tree. The set R produced by BFS is the connected component of G containing s.
Another way to determine if there is a path is using Depth First Search (DFS). DFS follows a path until it reaches a dead-end and then backtracks. DFS visits the same nodes as BFS, but in a different order. It produces a DFS tree rooted at s that tends to be narrow. If two nodes are connected in our graph, then one is ancestor of the other in the DFS tree.
Both BFS and DFS produce the connected component containing s. It is useful to recognize that for two nodes, their connected components are either identical or disjoint.
Readability: 8
