Discrete Mathematics for Computer Science

410 CHAPTER 6 Graph Theory

degree sequence intersection regular graph

distance invariant same

edges isolated vertex self-complementary

even (odd) isomorphic graph

graph isomorphism spanning subgraph

graphical k-cycle subgraph

Hamiltonian cycle length trail

Hamiltonian graph n-cube (Qn ) triangle

hypercube neighbros union

incident n-regular vertex

induced subgraph path vertices

THEOREMS

Handshaking theorem In any graph the number of odd vertices is

even.

6.7-6.8 Summary

TERMS

breadth first search depth first search tree Konigsberg Bridge

breadth first search tree disconnected Problem

connected Eulerian circuit multigraph

connected component Eulerian trail queue

depth first search first-in-first-out list

THEOREMS

Conn is an equivalence relation.

K6nigsberg Bridge Problem

ALGORITHMS

Breadth First Search (Bfs) Connected Components Depth First Search (Dfs)

6.10-6.13 Summary

TERMS

ancestor height right child

A-V-L tree inorder root

binary search tree interior vertex rooted subtree

binary tree leaf rooted tree

child left child rotation

cost level sibling

decision tree Minimum Cost Spanning spanning subgraph

descendant tree (MCST) spanning tree

forest parent terminal vertex

greedy algorithm postorder tree

heap preorder value