FC1 Week 9 SGT

1

1. Six vertices, where each has degree 3.

   graph {
    rankdir=LR
   	a--b,c,d
    c--d
    e--f
    b--c,e
    d--f
    e--f
   }

2. Six vertices and four edges.

   graph {
    rankdir=LR
   	a--b,c,d,e
    f--b,c,d,e
    e--b,b
    c--d,d
   }

3. Four edges, and four vertices of degrees $1,2,3,4$ respectively. This is not possible as if we add up the degrees of the four vertices, $1+2+3+4=10$, we need $10$ edges to represent all the connections between the vertices. But this is a contradiction the statement says we must use four edges.

   [[Handshaking Theorem]]
    
   $$
   	\Sum 1,2,3,4 = \frac{10}{2} = 5 \text{ edges at minimum}
   $$

2

Hamiltonian:

• $(b,c,d,e,a,b)$ Not Hamiltonian:
• $(b,c,a,b)$
• $(b,c,d,a,b)$
• $(b,c,d,e,a,b)$
• $(d,a,e,d)$
• $(c,d,a,c)$
• $(d,e,a,c,d)$

3

Look at all the vertices of degree $2$:

• Consider the length of the path between the vertices of degree $2$
  • $a$ to $d$ is length $3$
  • $6$ to $8$ is length $3$
  • $v$ to $

Acceptable invariants:

• $I_1$: One path of length $3$.
• $I_2$: Path of length $4$.

Mapping $G_1$ to $G_2$:

• $f(a)=6$
• $f(d)=8$

4

1. Root: $a$
2. Internal: $a,b,d,e,f,g,h,i,o$
3. Leaves: $j,k,f,l,m,c,n,q,r,s,p$
4. $j$ has no children
5. Parent of $h$ is $d$
6. Siblings of $o$ are: $p$
7. Ancestors of $m$ are: $g,b,a$
8. Descendants of $b$ are: $e,f,g,j,k,l,m$

5

1. Construct a BST for the given words.

   graph {
   	node[shape=plain]
    null2,null4,null5,null6,null7[label=""]
    old
    old--never,programmers
    never--die
    programmers--null2,they
    they--their,null4
    die--null5,just
    just--null6,lose
    lose--null7,memories
   }

2. How many comparisons are required to find or add:
   1. lose: $5$ comparisons to find
   2. java: $4$ comparisons to add

6

1. Pre-order traversal: $a,b,e,j,k,f,g,l,m,c,d,h,n,i,o,q,r,s,p$
2. In-order traversal: $j,e,k,b,f,l,g,m,a,c,n,h,d,q,r,o,s,i,p$
3. Post-order traversal: $j,k,e,f,l,m,g,b,c,n,h,q,r,s,o,p,i,d,a$