第十三章 几种特殊的图 主要内容 欧拉图 哈密顿图 二部图与匹配 平面图 着色.

Presentation on theme: "第十三章 几种特殊的图 主要内容 欧拉图 哈密顿图 二部图与匹配 平面图 着色."— Presentation transcript:

1 第十三章 几种特殊的图 主要内容 欧拉图 哈密顿图 二部图与匹配 平面图 着色

2 13.1 欧拉图 历史背景：哥尼斯堡七桥问题

3 欧拉图定义 定义13.1 图(无向图或有向图)中所有边恰好通过一次且经过 所有顶点的通路称为欧拉通路. 图中所有边恰好通过一次且
定义13.1 图(无向图或有向图)中所有边恰好通过一次且经过 所有顶点的通路称为欧拉通路. 图中所有边恰好通过一次且 经过所有顶点的回路称为欧拉回路．具有欧拉回路的图称为 欧拉图. 具有欧拉通路而无欧拉回路的图称为半欧拉图． 说明： 规定平凡图为欧拉图. 环不影响图的欧拉性.

4 欧拉图实例 欧拉图 半欧拉图 不是 欧拉图 半欧拉图 不是

5 欧拉图的判别法 定理13.1 (1) 无向图G是欧拉图当且仅当G是连通的且没有奇 度顶点．
(3) 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入 度等于出度． (4) 有向图D是半欧拉图当且仅当D是单向连通的且恰有两个 奇度顶点, 其中一个顶点的入度比出度大1, 另一个顶点出度 比入度大1, 其余顶点的入度等于出度． 例1 设G是非平凡的欧拉图，则(G)2. 证 只需证明G的任意一条边e都不是桥. 设C是一条欧拉回路, e在C上，因而Ge仍是连通的，故e不是桥．

6 Fleury算法 算法： (1) 任取v0V(G), 令P0=v0, i=0. (2) 设Pi = v0e1v1e2…eivi ，
如果E(G)-{e1,e2,…,ei }中没有与vi关联的边, 则计算结束; 否则按下面方法从E(G){e1,e2,…,ei }中选取ei+1： (a) ei+1与vi 关联； (b) 除非无别的边可供选择, 否则ei+1不应为 G{e1,e2,…,ei } 中的桥. 设ei+1=(vi,vi+1), 把ei+1vi+1加入Pi. (3) 令i=i+1, 返回(2).

7 实例 一笔画出一条欧拉回路

8 实例 一笔画出一条欧拉回路

9 13.2 哈密顿图 历史背景：哈密顿周游世界问题 (1) (2)

10 哈密顿图与半哈密顿图 定义13.2 经过图中所有顶点一次且仅一次的通路称作哈密顿 通路. 经过图中所有顶点一次且仅一次的回路称作哈密顿回
路. 具有哈密顿回路的图称作哈密顿图. 具有哈密顿通路且无 哈密顿回路的图称作半哈密顿图. 规定: 平凡图是哈密顿图. 例 哈密顿图 哈密顿图 半哈密顿图 不是

11 无向哈密顿图的一个必要条件 定理13.2 设无向图G=<V,E>是哈密顿图，对于任意V1V且
V1，均有 p(GV1)  |V1| 证 设C为G中一条哈密顿回路 (1) p(CV1)  |V1| (2) p(GV1)  p(CV1)  |V1| （因为CG） 推论 设无向图G=<V,E>是半哈密顿图，对于任意的V1V且V1均有 p(GV1)  |V1|+1 证 设 为从u到v的哈密顿通路，令G = G(u,v)，则G为哈密顿图. 于是 p(GV1) = p(GV1(u,v))  p(GV1)+1  |V1|+1

12 例题 例2 判断下面的图是不是哈密顿图, 是不是半哈密顿图.
例2 判断下面的图是不是哈密顿图, 是不是半哈密顿图. 解 (a)取V1={a,f}, p(GV1)=|{b,c,d,e}|=4>|V1|=2, 不是哈密顿图，也不是半哈密顿图． (b)取V1={a,g,h,i,c}, p(GV1)=| {b,e,f,j,k,d}|=6>|V1|=5, 不是哈密顿图. 而baegjckhfid是一条哈密顿通路, 是半哈密顿图． (c) abcdgihjefa是一条哈密顿回路，是哈密顿图．

13 例题 例3 设G为n阶无向连通简单图，若G中有割点或桥，则G不 是哈密顿图.
证 设v为割点，则 p(Gv)  2>|{v}|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的连通图均有割点.

