Chapter Review
411
vertex label
weight
vertex label listing
weighted graph
THEOREM
Tree Characterization
ALGORITHMS
Minimum Cost Spanning Tree-Kruskal
Spanning Tree-Kruskal
Search Using a Binary Search Tree
6.14-6.19 Summary
TERMS
adjacent edges
embedding a partial order
score sequence
bipartite
head
single-unit resource
complement
incident
scheme stack
dag
indegree
STCONN
deadlock
induced subgraph
strongly connected
digraph
isomorphic directed
strongly connected comdirected circuit
graphs
ponent
directed cycle
linear order
tail
directed edge
orientable
topological sort
directed Eulerian circuit
orientation
tournament
directed graph
outdegree
transition
directed path
partial order
underlying graph
directed subgraph
ranking
WAITFOR graph
directed trail
schedule
weakly connected
THEOREM
STCONN is an equivalence relation
ALGORITHMS
Directed Cycle Detection
Topological Sort
6.21.2 Starting to Review
1. A trail may contain
(a) Repeated occurrences of vertices and edges
(b) Repeated occurrences of vertices but no repeated occurrences of edges
(c) No repeated occurrences of vertices, and no repeated occurrences of edges
(d) None of the above
2. Let G = (V(G), E(G)) and H = (V(H), E(H)) be graphs. If G is isomorphic to H,
what may we correctly conclude?
(a) IV(G)I = V(H)j and IE(G)I = IE(H)I
(b) IV(G)I = IV(H)t only.
(c) IE(G)I = IE(H)I only.
(d) None of the above