Tree : undirected, connected, cycless graph

←→ undirected, there exists 1 path between any nodes u,v

Free tree

       Parent, children, sibling

     Nonterminal node      ( internal )

       Height

       Internal path length, I= 0 + 1 + 1 + 1 + 2

       External path length, E= 2 + 3 + 2 + 1 + 2 + 2

                        → (1) N + 1 external nodes tree3.gif (2756 bytes)

                             (2) E = I + 2N

                        proof : (1) external ←→ player

                                        internal ←→ game
 
                                  (2) E = I + ( #edges )
 
                                             2 → E

                                             1 →  I