14 无向哈密顿图的一个充分条件 定理13.3 设G是n阶无向简单图, 若对于任意不相邻的顶点 vi,vj, 均有
d(vi)+d(vj)  n () 则G 中存在哈密顿通路. 推论 设G为n (n3) 阶无向简单图, 若对于G中任意两个不相 邻的顶点vi,vj, 均有 d(vi)+d(vj)  n （） 则G中存在哈密顿回路.

15 判断是否为哈密顿图 判断是否为(半)哈密顿图至今还是一个难题. (1) 观察出一条哈密顿回路或哈密顿通路. (2) 证明满足充分条件.
(3) 证明不满足必要条件. 例4 证明右图(周游世界问题)是哈密顿图 证 a b c d e f g h i j k l m n o p q r s t a 是一条哈密顿回路. 注意，此图不满足定理11.3推论的条件. 例5 完全图Kn (n3)是哈密顿图. 证 任何两个顶点u,v，d(u)+d(v) = 2(n1)  n

16 货郎问题 货郎问题: 有n个城市, 给定城市之间道路的长度(长度可以为 , 对应这两个城市之间无交通线). 货郎从某个城市出发, 要
经过每个城市一次且仅一次, 最后回到出发的城市, 问如何走 才能使他走的路线最短? 图论方法描述如下: 设G=<V,E,W>为一个n阶完全带权图Kn, 各边的权非负, 且可能为. 求G中的一条最短的哈密顿回路. 不计出发点和方向, Kn(n3)中有(n1)!/2 条不同的哈密顿回 路

17 例题 例6 求下面带权图K4中最短哈密顿回路. 解 C1= a b c d a, W(C1)=10
C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)= 最短

18 13.3 二部图与匹配 定义13.3 设 G=<V,E>为一个无向图, 若能将 V分成 V1和V2
(V1V2=V, V1V2=), 使得 G 中的每条边的两个端点都是一 个属于V1, 另一个属于V2, 则称 G 为二部图 ( 或称二分图, 偶 图), 称V1和V2为互补顶点子集, 常将二部图G记为<V1,V2,E>. 又若G是简单二部图, V1中每个顶点均与V2中所有的顶点相邻， 则称G为完全二部图, 记为 Kr,s, 其中r=|V1|, s=|V2|.

19 实例 例 K2,3 K3,3

20 二部图的判别法 定理13.4 无向图G=<V1,V2,E>是二部图当且仅当G中无奇圈 .
证 必要性. 若G中无圈, 结论成立. 若G中有圈, 设G中的一个 圈C=v1v2vlv1, l≥2. 不妨设v1V1, v1,v2,,vl 依次交替属于V1, V2且vlV2, 因而l为偶数. 得证C为偶圈． 充分性. 不妨设G为连通图, 否则可对每个连通分支进行讨论, 孤立点可根据需要分属V1和V2. 设v0为G中任意一个顶点, 令 V1={v | vV(G)d(v0,v)为偶数} V2={v | vV(G)d(v0,v)为奇数} d(v0,v)是v0到v的最短路径的边数(每条边的权为1). V1， V2, V1V2=, V1V2=V(G). 要证V1中任意两点不相邻．

21 证明 假若存在vi,vjV1相邻, 记e=(vi,vj), 设v0到vi,vj的最短路径分别
为i, j, 由i,j和e构成一条长度为奇数的回路. 这条回路可 能是一条复杂回路, 可以分解成若干由i,j共有的边构成的 回路(实际上是每条边重复一次的路径)和由i,j不共有的边 及e构成的圈. 由i,j共有的边构成的回路的长度为偶数, 故在 由i,j不共有的边(可以还包括e)构成的圈中一定有奇圈, 这 与已知条件矛盾. 得证V1中任意两顶点不相邻. 由对称性, V2 中也不存在相邻的顶点, 得证G为二部图．

22 最大匹配 定义13.4 设G=<V1,V2,E>为二部图, ME, 如果M中的任意两
条边都不相邻, 则称M是G的一个匹配. G中边数最多的匹配 称作最大匹配. 又设|V1||V2|, 如果M是G的一个匹配且 |M|=|V1|, 则称M是V1到V2的完备匹配. 当|V2|=|V1|时, 完备匹 配又称作完美匹配． 例 完备匹配 完美匹配 最大匹配

