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