则G不是哈密顿图.
证 (1) 设v为割点, 则p(G?v) ? 2>|{v}|=1. 根据定理,
G不是哈密顿图.
(2) 若G是K2(K2有桥), 它显然不是哈密顿图. 除K2 外, 其他的有桥连通图均有割点. 由(1), 得证G不是 哈密顿图.
无向哈密顿图的一个充分条件 定理
设G是n阶无向简单图, 若任意两个不相邻的顶点 的度数之和大于等于n?1, 则G中存在哈密顿通路. 当n?3时, 若任意两个不相邻的顶点的度数之和大 于等于n, 则G中存在哈密顿回路, 从而G为哈密顿 图.
哈密顿通路(回路)的存在性(续)
定理中的条件是存在哈密顿通路(回路)的充分条 件, 但不是必要条件.
例如, 设G为长度为n?1(n?4)的路径, 它不满足定理 中哈密顿通路的条件, 但它显然存在哈密顿通路. 设G是长为n的圈, 它不满足定理中哈密顿回路的条 件, 但它显然是哈密顿图.
由定理, 当n?3时, Kn均为哈密顿图. 判断某图是否为哈密顿图至今还是一个难题
判断是否是哈密顿图的可行方法 ? 观察出一条哈密顿回路 例如 右图(周游世界问题)中红 边给出一条哈密顿回路, 故它 是哈密顿图.
注意, 此图不满足定理的条件. ? 满足充分条件
例如 当n?3时, Kn中任何两个不同的顶点 u,v, 均 有d(u)+d(v) = 2(n?1) ? n, 所以Kn为哈密顿图.
例 某次国际会议8人参加，已知每人至少与其余7人中 的4人有共同语言，问服务员能否将他们安排在同一张 圆桌就座，使得每个人都能与两边的人交谈？
解 图是描述事物之间关系的最好的手段之一. 作无向图
G=
由本题想到的：哈密顿图的实质是能将图中所有的顶点 排在同一个圈中. 8.4 平面图 平面图与平面嵌入
定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面嵌入. 没有平面嵌入的图称作非平面图.
例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入，(4)是(3)的平面嵌入. (5)是非平面图.
平面图的面与次数 设G是一个平面嵌入
G的面: 由G的边将平面划分成的每一个区域 无限面(外部面): 面积无限的面, 用R0表示
有限面(内部面): 面积有限的面, 用R1, R2,…, Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用deg(Ri)表示
说明: 构成一个面的边界的回路组可能是初级回路, 简单回 路, 也可能是复杂回路, 还可能是非连通的回路之并. 定理 平面图各面的次数之和等于边数的2倍.
极大平面图: 定义 若G是简单平面图, 并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图, 则称G为极大平面图. 性质
? 若简单平面图中已无不相邻顶点，则是极大平面图. 如
K1, K2, K3, K4都是极大平面图. ? 极大平面图必连通.
? 阶数大于等于3的极大平面图中不可能有割点和桥. ? 设G为n(n?3)阶极大平面图, 则G每个面的次数均为3. ? 任何n(n?4)阶极大平面图G均有δ(G)?3.
极小非平面图: 定义 若G是非平面图, 并且任意删除一条边所得图 都是平面图, 则称G为极小非平面图. 说明:
K5, K3,3都是极小非平面图 极小非平面图必为简单图 下面4个图都是极小非平面图
欧拉公式: 定理8.11 (欧拉公式) 设G为n阶m条边r个面的连通平面图， 则 n?m+r=2.
证 对边数m做归纳证明.
m=0, G为平凡图, 结论为真.
设m=k(k?0)结论为真, m=k+1时分情况讨论如下:
(1) G中无圈, 则G必有一个度数为1的顶点v, 删除v及它关 联的边, 记作G ?. G ?连通, 有n-1个顶点, k条边和r个面. 由归 纳假设, (n-1)-k+r=2, 即n-(k+1)+r=2, 得证m=k+1时结论成立. (2) 否则,删除一个圈上的一条边,记作G ?. G ?连通, 有n个顶
离散数学第八章一些特殊的图知识点总结