23 与匹配有关的概念 定义13.5 设M是二部图G=<V1,V2,E>的一个匹配. 称M中的边
边和非匹配边交替构成的路径称为交错路径, 起点和终点都是 非饱和点的交错路径称为可增广的交错路径． M为G的完备匹配当且仅当V1或V2中的每个顶点都是饱和点． M为G的完美匹配当且仅当G中的每个顶点都是饱和点．

24 可增广的交错路径 例 u1 u2 u3 u4 v1 v2 v3 v4 左图, 饱和点:u1,u3,u4,v1,v2,v3; 非饱和点:u2,v4; 可增广的交错路径 : u2v3u4v2u1v4. 由 得到多一条边的匹配. 设M为G的一个匹配, 是关于M的可增广的交错路径, 则 M =ME( )=(ME( ))(ME( )) 是比M多一条边的匹配. 定理13.5 M为G的最大匹配G中不含M的可增广的交错路径.

25 Hall定理 定理13.6 (Hall定理) 设二部图G=<V1,V2,E>, 其中|V1||V2|, 则
G中存在从V1到V2的完备匹配当且仅当V1中任意k(1k|V1|) 个顶点至少与V2中的k个顶点相邻.(相异性条件) 证 必要性显然. 证充分性. 设M为G的最大匹配, 若M不是完备 的, 则存在非饱和点vxV1. 于是, 存在eE1=EM与vx关联, 且 V2中与vx相邻的顶点都是饱和点. 考虑从vx出发的尽可能长的 所有交错路径, 这些交错路径都不是可增广的, 因此每条路径 的另一个端点一定是饱和点, 从而全在V1中. 令 S={v | vV1且v在从vx出发的交错路径上} T={v | vV2且v在从vx出发的交错路径上} 除vx外, S和T中的顶点都是饱和点, 且由匹配边给出两者之间 的一一对应, 因而|S|=|T|+1. 这说明V1中有|T|+1个顶点只与V2 中|T|个顶点相邻, 与相异性条件矛盾.

26 t条件 例 前两个满足相异性条件, 第3个不满足 定理13.7 设二部图G=<V1,V2,E>, 如果存在t使得, V1中每个顶
点至少关联t条边, 而V2中每个顶点至多关联 t 条边, 则G 中存 在V1到V2的完备匹配.(t条件) 证 V1中任意k(1k|V1|)个顶点至少关联kt条边, 而V2中每个顶 点至多关联t条边, 这kt条边至少关联V2中k个顶点. G满足相异 性条件． 第2个图不满足t条件, 但有完备匹配.

27 一个应用实例 例7 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、
想去广州或香港. 问该课题组在满足个人要求的条件下，共 有几种派遣方案？ 解 令G=<V1,V2,E>，其中V1={s, g, x}，s, g, x分别表示上海、广州和香港. V2={a, b, c, d, e}, E={(u,v) | uV1, vV2, v想去u}. 每个V1到V2的完备匹配给出一个派遣方案, 共有9种.如a到上海, b到广州, c到香港.

28 13.4 平面图 定义13.6 如果能将无向图G画在平面上使得除顶点处外无边相交, 则称G是可平面图, 简称平面图. 画出的无边相交的图称为G的平面嵌入. 无平面嵌入的图称为非平面图． 例 (1) (2) (3) (4) (2)是(1) 的平面嵌入，(4)是(3)的平面嵌入.

29 平面图的性质 K5, K3,3都是非平面图（定理11.13） 平行边与环不影响平面性.
定理13.8 平面图的子图都是平面图, 非平面图的母图都是非 平面图． 例如, 所有度数不超过4的简单图都是平面图. 当|V1|=1和2时二部图G=<V1,V2,E>是平面图. Kn(n5)和Ks,t(s,t3)都是非平面图.

30 平面图的面与次数 定义13.7 给定平面图G的平面嵌入, G的边将平面划分成若干 个区域, 每个区域都称为G的一个面, 其中有一个面的面积无
限, 称为无限面或外部面, 其余面的面积有限, 称为有限面或 内部面. 包围每个面的所有边组成的回路组称为该面的边界， 边界的长度称为该面的次数．面R的次数记为deg(R)． 例 deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8.

31 次数的性质 定理13.4 平面图各面次数之和等于边数的两倍. 证 对每一条边e, 若e在两个面的公共边界上, 则在计算这两 个面的次数时, e各提供1. 而当e只在某一个面的边界上出现 时, 它必在该面的边界上出现两次, 从而在计算该面的次数时, e提供2．

