几类特殊的图课件.pptVIP

Chapter 8 几类特殊的图 图论是处理离散对象的一种重要的数学工具. 本章讨论几类在理论研究和实际应用中都有着重要意义的特殊图. Euler图; Hamilton图; 无向树; 有向树(特别是根树); 平面图及其面着色; 二部图等. 8.1 Euler图 1.Euler图的有关概念 8.2 Hamilton 图 1859年爱尔兰数学家W. R. Hamilton发明了一个周游世界游戏: 在一个正12面体的20个顶点上标示世界上的20个大城市,若从一个城市出发,沿正12面体的棱旅行,经过每个城市一次且仅经过一次,最后回到原出发点,就算旅行成功. 从这个游戏抽象出图论中一种非常重要的Hamilton图,且派生出至今为止仍具研究价值的TSP (Traveling Salesman Problem). 8.3 无向树 树是图论中的重要内容之一(研究独立) (1) 1847年Kirchhoff电路网络; (2) A. Cayley 1857同分异构体. 树分为无向树和有向树. 本节仅讨论无向树. 树在各个领域都有重要应用, 特别是在计算机科学中. 8.4 有向树 在8.3节讨论的是无向树, 本节讨论有向树, 特别是根树的有关内容, 它们在计算机算法设计及程序设计研究中都起着重要作用. 1.有向树的定义 Def 一个有向图, 在不考虑边的方向时是一棵无向树,则该有向图称为有向树(directed tree). 例子见书(P234). 8.5 平面图 本节仅讨论无向图. 对于一个无向图来说，怎样将其图形画出来本身是无关紧要的，只要与原来的图同构皆可. 但有些实际问题要求把图画在一个平面上，同时使得图的边仅仅在节点处才相交. 例如单层印刷电路版、集成电路的布线等问题就需要满足上面的要求. 虽然在现实生活中出现了交通立交桥、多层电路版，但平面图问题仍然是一个基本问题. 例如在上章7.1节提到的“3户3井问题”就是判定一个图是否是平面的问题. 平面图与地图着色问题密切相关. 8.6 平面图的面着色 “四色猜想”(4CC, Four Color Conjecture). 1879年伦敦数学会会员A. B. Kemple给出了四色猜想的第一个证明,10年后P. J. Heawood指出了Kemple证明过程中存在一个不可克服的漏洞,并沿用Kemple的方法证明了五色定理,即五种颜色足够. 8.7 二部图及其匹配 在诸如人员分配、资源分配等问题的讨论中,经常涉及到二部图及其匹配. 本节仅对简单无向图进行讨论. 1. 二部图 Definition V划分为V1和V2, 任意边关联的两个节点中一个在V1中, 一个在V2中. 3.Kuratowski定理 先介绍同胚的定义. Def 若两个图是同构的, 或者通过反复进行以下操作(见图8-42)使得它们同构, 则称这两个图同胚(homeomorphism): Theorem (Kuratowski, 1930) 无向图G是平面图的充要条件是G无同胚于K5和K3,3的子图. 例8-18 证明: Petersen图不是平面图. P246 5(利用Euler公式证明) 4.平面图的对偶图 对平面图G的面的研究可以转换为对其对偶图G*的节点的研究. 根据定义知, 任意平面图的对偶图是平面图且是连通的. 设G是(n, m)平面图,有r个面,则G*是(r, m)平面图,有n个面. 对于连通平面图G, 其对偶图为G*, 这时G*的对偶图G**为本身. 对于非连通平面图G, 可能G与G*不同构. 作业 习题8.5 2—6, 9, 11, 13, 15, 17. 4CC成了会下金蛋的鹅. 在1976年,美国的Kenneth Appel和Wolfgang Haken与John Koch合作, 用了1260个小时证明了“四色猜想”,它开启了定理机器证明的新篇章,四色猜想变成四色定理了. 1999年又给出了一些改进,缩短了计算机的运行时间. 至今为止还没有发现4CC的纯数学证明. 本节主要内容是平面图的面着色问题,顺便介绍任意无向图的节点着色以及边着色等有关内容. 1.平面图的面着色 Def 设G是平面图, 若对G的每个面涂上一种颜色且相邻的面出现不同的颜色, 则称对该平面图的面着色(face coloring), 所需颜色的最少种数称为面着色数(region chromatic number). Figure 8-47(see below) Remark 任意平面图均有无限面. 2.图的节点着色 (1)任意图的节点着色 Def 设G是任意无向图,若对G的每个节点涂上一种颜色且相邻的节点出现不同的颜色,则称对该图的节点着色(