1.4 图与树

现实世界中，有许多问题可以抽象成图来表示。图是由一些点和连接两点的边组成的。

定义1.10 无向图的定义。

设V是一个非空的有穷集合，E ⊆ V×V，称G=（V, E）为一个无向图。V称为顶点集，V中的元素称为顶点；E称为无向边集，E中的元素称为无向边。

无向图中的边都没有方向。例如，（vi,vj）和（vj,vi）表示的是同一条边。

定义1.11 有向图的定义。

设V是一个非空的有穷集合，E ⊆ V×V，称G=（V, E）为一个有向图。V称为顶点集，V中的元素称为顶点；E称为有向边集，E中的元素称为有向边。

有向图中的边都有方向。例如，（vi,vj）表示的是从顶点vi（前导）出发，到达顶点vj（后继）的一条边；其中，vi称为vj的前导，vj称为vi的后继。（vi,vj）和（vj,vi）表示的是不同的边。

定义1.12 有向路的定义。

设G=（V, E）为一个有向图。若对于1≤i≤k均有（vi, vi+1）∈E，则称v1, v2, v3,…, vk是G的一条有向路。当v1=vk时，v1,v2,v3,…,vk称为一条有向回路。

定义1.13 树的定义。

设G=（V,E）为一个有向图。当G满足如下条件时，称G为一棵（有向）树：

（1）存在一个顶点v没有前导，且v到图中的其他顶点都有一条有向路，该顶点称为树的根节点；

（2）每个非根顶点有且仅有一个前导；

（3）每个顶点的后继按其拓扑关系从左到右排序。

通常，树中的顶点称为节点，某个顶点的前导称为该节点的父亲，某个顶点的后继称为该节点的儿子。若树中有一条从顶点vi到顶点vj的有向路，则称vi是vj的祖先，vj是vi的后代。无儿子的节点称为叶子节点，非叶子节点称为中间节点（分支节点）。