32 极大平面图 定义13.8 G为简单平面图, 若在G的任意两个不相邻的顶点 之间加一条边所得图为非平面图, 则称G为极大平面图.
例如, K5,K33删去一条边后是极大平面图 K1, K2, K3, K4都是极大平面图. 定理 设G为n(n3)阶简单连通的平面图, G为极大平面图当且仅当G的每个面的次数均为3. 证 现只证必要性. 各面次数都大于或等于3. 假如deg(Ri)=s4, 若v1与v3不相邻, 则在Ri内加边(v1,v3)不 破坏平面性, 与G是极大平面图矛盾, 因 而v1与v3必相邻, 且边(v1,v3)必在Ri外部. 同样地, v2与v4也相邻且边(v2,v4)在Ri的 外部. 于是, (v1,v3)与(v2,v4)相交于Ri的外 部, 与G是平面图矛盾.

33 定理的应用 例 是否是极大平面图? (1) (2) (3) 只有(3)为极大平面图

34 极小非平面图 定义13.9 若在非平面图G中任意删除一条边, 所得图为平面图, 则称G为极小非平面图. K5, K3,3都是极小非平面图
极小非平面图必为简单图

35 欧拉公式 定理13.11 设G为n阶m条边r个面的连通平面图, 则 nm+r=2
证 对m做归纳证明. m=0时, G为平凡图, n=1,m=0,r=1,成立. 设m=k(k0)时结论成立. 当m=k+1时, 分两者情况讨论: (1) G中有一个1度顶点v, 令G =Gv, 仍是连通的, n =n1, m =m1=k, r =r. 由归纳假设, nm +r =2. 于是 nm+r = (n +1)(m +1)+r = n m +r = 2 (2) G中没有1度顶点, 则每一条边都在某两个面的公共边界 上. 任取一条边e, 令G =Ge, 仍连通且n =n, m =m1=k, r =r1. 由归纳假设, n m +r =2. 于是 nm+r = n (m +1)+(r +1) = n m +r = 2

36 欧拉公式的推广 推论 对于有k个连通分支的平面图G, 有 n  m + r = k+1 其中n, m, r分别为G的顶点数, 边数和面数. 证 设G的连通分支为G1,G2,…,Gk, 由欧拉公式 ni  mi + ri = 2, i=1,2,…,k. G的面数 . 于是， 整理得

37 与欧拉公式有关的定理 定理13.12 设G为连通的平面图, 每个面的次数至少为l3，则 证 由定理11.9及欧拉公式, 解得
证 由定理11.9及欧拉公式, 解得 定理 K5, K3,3都是非平面图. 证 假设K5是平面图, K5无环和平行边, 每个面的次数均大于等 于3. 应该有 矛盾.

38 与欧拉公式有关的定理 证(续) 假设K3,3是平面图, K3,3中最短圈的长度为4, 每个面的次数均大于等于4. 应该有 矛盾.
定理 设G为n(n3)阶m条边的极大平面图, 则m=3n6. 证 极大平面图是连通图, 由欧拉公式得 r = 2+mn. 又由定理11.10的必要性, G的每个面的次数均为3, 所以2m=3r. 得m=3n6． 推论 设G是n(n3)阶m条边的简单平面图, 则 m3n6

39 定理13.10充分性证明 如果简单连通平面图G的每个面的次数都等于3, 则G为极大平面图. 证 由定理13.9, 2m=3r 由欧拉公式,
证 由定理13.9, 2m=3r 由欧拉公式, r = 2 + m  n 整理得 m = 3n6 若G不是极大平面图, 则G中存在不相邻的顶点u,v, 使得G =G(u,v)还是简单平面图, 而G 的边数m =m+1, n =n, 故 m >3n6 与定理13.14的推论矛盾．

40 同胚 定义 设e=(u,v)为图G的一条边, 在G中删除e, 增加新的顶点w, 使u,v均与w相邻, 称为在G中插入2度顶点w. 设w为G中一个2度顶点, w与u,v相邻, 删除w, 增加新边(u,v), 称为在G中消去2度顶点w. 若两个图G1与G2同构, 或通过反复插入、消去2度顶点后同构, 则称G1与G2同胚． 例 插入与消去2度顶点 收缩边

