unit 5 part 3

Question 1

Hamilitonian path

example

Answer 1

each vertex once

Question 2

Hamiltonian circuit/graph/cycle

example

Answer 2

first and last vertex same

hypercube, square

Question 3

not ever a hami cycle

Answer 3

bipartite no split vertices equal

Question 4

Rules for hami path/cycle

Answer 4

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

Question 5

Trees denoted by

Answer 5

T

Question 6

When graph -> tree

Answer 6

connected, no closed loops

Question 7

rooted tree

Answer 7

root (indegree 0) uppermost-> other away

directed path to each vertex fro root (indegree 1) lower

Question 8

leaf node

Answer 8

pendant vertex

Question 9

forest

Answer 9

disconnected graph

Question 10

tree def

Answer 10

connected graph -> n vertices, n-1 edges

Question 11

directed tree

Answer 11

up to down, downward arrows

Question 12

root

Answer 12

indegree 0

Question 13

parent

Answer 13

predecessor to node

Question 14

child

Answer 14

descendent of node

Question 15

siblings

Answer 15

same parent

Question 16

ancestors

Answer 16

node connected to all lower level nodes

Question 17

descendents

Answer 17

all lower level nodes

Question 18

leaf

Answer 18

no children

Question 19

internal vertices

Answer 19

children

Question 20

subtree

Answer 20

tree child of node

Question 21

length(V)

Answer 21

unique path from root to V

Question 22

height

Answer 22

max levels

length of path from root to furthest node

Question 23

m-ary trees

Answer 23

rooted tree every internal node has m children

Question 24

2-ary tree called

Answer 24

binary tree

Question 25

balanced tree

Answer 25

rooted tree height h, leaves all atlevels h or h-1

Question 26

full binary tree

Answer 26

all trees at level l, 0 or 2 children each node

Question 27

spanning tree

Answer 27

subG of connected G, all vertices of G

Question 28

finding spanning tree

Answer 28

bfs and dfs

Question 29

bfs

Answer 29

all vertices on same level first

Question 30

dfs

Answer 30

explores as far as possible before backtracking