1.4 圖與樹

現(xiàn)實(shí)世界中，有許多問題可以抽象成圖來表示。圖是由一些點(diǎn)和連接兩點(diǎn)的邊組成的。

定義1.10 無向圖的定義。

設(shè)V是一個(gè)非空的有窮集合，E ? V×V，稱G=（V, E）為一個(gè)無向圖。V稱為頂點(diǎn)集，V中的元素稱為頂點(diǎn)；E稱為無向邊集，E中的元素稱為無向邊。

無向圖中的邊都沒有方向。例如，（vi,vj）和（vj,vi）表示的是同一條邊。

定義1.11 有向圖的定義。

設(shè)V是一個(gè)非空的有窮集合，E ? V×V，稱G=（V, E）為一個(gè)有向圖。V稱為頂點(diǎn)集，V中的元素稱為頂點(diǎn)；E稱為有向邊集，E中的元素稱為有向邊。

有向圖中的邊都有方向。例如，（vi,vj）表示的是從頂點(diǎn)vi（前導(dǎo)）出發(fā)，到達(dá)頂點(diǎn)vj（后繼）的一條邊；其中，vi稱為vj的前導(dǎo)，vj稱為vi的后繼。（vi,vj）和（vj,vi）表示的是不同的邊。

定義1.12 有向路的定義。

設(shè)G=（V, E）為一個(gè)有向圖。若對(duì)于1≤i≤k均有（vi, vi+1）∈E，則稱v1, v2, v3,…, vk是G的一條有向路。當(dāng)v1=vk時(shí)，v1,v2,v3,…,vk稱為一條有向回路。

定義1.13 樹的定義。

設(shè)G=（V,E）為一個(gè)有向圖。當(dāng)G滿足如下條件時(shí)，稱G為一棵（有向）樹：

（1）存在一個(gè)頂點(diǎn)v沒有前導(dǎo)，且v到圖中的其他頂點(diǎn)都有一條有向路，該頂點(diǎn)稱為樹的根節(jié)點(diǎn)；

（2）每個(gè)非根頂點(diǎn)有且僅有一個(gè)前導(dǎo)；

（3）每個(gè)頂點(diǎn)的后繼按其拓?fù)潢P(guān)系從左到右排序。

通常，樹中的頂點(diǎn)稱為節(jié)點(diǎn)，某個(gè)頂點(diǎn)的前導(dǎo)稱為該節(jié)點(diǎn)的父親，某個(gè)頂點(diǎn)的后繼稱為該節(jié)點(diǎn)的兒子。若樹中有一條從頂點(diǎn)vi到頂點(diǎn)vj的有向路，則稱vi是vj的祖先，vj是vi的后代。無兒子的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)稱為中間節(jié)點(diǎn)（分支節(jié)點(diǎn)）。