教案2013第6-7章-图论基础4简

1、16.4 几种特殊的图6.4.1 二部图6.4.2 欧拉图（Euler）6.4.3 哈密尔顿图（Hamilton）6.4.4 平面图26.4.1 二部图定义 6.19 设 无向图 G = ， 若 V1, V2 使得V1V2 = V，V1V2 = ， 且 G 中的每条边的两个端点都 一个属于V1， 另一个属于V2， 则称 G 为二部图。记为： G = 。 若 G 是简单图，且V1中每个顶点均与 V2中每个顶点相邻， 则称 G 为完全二部图，记为 Kr, s 。3定理 6.7 无向图 G = 是二部图，当且仅当 G 中无奇长度的回路。 6.4.1 二部图K23K334实 例非二部图非二部图5例 6

2、.12 某中学有 3 个课外活动小组：数学组、计算机组、生物组。有 赵、钱、孙、李、周 5 名学生，问分别在下述 3 种情况下，能否选出 3 人各任一个组的组长? (1)数学组：赵、钱 计算机：赵、孙、李 生物组：孙、李、周 (2) 数学组：赵 计算机组：钱、孙、李 生物组：钱、孙、李、周 二部图的应用：6解：以课程组及学生为顶点集，作二部图如下。由作图可知： (1)，(2) 有多种方案可选；(3) 不可能。(1)数计生赵钱孙李周(2)数计生赵钱孙李周(3)数计生赵钱孙李周二部图的应用：76.4.2 欧拉图（Euler）一、问题的提出1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡

3、七桥问题”(简称七桥问题)。 这个问题是：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游。 于是便产生了能否“从某地出发，通过每座桥恰好一次，在走遍了七桥后又返回到原处”的问题。8哥尼斯堡城七桥问题 图普雷格尔河 “从某地出发，通过每座桥恰好一次，在走遍了七桥后，又返回到原处”9欧拉巧妙地把哥尼斯堡城图化为图 2 所示的图，把陆地设为图 2 中的顶点，把桥画成联结陆地结点的边。图 1 哥尼斯堡七桥问题 图 2 10 欧拉在这篇论文中提出了一条简单准则，确定七桥问题无解。后来简化为一笔画问题。 即一个图，能否一笔不断，也不重复地画出来? 例： 下

4、面的各图，是否可以一笔画出？NYYN11 二、相关概念 设图 G = 是连通图（无向或有向图）。 1、欧拉通路：G 中经过每条边一次且仅一次的通路。 2、欧拉回路：G 中经过每条边一次且仅一次的回路。 3、欧拉 图：含欧拉回路的图。说明：（1）规定平凡图为欧拉图。（2）欧拉通路是简单通路、欧拉回路是简单回路。（3）图中存在环，不影响图的欧拉性。 6.4.2 欧拉图（Euler）12三、欧拉图判别定理 1（无向图）定理 6.8 （1）无向图 G 是欧拉图， 当且仅当G 是连通的、且无奇度顶点。（2）无向图 G 具有欧拉通路，但无欧拉回路， 当且仅当 G 是连通的、且有且仅有 2 个 奇度顶点。

5、这 2 个奇度顶点，是每条欧拉通路的端点。13YNYN例：下面4 个图中，哪些是欧拉图？14由欧拉图的判别定理知，哥尼斯堡七桥问题无解！15例 6.13（P.179）无欧拉通路欧拉图欧拉图有欧拉通路非欧拉图有欧拉通路非欧拉图无欧拉通路16三、欧拉图判别定理 2（有向图）定理 6.9 （1）有向图 D 是欧拉图，当且仅当 D 是连通的、 且每个顶点的入度出度(顶点度为偶数)。（2）有向图 D 有欧拉通路、但没有欧拉回路， 当且仅当 D 是连通的且存在两个奇度顶点： 一个顶点，其 入度 - 出度 = 1； 一个顶点，其 出度 - 入度 = 1； 其余的顶点，入度 = 出度。17例 6.14（P.1

6、80）欧拉图无欧拉通路无欧拉通路有欧拉通路无欧拉回路无欧拉通路有欧拉通路无欧拉回路181859 年，爱尔兰数学家 哈密尔顿 首先提出 “环球周游”问题。他用一个 正十二面体的20个顶点，代表世界上的20个大城市，这个正十二面体同构于一个平面图 。要求旅游者能否找到沿着正十二面体的棱，从某个顶点（即城市）出发，经过每个顶点恰好一次，然后回到该顶点？6.4.3 哈密尔顿图（Hamilton）19哈密尔顿图20哈密尔顿图21周游世界问题(W.Hamilton, 1859年)22一、相关概念设图 G = 是无向图或有向图。（1）哈密顿通路： 经过图中所有顶点一次且仅一次的通路。（2）哈密顿回路： 经过

7、图中所有顶点一次且仅一次的回路。（3）哈密顿图： 具有哈密顿回路的图。初级通路初级回路注：环与平行边不影响图的哈密顿性。23例：下面图中，是否存在哈密尔顿通路或回路？有哈通路有哈回路有哈回路哈密尔顿图哈密尔顿图24三、哈密顿图的应用 （P.190 例 6.18）例：有 7 个人， A 会讲英语， B 会讲英语和汉语， C 会讲英语、意大利语和俄语， D 会讲日语和汉语， E 会讲德语和意大利语， F 会讲法语、日语和俄语， G 会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈，使得每个人都能与两旁的人交谈?解：作无向图， 每人是一个顶点。两人之间联一条边 他们有共同的语言。A B C D E

8、 FG结论：ACEGFDBA 是一条哈密顿回路， 按此顺序就坐即可。25例 ： 有 7 个人， A 会讲英语， B 会讲英语和汉语， C 会讲英语、意大利语和俄语， D 会讲日语和汉语， E 会讲德语和意大利语， F 会讲法语、日语和俄语， G 会讲法语和德语. 266.4.4 平面图 平面图与平面嵌入 平面图的面及其次数 极大平面图 极小非平面图 欧拉公式 库拉图斯基定理 平面图的对偶图27一、平面图与非平面图定义 6.22 如果能将图 G 除顶点处外边不交叉地画在平面上， 则称 G 是平面图。这个画出的无边交叉的图称作 G 的 平面嵌入。 没有平面嵌入的图，称作非平面图。 上图中： (1)

9、 (4) 是平面图， (5) 是非平面图。 (2) 是 (1) 的平面嵌入； (4) 是 (3) 的平面嵌入。28二、平面图的面与次数定义 6.23 设 G 是一个平面嵌入，（1）G 的面：由 G 的边将平面划分成的每一个区域。（2）无限面(外部面)：面积无限的面，用 R0 表示。（3）有限面(内部面)：面积有限 的面，用 R1, R2, 表示。 （4）面 Ri 的边界： 包围 Ri 的所有边构成的回路组。（5）面 Ri 的次数： Ri 边界的长度，用 deg(Ri) 表示。 说明： 构成一个面的边界的回路组， 可能是初级回路、简单回路、复杂回路； 还可能是非连通的回路之并。29例 1：右图有 个面。4deg(R1)=deg(R2)=deg(R3)=deg(R0)=1328R1 的边界：R2 的边界：R3 的边界：R0 的边界：ab c ef ga b c d d e，f g30(1)R1R2R3(2)R1R2R3说明： （1） 一个平面图，可以有多个不同形式的平面嵌入， 它们