[2018年最新整理]15第十五次课(图论与总结).ppt

Hongzhi Qiao, XiDian Univ. 定义1： 简单图的着色/coloring 定理 四色定理/four color theorem 离散数学 总结 * Graphs/图论 * 由上面的讨论不难看出，若两个图同构，它们必须满足: 结点个数相等； 边数相等； 度数相同的结点个数相等。 上面的三个条件只是两个图同构的必要条件，不是充分条件。 上图中(a)，(b)两图示满足上述三个条件，但由于(a)中度数为3的结点v1与两个度数为1的结点v2， v3相邻，而在(b)中，度数为3的结点u1只与一个度数为1的结点u2相邻，故(a)，(b) 不同构。 v1 v2 v3 u1 u2 (a) (b) [定理1]（欧拉定理）： 没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是０个或2个。 第八章 --- 图论 说明： 哥尼斯堡七桥问题，由于四个顶点都是奇次的，不可能有欧拉道路。 应用与推广： （1） 一笔画问题； （2） 如果奇次顶点个数为2K个，此问题是K笔画问题。 第八章 --- 图论 Hamilton(哈密顿)道路问题： １８５９年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。 第八章 --- 图论 [定义]哈密顿道路/回路： Ｇ＝（Ｖ，Ｅ），G中经过Ｖ中所有顶点的基本道路称为哈密顿道路/Hamilton Path，简称Ｈ道路。 Ｇ＝（Ｖ，Ｅ），G中经过Ｖ中所有顶点的基本回路称为哈密顿回路/Hamilton Circuit，简称Ｈ回路。 第八章 --- 图论 图Ａ 每个顶点都是奇次的，不存在欧拉道路，但有Ｈ道路。 图Ｂ存在欧拉道路，不存在Ｈ道路。 第八章 --- 图论 [定理3]：设Ｇ＝（Ｖ，Ｅ）是ｎ个顶点的简单图，如果任何一对顶点的次之和≥ｎ－１，则Ｇ中一定有Ｈ道路。 注意: 此定理条件显然不是必要条件，如ｎ≥６的ｎ边形，二个顶点次之和＝４， ４＜ｎ－１，而ｎ边形显然有Ｈ道路。 第八章 --- 图论 每一个顶点指定一个颜色使得任意两个相邻顶点有不同的颜色。 定义2： 简单图的色数/chromatic number 图的着色中使用的最小颜色数。 第八章 --- 图论 任意一个图的色数小于等于4。 第八章 --- 图论 * Graphs/图论