Discrete Mathematics for Computer Science

Finding a Cycle in a Directed Graph 397 User 1 I Tape Drive User 2 Disk Drive User 3 0*-- Printer allocated requested Figure 6.5 ...

398 CHAPTER 6 Graph Theory cycle-that is, those vertices of outdegree zero. Q is the queue of vertices in NotlnCycle waiting to ...

Priority in Scheduling 399 6.20, and the correct result is returned. This follows because Q = 0 and the outer loop is never ente ...

400 CHAPTER 6 Graph Theory Before examining the general problem, consider the smaller scheduling problem rep- resented by the di ...

Priority in Scheduling 401 INPUT: A directed acyclic graph D(V, E) OUTPUT: An ordering of the vertices so that if D contains a d ...

402 CHAPTER 6 Graph Theory The induced subgraph D 1 formed from the set of vertices still marked FALSE that remain will be a dag ...

Connectivity in Directed Graphs 403 The property of having two directed paths joining a pair of vertices, one path in each direc ...

404 CHAPTER 6 Graph Theory 6.18.2 Application: Designing One-Way Street Grids To alleviate traffic problems on narrow, crowded s ...

Eulerian Circuits in Directed Graphs 405 Definition 3. Let G be an undirected graph and 0 an orientation for the edges of G. G i ...

4M6 CHAPTER 6 Graph Theory Information Links on the Web The pages accessible from a Web browser can be represented by a graph in ...

Exercises 407 Verify that the following graph D is a dag. Perform a topological sort on the vertices of the graph. a h f e D ...

408 CHAPTER 6 Graph Theory For the tournament shown, find a ranking of the players: a b d c Let D = (V, E) be a tournament. P ...

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, ...

410 CHAPTER 6 Graph Theory degree sequence intersection regular graph distance invariant same edges isolated vertex self-complem ...

Chapter Review 411 vertex label weight vertex label listing weighted graph THEOREM Tree Characterization ALGORITHMS Minimum Cost ...

412 CHAPTER 6 Graph Theory Let D = (V, E) be a directed graph. An edge (a, b) E E: (a) Contributes one to the indegree of a (b) ...

Chapter Review^413 List the vertices in the tree shown when they are visited in a preorder traversal and in a postorder travers ...

414 CHAPTER 6 Graph Theory Prove that G has no Hamiltonian cycle that contains the edge (e, j). a h g e c f d G Prove that th ...

Chapter Review 415 degree value. (Hint: If I V I is even, then the repeated degree can have two possible values. If I V I is odd ...

416 CHAPTER 6 Graph Theory Topologically sort D. 5 4 6 3 7 2 8 D Prove that G contains no Hamiltonian cycle. G 16. Let A be ...