41 库拉图斯基定理 定理13.15 G是平面图  G中不含与K5和K3,3同胚的子图.
例8 证明下边两个图为非平面图. 与K3,3同胚 。 与K5同胚 。

42 例题 例9 证明彼得森图为非平面图. 与K3,3同胚 与K5同胚 收缩(b,g),(c,h), 收缩(a,f),(b,g),
例9 证明彼得森图为非平面图. 与K5同胚 收缩(a,f),(b,g), (c,h),(d,i),(e,j) 与K3,3同胚 收缩(b,g),(c,h), (d,i),(e,j)

43 点着色 定义 设无向图G无环, 对G的每个顶点涂一种颜色, 使相邻的顶点涂不同的颜色, 称为图G的一种点着色,简称着色. 若能用k种颜色给G的顶点着色， 则称G是k-可着色的． 图的着色问题: 要用尽可能少的颜色给图着色. 1 2 3 4 例10 偶圈用2种颜色, 奇圈用3种. 奇阶轮图用3种, 偶阶轮图用4种. 例11 G是2-可着色的当且仅当G是二部图.

44 应用 1. 有n项工作, 每项工作需要一天的时间, 有些工作不能同时进行, 问至少需要几天才能完成所有的工作? 顶点表示工作, 两点之间有一条边这两项工作不能同时进行. 工作的时间安排对应于这个图的点着色: 着同一种颜色的顶点对应的工作可安排在同一天, 所需的最少天数是所需要的最少颜色数. 2. 寄存器分配. 计算机有k个寄存器, 要给每一个变量分配一 个寄存器. 如果两个变量要在同一时刻使用, 则不能把它们分 配给同一个寄存器. 每一个变量是一个顶点, 如果两个变量要 在同一时刻使用, 则用一条边连接这两个变量. 这个图的k-着 色对应给变量分配寄存器的一种安全方式: 给着同一种颜色 的变量分配同一个寄存器.

45 应用 3. 无线交换设备的波长分配. 有n台设备和k个发射波长, 要给每一台设备分配一个波长. 如果两台设备靠得太近, 则不能给它们分配相同的波长. 以设备为顶点, 如果两台设备靠得太近, 则用一条边连接它们. 这个图的k-着色给出一个波长分配方案: 给着同一种颜色的设备分配同一个波长.

46 地图着色与对偶图 地图: 连通无桥平面图的平面嵌入. 每一个面是一个国家(或省, 市, 区等). 若两个国家有公共的边界，则称这两个国家是相邻的. 对地图的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对地图的面着色, 简称地图着色. 地图着色问题: 用尽可能少的颜色给地图着色. 定义 设G是一个平面嵌入, 构造图G*如下: 在G的每一个面Ri中放置一个顶点vi*. 设e为G的一条边, 若e在G的面Ri与Rj的公共边界上, 则作边e*=(vi*,vj*)与e相交, 且不与其他任何边相交. 若e为G中的桥且在面Ri的边界上, 则作以vi*为端点的环e*=(vi*,vi*). 称G*为G的对偶图.

47 实例 实线和空心点是平面嵌入, 虚线和实心点是对偶图. 注意: 这两个平面嵌入是同一个平面图的平面嵌入.

48 四色定理 四色猜想(19世纪50年代, 德摩根)  五色定理(1890年, 希伍德)  四色定理(1976年, 阿佩尔与黑肯)
定理 任何平面图都是4-可着色的.

49 第十一章 习题课 主要内容 欧拉通路与欧拉回路, 欧拉图与半欧拉图及判别 哈密顿通路与哈密顿回路, 哈密顿图与半哈密顿图及判别 货郎问题
二部图及其判别 二部图匹配及相关概念 二部图最大匹配的充要条件, 存在完备匹配的条件 平面图及其性质(欧拉公式) 平面图的判别 着色问题 地图着色与平面图的对偶图 四色定理 应用

50 基本要求 基本要求 深刻理解欧拉图, 半欧拉图, 哈密顿图, 半哈密顿图的定义 掌握欧拉图, 半欧拉图的判别
会用哈密顿图与半哈密顿图的必要条件和充分条件 会一笔画出欧拉回路 了解货郎问题 深刻理解二部图的定义, 掌握二部图的判别 深刻理解二部图匹配及相关概念 了解二部图最大匹配的充要条件, 会用存在完备匹配的条件(Hall定理与t条件)

