如何学习图论.ppt

1 8 8图着色GraphColoring Dualgraph 对偶图 Eachregionofthemapisrepresentedbyavertex Edgesconnecttwoverticesiftheregionsrepresentedbytheseverticeshaveacommonborder 2 8 8图着色GraphColoring 例 3 8 8图着色GraphColoring 例 4 8 8图着色GraphColoring 设G 是连通平面图G的对偶图 n m r 和n m r分别为G 和G的顶点数 边数和面数 则n rm mr n设G 的顶点vi 位于G的面Ri中 则dG vi deg Ri 5 8 8图着色GraphColoring DEFINITIONAcoloring 着色 ofasimplegraphistheassignmentofacolortoeachvertexofthegraphsothatnotwoadjacentverticesareassignedthesamecolor 6 8 8图着色GraphColoring DEFINITIONThechromaticnumber 色数 ofagraphistheleastnumberofcolorsneededforacoloringofthisgraph denotedby四色定理THEFOURCOLORTHEOREMThechromaticnumberofaplanargraphisnogreaterthanfour 7 8 8图着色GraphColoring 五色定理 Heawood 1890 用 种颜色可以给任何简单连通平面图着色 证明 对结点数v用归纳法a 当v 1 2 3 4 5时显然成立 b 设v k时成立 现考察v k 1已知必存在结点u 使deg u 5 在图G中删去u 得到G u 由归纳假设知G u 可以用5种颜色着色 8 8 8图着色GraphColoring 将u加入到G u 中 若deg u 5 必可对u正常着色 得到一个最多是五色的图G 9 8 8图着色GraphColoring 将u加入到G u 中 若deg u 5 令H为G u 中绿色和蓝色的顶点集合 F为G u 中红色和紫色的顶点集合 10 8 8图着色GraphColoring 若v1与v3属于顶点集H所导出子图的两个不同的连通分支中 将v1所在分图中的蓝色和绿色对调 在u上着绿色 11 8 8图着色GraphColoring 若v1与v3属于顶点集H所导出子图的同一个连通分支中 那么v2与v4将分别属于结点集F所导出子图的两个不同连通分支中 在包含v2的连通分支中将红色和紫色对调 对u着红色 12 8 8图着色GraphColoring Example Trytofindacoloringofthegraph includingtheinfiniteregion 13 韦尔奇 鲍威尔 Welch powell 图着色法 例 用韦尔奇 鲍威尔法对图着色 1 将图中结点数依照度数的递减次序进行排列 上图根据结点度数以递减排列次序为 6 5 5 4 4 4 3 3 8 8图着色GraphColoring 14 2 对5及与5不相邻的结点1着蓝色 3 对3和与3不相邻的结点4 8着红色 对7和与7不相邻的结点2 6着黄色 着色完毕 8 8图着色GraphColoring 15 8 8图着色GraphColoring 16 例 大学中7门考试 以下课程中有公共学生 12 13 14 17 23 24 25 27 34 36 37 45 46 56 57 67 问如何在尽可能少的时间段里安排7门考试并使得没有学生在同一时