CSCI$-3310$ Homework $9-10$

Problem $1.$ Consider $\backslash ($ G$=($V$,$ E$)\backslash )$ for figure $1$ where $\backslash ($ V $\backslash )$ is the vertex$/$nodes and $\backslash ($ E $\backslash )$ is the edges. $($Hint: for example, for $\backslash ($ V$=\backslash \{$a$,$ b$\backslash \}\backslash )$ and the edge would be $\backslash ($ E$=\backslash$left$\backslash \{$e$\_\{$a b$\}\backslash$right$\backslash \}\backslash ).)$

$(1)$ Write down set of $\backslash ($ V $\backslash )$ and $\backslash ($ E $\backslash ).$

$(2)$ Is $\backslash ($ G $\backslash )$ a tree if $\backslash ($ f $\backslash )$ is a root? If yes, write down the value of $\backslash ($ m $\backslash )$ for m$-$ary tree. If no$,$ explain why.

$(3)$ What is the height of the tree if $\backslash ($ f $\backslash )$ is root?

$(4)$ Suppose the current height of the tree with root $\backslash ($ f $\backslash )$ is $\backslash ($ H $\backslash ).$ You want to insert a node $\backslash ($ j $\backslash )$ to increase the maximum height. Where would you insert it$?$ Draw it out.

Figure $2$: Graph for Problem $1$

Problem $2.$ Consider Figure $2$ again. $(1)$ Write down the adjacent nodes for $\backslash ($ v$\_\{1\}\backslash )$ and $\backslash ($ v$\_\{2\}\backslash ).(2)$ write down the adjacency matrix in the order of $\backslash ($ v$\_\{1\}-$v$\_\{5\}\backslash ).$

Problem $3.$ Given $6$ nodes, construct a binary tree with the following requirement:

$(1)$ Draw a tree with minimum height.

$(2)$ Draw a tree with maximum height.

$(3)$ Prove that your solution for $(2)$ by mathematical induction.