51 基本要求 深刻理解平面图及相关的概念 牢记极大平面图的主要性质和判别方法 熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题
会用库拉图斯基定理证明非平面图 了解对偶图的概念 了解着色问题, 地图着色问题和四色定理 会用上述概念和有关定理解决简单的实际问题

52 练习1 1. 设G为n(n2)阶无向欧拉图, 证明G中无桥.
证一 设C为G中一条欧拉回路, eE(G), e在C上, Ce 连通, Ge也连通, 所以e不为桥. 证二 用反证法. 假设e=(u,v)是桥, 则Ge产生两个连通分支G1, G2, 不妨设u在G1中, v在G2中. G中没有奇度顶点, 而删除e,只使u,v 的度数各减1, 因而G1(G2)中只含一个奇度顶点, 与任何图中奇度顶点的个数是偶数矛盾.

53 练习 2 2. 证明右图不是哈密顿图. 证一 取 V1 = {a, c, e, h, j, l}，
p(GV1) = 7 > 6=|V1| 证二 G为二部图, V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}, |V1|  |V2|. 证三 n = 13, m = 21. h, l, j为4度顶点, a, c, e为3度顶点, 且它 们关联不相同的边. 而在哈密顿回路上, 每个顶点关联两条边, 于是可能用于哈密顿回路的边至多有21(32+31) = 条 边不可能构成经过13个顶点的回路.

54 练习 3 3．某次国际会议8人参加, 已知每人至少与其余7人中的4人能用相同的语言, 问服务员能否将他们安排在同一张圆桌就座, 使得每个人都能与两边的人交谈？ 解 做无向图G=<V,E>, 其中V={v| v为与会者}， E={(u,v) | u,vV, u与v有能用相同的语言, 且u  v}. G为简单图且vV, d(v)4. 于是, u,vV, d(u)+d(v)  8,故G为哈密顿图. 服务员在G中找一条哈密顿回路, 按回路中相邻关系安排座位即可.

55 练习 4 4. 某公司招聘了3名大学毕业生, 有5个部门需要人. 部门领导与毕业生交谈后, 双方都愿意的结果如表所示. 如果每个部门只能接收一名毕业生, 问这3名毕业生都能到他满意的部门工作吗?试给出分配方案. 部门1 部门2 部门3 部门4 部门5 毕业生A    毕业生B    毕业生C    解 作二部图G=<V1,V2,E> 1 A B C 2 3 4 5 一个分配方案是G的一个匹配. G满足t条件, t=3, 有完备匹配. 如, A1, B 2, C 3; A 3, B 2, C 5等.

56 练习5 5. 设G是连通的简单平面图, 面数r<12, (G)3. (1) 证明G中存在次数4的面.
解 设G的阶数, 边数, 面数分别为n, m, r. (1) 用反证法. 假设所有面的次数大于等于5, 由欧拉公式得 2m 5r = 5 (2+mn) ① 由(G)3及握手定理有 2m  3n ② 得 m30 又有 r=2+mn < ③ ③ 与②又可得 m<30, 矛盾. (2) 正十二面体是一个反例

57 练习6 6. 设G是阶数11的非平凡简单无向图, 证明G和 不可能全是平面图. 证 用反证法. 假设 与G 都是平面图, 则
G与 的边数m, m应满足 不妨设 由于G是平面图, 又有 m  3n  6 得 n213n+24  0 解得  n 10 与n 11矛盾.

58 练习7 7. 证明下图为非平面图 证一 含子图K3,3: 删去顶点a和边(c,d)
证二 含与K5同胚的子图: 删去(a,f), 收缩(a,e)和(f,g)

59 练习8 8. 给下图着色至少要用几种颜色? 解 由于a, b, c 彼此相邻, 至少要用3种颜色, 设它们分别着颜色1,2,3. 最少还要用这三种颜色给d, e, f 着色. 而g与d, e, f相邻只能用第4种颜色. 故至少要用4种颜色.

60 练习9 9. 某校计算机系三年级学生在本学期共有6门选修课Ci, i=1, 2, …, 6. 设S(Ci)为选Ci课的学生集. 已知
S(Ci)S(C6)  , i=1, 2, …, 5， S(Ci)S(Ci+1)  , i=1, 2, 3, 4， S(C5)S(C1)  . 问这6门课至少几天能考完？ 解 做无向图G=<V,E>, 其中 V={C1, C2, …, C6} E={(Ci,Cj)| S(Ci)S(Cj)} 最少要用4种颜色着色, 故最少要4天