TODO -- try creating github pages similar to site https://github.com/walkccc/CLRS from md file and katex math library.
Let G = (V,E) be Directed acyclic graph in which vertex exits V0 such that there exists unique path from V0 to all vertex. Prove that undirected version of G forms a tree
Solution:
my thoughts.
Lemma 1 : in the DAG all vertices (except V0) have incidence less than 2.
assume a vertex Vx has 2 edges incident on it from Vz and Vy and given V0 has unique path to all vertices, hence V0 --> ... --> Vz is unique and V0 --> ... --> Vy is unique, but V0 --> ... --> Vy --> Vx and V0 --> ... Vz --> Vx are 2 different paths from V0 to Vx. hence contradiction. hence proved lemma 1.
Lemma 2: vertex V0 has no incident edges
assume vertex V0 has incident edge form Vx, and given that V0 --> ... Vy ... --> Vx there is a unique path, hence V0 --> Vy --> Vx --> V0 will become cycle, which contradicts that given graph is acyclic.
Lemma 3: in DAG all vertex (except V0) have incidence == 1.
from given condition that V0 is connected to all, hence incidence is at least 1. and from lemma 1 , incidence is equal to 1.
Lemma 4: |E| = |V| - 1
counting incident edges on each vertex, total vertex = V - 1 since V0 has no incident edges and other have 1 incident edge.
counting incidents edges is sufficient since edge connects 2 nodes.
(not so convincing, put more facts here) how about each incidents edge of node is unique (so no double counting) and all incident edge accounts for all edges of graph (hence no edge is left)
Lemma 5: the undirected graph is connected.
this follows from fact the V0 connects all, removing the direction from edges, all vertices are connected to each other via V0
from Lemma 4 and Lemma 5: graph is tree (proof for this fact is in book in Theorem B.2 property 4)
QED
Show by induction that the number of degree-2 nodes in any nonempty binary tree is 1 fewer than the number of leaves. Conclude that the number of internal nodes in a full binary tree is 1 fewer than the number of leaves.
Solution:
L - leaf, d2N - degree 2 nodes
part1:
base case - 1 root node with 2 children
|d2N| = 1
|L| = 2
therefore |d2N| = |L| - 1
assume a nth case is true for a binary tree (not we are not assuming a full binary tree / complete binary tree) |d2N| = n , |L| = m and n = m -1
now for the next level of leaves, out of m leaves at level nth let us assume that in next level p have 2 child nodes, q have 1 child node and r have no child m = p + q + r
so leaves at (n+1)th level |L| = 2p + q + r
|d2N| = n + p (since only the p contribute to 2 degree nodes)
= m - 1 + p
= p + q + r - 1 + p
= 2p + q + r - 1
= |L| - 1
QED
2nd part is easy since all internal nodes in a full binary tree are degree 2 nodes.
The internal path length of a full binary tree is the sum, taken over all internal nodes of the tree, of the depth of each node. Likewise, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Consider a full binary tree with n internal nodes, internal path length i , and external path length e. Prove that e D i C 2n.
Solution
Note full binary tree is different from complete binary tree. we will prove for a general case.
base cases are easy to check. one root and 2 children OR one root, one children with 2 more children. another children as leaf.
assume ith case is true. (using i to not confuse with n , internal nodes count).
Ei = Mi . i where Ei is external path length at depth i, Mi is the leaf nodes at level i.
so Ei = Li + 2Ni where Ni is the internal path length at depth i. ............ (1)
to prove (i+1)th case.
assume in i+1 depth, from Mi leaves, Pi have children and Qi remain leaf.
Mi = Pi + Qi
so
N(i+1) = Ni + Pi
L(i+1) = Li + i . Pi .......................................(2)
E(i+1) = (i+1) . 2Pi + i . Qi because each Pi with have 2 children since full binary tree
to prove E(i+1) = L(i+1) + 2 . N(i+1)
E(i+1)
= (i+1) . 2Pi + i . Qi
= i.2Pi + 2Pi + i . Qi
= i.(Pi + Qi) + i . Pi + 2Pi
= i . Mi + i . Pi + 2Pi
= Li + 2Ni + 2Pi + i . Pi (from 1 above)
= (Li + i . Pi) + 2 (Ni + Pi)
= L(i+1) + 2 (Ni + Pi) (from 2 above)
= L(i+1) + 2 .N(i+1)
QED