Chapter Review 409- Let R be the relation on {1, 2, 3, 4, 5} with elements {(1, 1), (2, 1), (3, 2), (2, 3), (1, 4),
(3, 5), (5, 2)}. Represent the symmetric closure of R as a digraph. - Let R be the relation on {1, 2, 3, 4} with elements {(1, 1), (2, 1), (3, 2), (2, 3), (1, 4)).
Represent the transitive closure R* of R as a digraph.
Chapter Review
Definitions and notation are the first hurdles in studying graph theory. Vertices, edges, inci-
dence, adjacency, and degrees are the core terms. Using these terms, one learns to identify
parts of a graph, such as a subgraph, a spanning subgraph, an induced subgraph, a trail,
a path, a circuit, and a cycle. The idea of a graph isomorphism is needed to distinguish
between graphs that are truly different and graphs that are simply labeled differently. The
standard representations of graphs by adjacency matrices and adjacency lists finish the in-
troduction to the basic vocabulary. The next major topic involves determining whether a
graph is connected and, if not, what its connected components are. Two fundamental search
procedures, depth first search and breadth first search, are explained. The complexity of the
algorithms for carrying out these search procedures as well as the determination that the
algorithms are correct concludes this discussion. The search procedures are also used in an
algorithm to identify the connected components of a graph. These algorithms are proven
to be correct, and their complexity is determined. The chapter then examines two special
kinds of graphs: trees, and directed graphs. Various definitions of trees are proven to be
equivalent. Minimal connected spanning subgraphs are introduced. Kruskal's algorithm
for finding an MCST is presented, with correctness and complexity issues being explained.
A second class of trees, called rooted trees, is then introduced and used in searching pro-
cedures. Finally, with directed graphs, the vocabulary is introduced, as are two further
algorithms. The first detects a directed cycle, and the second carries out a topological sort.
The directed form of Euler's Theorem is presented, as is the notion of a strongly connected
directed graph.
Applications include developing a process to determine if a graph has a Hamiltonian
cycle. Euler's Theorem is used to determine an effective way to draw a graph. Decision
trees are used to find a lower bound for the complexity of any sorting algorithm based on
comparing pairs of elements. Directed graphs are used to characterize deadlock in an op-
erating system that uses a single resource allocation scheme. The notion of being strongly
connected is used to describe effective grids of one-way street patterns.6.21.1 Terms, Theorems, and Algorithms
6.1-6.5 SummaryTERMS
acyclic bipartite graph complete bipartite graph
adjacency list bipartition complete graph
adjacency matrix circuit cubic graph
adjacent clique cycle
binary representation complement degree