Discrete Mathematics for Computer Science

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 com-
directed 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