unit 5 part 3 Flashcards
Hamilitonian path
example
each vertex once
Hamiltonian circuit/graph/cycle
example
first and last vertex same
hypercube, square
not ever a hami cycle
bipartite no split vertices equal
Rules for hami path/cycle
G: n vertices, -> path: n-1 edges, cycle: n edges
deg(V) = K path: 1 <= edges incident on V <= 2 cycle = 2 edges
all vertices of G
path through V delete all unused edges incident on V
Trees denoted by
T
When graph -> tree
connected, no closed loops
rooted tree
root (indegree 0) uppermost-> other away
directed path to each vertex fro root (indegree 1) lower
leaf node
pendant vertex
forest
disconnected graph
tree def
connected graph -> n vertices, n-1 edges
directed tree
up to down, downward arrows
root
indegree 0
parent
predecessor to node
child
descendent of node
siblings
same parent
ancestors
node connected to all lower level nodes
descendents
all lower level nodes
leaf
no children
internal vertices
children
subtree
tree child of node
length(V)
unique path from root to V
height
max levels
length of path from root to furthest node
m-ary trees
rooted tree every internal node has m children
2-ary tree called
binary tree
balanced tree
rooted tree height h, leaves all atlevels h or h-1
full binary tree
all trees at level l, 0 or 2 children each node
spanning tree
subG of connected G, all vertices of G
finding spanning tree
bfs and dfs
bfs
all vertices on same level first
dfs
explores as far as possible before backtracking
