图论__树.pptVIP

图 论 图——基本概念 图、路与连通、最短路、有向图、图的矩阵 Euler图与Hamilton图 树 树、生成树、有向树 平面图　图的着色 平面图、对偶图、顶点着色、面着色 网络　匹配　独立集 树 树的概念 生成树 有向树 树 定义1　连通无回路的图称为树，树中度为1的点称为树叶，度大于1的点称为分枝点或内点，每个连通分支均为树的图称为森林。 定理1　设图T是有n个顶点、ε条边的非平凡图，则下列各条等价。 (1) T是树。 (2) T中无回路，且ε＝n－1。 (3) T连通，且ε＝n－1。 (4) T中无回路，且在T的任意两个不相邻点之间添加一边恰得一条回路。 (5) T连通，删去任一边则不连通。 (6) T的任意两个不同顶点之间恰有一条路。 定理２　任意一棵非平凡树 T 中，至少有两片树叶。 作业 证明　非平凡树中最长路的起点和终点均为树叶。 证明　一棵树恰有２片树叶，则此树为路。 生成树 定义1　若图G的生成子图T是树，则称T为G的生成树。 定理1　G是连通图当且仅当G有生成树。 权图G中带权最小的生成树称为最小生成树 Kruskal算法 输入：简单连通图G ，权函数w 。 输出：最小生成树T Kruskal算法 (1)选取G的一边e1，使w(e1)＝min{w(e)|e?E}，令E1＝｛e1｝ (2)若已选出Ei＝｛e1，…，ei｝，那么，从E－Ei中选取一边ei＋1，使 (Ⅰ)Ei∪｛ei＋1｝的导出子图中不含回路； (Ⅱ)w(ei＋1)＝min{w(e)|e?E－Ei , Ei∪{e}的导 出子图无回路} (3)若ei＋1存在，令Ei＋1＝Ei∪｛ei＋1｝，i＋1→i，转(2)，若ei＋1不存在，则停止。 上面的算法能执行吗？ 会终止吗？ 每次执行结果一样不一样？ 定理２　Kruskal算法得到的图T*是最小生成树。 证明:　 （1）T*是生成树。 （2） E(T*) ＝｛e1，…，en-1｝，若T*不是最小生成树，设T1是最小生成树，则T*中必有边不在T1中，设ek是第一条不在T1中的边…… 有向树 定义1　设D是一个有向图，如果在不考虑弧的方向时D是一棵树(即D的底图是一棵树)则称D为一棵有向树。 定义２　若一棵有向树中恰有一个顶点的入度为０，其余所有顶点的入度均为1，则称该有向树为有根树(或树形图)，入度为０的顶点称为根。 定理1　设T是一棵有根树，r是T的根，则r到其余每个顶点恰有一条有向路。 有根树的画法 定义３　儿子，父亲，兄弟，子孙，祖先；从根到某一顶点的路长称为该顶点的路长或层数，从根到树叶的最大层数，称为有根树的高。 定义４　设u是有根树T的一个顶点，Vu是u及其子孙构成的顶点集，Vu的导出子图称为T的以u为根的子树。 定义５　有序树 定义６　在有序树中，如果每个顶点v都满足ｄ＋(v)≤m，则称该有序树为m叉树，如果每个顶点v都满足ｄ＋(v)＝m，称该有序树为正则m叉树。 一类重要的m叉树是二叉树和正则二叉树。左儿子、右儿子，左子树、右子树。 定理２　在正则m叉树中，分枝点数i与树叶数l满足 (m－1)i＝l－1。 定理３　设T是正则m叉树，I表示分枝点的路长总和，L表示树叶的路长总和，i是分枝点数，则 L＝(m－1)I＋mi。 作业 对非平凡正则m叉数的分枝点数i施行归纳法，以证明定理２。 *