6图论 欧拉图与哈密顿图10 12.pptVIP

判定哈密顿图、半哈密顿图的充分条件： 定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的结点u，v均有 d(u)+d(v)=n-1 则G中存在哈密顿通路 推论 设G是n（≥3)阶无向简单图，若对于G中任意不相邻的结点u，v均有 d(u)+d(v)=n 则G中存在哈密顿回路 由此结论来讨论Kn，当n为何值时Kn为哈密顿图？ 既为哈密顿图又是欧拉图？ 必要条件： 定理15.6 无向图G是哈密顿图，则对于任意V1? V 且 V1 ≠ φ 均有 p(G-V1)≤ |V1| （p(G)为图G的连通分支数） 定理15.8 设u,v为n阶无向简单图G中两个不相邻的结点，且d(u)+d(v)=n则G为哈密顿图当且仅当 G∪(u,v)为哈密顿图 定理15.9 n（≥2)阶竞赛图G中都有哈密顿通路 例：给定有向图D，4个顶点7条边 邻接矩阵为 第十六章 树 一、 无向树 1）定义： 连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树 常用T表示树，平凡图称为平凡树． 若无向图G至少有两个连通分支，则称G为森林． 在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点． 2）树的等价定义 设G＝V，E是n阶m条边的无向图， 则下面各命题是等价的： (1)G是连通无回路（树）． 可通过循环证明 (2) G中任意两个顶点之间存在惟一的路径． （连通则存在路径，若不唯一 （不同路径则构成回路） (3) G中无回路且 m = n - 1． 有长大于等于2的回路都与唯一路径矛盾 对结点进行归纳：n=1平凡图m= 0=n-1， 设n=k成了 n=k+1时 两个结点有唯一的路，去掉则为两个连通分支（各自满足假设） m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1 (4) G是连通的且 m = n - 1． 若不连通，对各个(s=2)连通分支是树且有mi=ni-1 m=n-s s=2 矛盾 (5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路． G无回路：n=1时成立， 归纳看n: 至少有一个结点度数为1（不然，结点的度=2则边=n) 去掉此结点所得到的G’无回路，再加上结点及边也无回路 任何二个结点有通路，增加一条新边构成简单回路（若不是初级的则删去此边，则G中必有简单回路） (6)G是连通的，但删去任何一条边后，所得图不连通． G连通：存在二个结点无通路，则在二个结点添加边后不会出现回路 由于无回路则删去任一条边，图不连通 只要证G无回路：若有回路-则删去一条边后仍连通-与条件矛盾 3）树的性质 对于给定的无向图—树是边数最小的连通图（mn-1则不连通） 树是边数最多的无回路图（mn-1则有回路） 结点的度： Σd(vi) =2(n-1) =2 m 定理： 设T是n阶非平凡的无向树，则T中至少有两片树叶 设：所有结点度=2 则 Σd(vi) =2n 有一个结点度为1其余的=2 则 Σd(vi)=2(n-1)+1=2n-1 （也可以设k个度为1的结点，其余结点的度大于等于2 ） 例：无向树T中度为4、3、2的结点各一个，其余为树叶，树叶＝？ 4) 阶数n比较小的所有非同构的无向树． 例：画出6阶所有非同构的无向树． m=n-1=5 从树的节点之和来分析：结点之和为10分配给6个结点 例：7阶无向树中有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3．试画出满足要求的所有非同构的无向树． 从树的节点之和来分析： Ti为满足要求的无向树，则边数mi = 6， 于是∑d(vi)＝12＝3＋3 +