第五章第五章 平面图平面图5.1 5.1 平面图与平面图与EulerEuler公式公式 一、平面图一、平面图定定义义5.1.1 5.1.1 若若一一个个图图能能画画在在平平面面上上使使它它的的边边互互不不相相交交（除除在在顶顶点点处处），则则称称该该图图为为平平面面图图，或或称该图能嵌入平面。称该图能嵌入平面。 例例如如下下图图（a a）是是平平面面图图G G，它它能能嵌嵌入入平平面面上上，如图（如图（b b）所示的图是）所示的图是G G的平面嵌入。的平面嵌入。 并非所有的图都能嵌入并非所有的图都能嵌入平面平面! ! 下下图（图（a a）表示的就是非平面图，这个图对应）表示的就是非平面图，这个图对应于一个有名的问题于一个有名的问题公用事业问题。设有三公用事业问题。设有三座房子座房子a a、b b、c c和三个公共设施和三个公共设施d d、e e、f f，能否，能否使每座房子与每个公共设施之间均有道路连接使每座房子与每个公共设施之间均有道路连接而无交叉。实践证明这是做不到的，图（而无交叉。实践证明这是做不到的，图（b b）说明（说明（a a）无法嵌入平面，此图为二分图）无法嵌入平面，此图为二分图K K3 3，3 3，它是一个非平面图。它是一个非平面图。 还有一个重要的非平面图，下图（还有一个重要的非平面图，下图（c c）、（）、（d d）所示，它就是完全图所示，它就是完全图K K5 5。K K3 3，3 3和和K K5 5又称为库拉又称为库拉托斯基图，它们是波兰数学家库拉托斯基托斯基图，它们是波兰数学家库拉托斯基（KuratowskyKuratowsky）发现的典型的非平面图）发现的典型的非平面图。 定定义义5.1.2 5.1.2 平平面面图图G G嵌嵌入入平平面面后后将将平平面面划划分分成成若若干干个个连连通通的的区区域域，每每一一个个区区域域称称为为G G的的一一个个面面，其其中中面面积积无无限限的的区区域域称称为为外外部部面面或或无无限限面面（常常记记为为R R0 0），面面积积有有限限的的称称为为内内部部面面或或有有限限面，记作面，记作R Ri i（i i=1=1，2 2，n n）；）； 包包围围每每个个面面的的所所有有边边所所构构成成的的回回路路称称该该面面的的边边界界，边边界界的的长长度度称称该该面面的的次次数数，面面R Ri i的的次次数数记记作作dedeg g（R Ri i）。）。 例如，下图所示平面图例如，下图所示平面图G G有四个面，有四个面，dedeg g（R R1 1）=3=3， dedeg g（R R2 2）=3=3，dedeg g（R R3 3）=5=5，dedeg g（R R0 0）=9=9。 定定义义5.1.3 5.1.3 设设G G为为一一个个简简单单平平面面图图，如如果果在在G G的的任任意意两两个个不不相相邻邻的的顶顶点点间间再再加加一一条条边边，所所得得图图为为非非平平面面图图，则则称称G G为为极极大大平平面图。面图。 例例如如，完完全全图图K Kn n当当n n44是是都都是是极极大大平平面面图图。K K5 5在在任意删去一条边后，为极大平面图任意删去一条边后，为极大平面图。 极极大平面图有如下的一些性质：大平面图有如下的一些性质： （1 1）极大平面图均是连通图。）极大平面图均是连通图。 （2 2）极大平面图中（）极大平面图中（n n33），不含割点和桥。），不含割点和桥。（3 3）任何）任何n n（n n33）阶极大平面图，每个面（包）阶极大平面图，每个面（包括无限面）的次数均为括无限面）的次数均为3 3，反之亦然。，反之亦然。（4 4）最小（顶点数最少）的极大平面图是）最小（顶点数最少）的极大平面图是K K5 5。 定定义义5.1.4 5.1.4 设设G G是是非非平平面面图图，若若在在G G中中任任意意删删去去一一条条边边后后，所所得得图图为为平平面面图图，则则称称G G是是极极小小非非平面图平面图。 例如例如K K5 5和和K K3 3，3 3均是极小非平面图。均是极小非平面图。 定定理理5.1.1 5.1.1 在在一一个个平平面面图图G G中中，所所有有面面的的次次数数之之和为边数的二倍，即和为边数的二倍，即证证明明：对对于于G G中中的的每每一一条条边边e e，e e或或是是两两个个面面的的公公共共边边，或或是是在在一一个个面面中中为为悬悬挂挂边边被被作作为为边边界界计计算算两次，故定理成立。证毕两次，故定理成立。证毕 其中，其中，r r为为G G的面数，的面数，m m为边数。为边数。 二、二、EulerEuler公式公式 定理定理5.1.2 5.1.2 设连通平面图设连通平面图G G有有n n个顶点，个顶点，m m条边和条边和r r个面，个面， 则有则有 n n- -m m+ +r r=2 =2 EulerEuler公式公式 证明：施归纳于证明：施归纳于G G的边数的边数m m。 m m=0=0时，时，G G为平凡图，为平凡图，n n=1=1，r r=1=1，公式成立。，公式成立。 设设m m= =k k-1-1（k k11）时公式成立，现在考虑）时公式成立，现在考虑m m= =k k时的情况。时的情况。 因为在连通图上增加一条边仍为连通图，则有三种情因为在连通图上增加一条边仍为连通图，则有三种情 况：况： （1 1）所所增增边边为为悬悬挂挂边边，此此时时G G的的面面数数不不变变，顶顶点数增点数增1 1，公式成立。，公式成立。 （2 2）在在图图的的任任意意两两个个不不相相邻邻点点间间增增加加一一条条边边，此此时时G G的的面面数数增增1 1，边边数数增增1 1，但但顶顶点点数数不不变变，公式成立。公式成立。 （3 3）所所增增边边为为一一个个环环，此此时时G G的的面面数数增增1 1，边边数数增增1 1，但顶点数不变，公式成立。，但顶点数不变，公式成立。 定理定理5.1.3 5.1.3 设设G G是连通的（是连通的（n n，m m）平面图且每个）平面图且每个面的次数至少为面的次数至少为l l（l l33），则），则证明：由定理证明：由定理5.1.15.1.1知知 ( (r r为为G G的的面面数数) )再由由EulerEuler公式公式 n n- -m m+ +r r=2=2于是有于是有故故 推推论论1 1 设设G G是是n n阶阶、边边数数为为m m的的连连通通平平面面简简单单图图（n n33），则），则 m m33n n-6-6证证明明：由由于于G G是是n n33的的连连通通平平面面简简单单图图，所所以以G G的的每每个个面面至至少少由由3 3条条边边围围成成，即即l l33，代代入入定定理理5.1.35.1.3，得，得 m m33n n-6 -6 证毕证毕 推论推论2 2 极大连通平面图的边数极大连通平面图的边数m m=3=3n n-6-6。 证证明明：因因为为极极大大平平面面图图的的每每一一个个面面的的次次数数均均是是3 3，所以，所以3 3r r=2=2m m，代入，代入EulerEuler公式有公式有 m m=3=3n n-6 -6 证毕证毕 推论推论3 3 若连通平面简单图若连通平面简单图G G不以不以K K3 3为子图，则为子图，则 m m22n n-4-4。证证明明：由由于于G G中中不不含含K K3 3，所所以以G G的的每每个个面面至至少少由由4 4条条边围成，即边围成，即l l44，代入定理，代入定理5.1.35.1.3，得，得 m m22n n-4 -4 证毕证毕 推论推论4 4 K K5 5和和K K3 3，3 3是非平面图。是非平面图。证证明明：假假设设K K5 5是是平平面面图图，由由推推论论1 1可可知知应应有有m m33n n-6-6，而当，而当n n=5=5，m m=10=10时，时， 10 310 3 5-6=95-6=9 这是不可能的，所以这是不可能的，所以K K5 5是非平面图。是非平面图。 假假设设K K3 3，3 3是是平平面面图图，因因其其不不含含子子图图K K3 3，由由推推论论2 2可可知知应应有有m m22n n-4 -4 ，当当n n=6=6，m m=9=9时，时， 9 29 2 6-4=86-4=8 这是不可能的，所以这是不可能的，所以K K3 3，3 3是非平面图。是非平面图。 证毕证毕 定定理理5.1.4 5.1.4 在在平平面面简简单单图图G G中中至至少少有有一一个个顶顶点点v v0 0，d d（v v0 0）5 5。 证证明明：不不妨妨设设G G是是连连通通的的，否否则则就就其其一一个个连连通通分支讨论再推广至全图。用反证法证明。分支讨论再推广至全图。用反证法证明。 假假设设一一个个平平面面简简单单图图的的所所有有顶顶点点度度数数均均大大于于5 5，又由欧拉公式推论，又由欧拉公式推论1 1知知3 3n n-6-6m m，所以，所以 这这是是不不可可能能的的。因因此此平平面面简简单单图图中中至至少少有有一一个个顶点顶点v v0 0，其度数，其度数d d（v v0 0）5 5。 证毕证毕 找找出出一一个个图图是是平平面面图图的的充充分分必必要要条条件件的的研研究究曾曾经经持持续续了了几几十十年年，直直到到19301930年年库库拉拉托托斯斯基基给给出出了了平平面面图图的的一一个个非非常常简简洁的特征，先介绍一些预备知识。洁的特征，先介绍一些预备知识。 5.2 5.2 平面图的判定平面图的判定 Kuratowsky定理定理?在一个无向图在一个无向图G G的边上，插入一个新的度数为的边上，插入一个新的度数为2 2的顶点，的顶点，使一条边分成两条边，或者对于关联同一个度数为使一条边分成两条边，或者对于关联同一个度数为2 2的顶点的两条边，去掉这个的顶点的两条边，去掉这个2 2度顶点，使两条边变成度顶点，使两条边变成一条边，如下面图（一条边，如下面图（a a）、（）、（b b）所示，这些都不会改）所示，这些都不会改变图原有的平面性，如图所表示的称为变图原有的平面性，如图所表示的称为“图的同胚图的同胚”。 定定义义5.2.1 5.2.1 如如果果两两个个图图G G1 1和和G G2 2同同构构，或或者者通通过过反反复复插插入入或或删删除除度度数数为为2 2的的顶顶点点后后同同构构，则则称称G G1 1和和G G2 2同胚。同胚。 由由于于同同胚胚的的两两个个图图具具有有相相同同的的平平面面性性，而而K K5 5和和K K3 3，3 3是典型的非平面图，因此有：是典型的非平面图，因此有：定理定理5.2.15.2.1（KuratowskyKuratowsky定理）定理）一个图是平面图一个图是平面图 的充分必要条件是它不含与的充分必要条件是它不含与K K5 5或或K K3 3，3 3同胚的子图。同胚的子图。 证明略。证明略。 例例5.2.1 5.2.1 证证明明下下图图中中的的（a a）和和（d d）不不是是平面图。平面图。 解：图解：图( (a a）是著名的彼得森）是著名的彼得森（PertersenPertersen）图，去掉其中的两条边后）图，去掉其中的两条边后得子图（得子图（b b），该子图同胚于），该子图同胚于K K3 3，3 3（c c）。）。因此彼得森图不是平面图。因此彼得森图不是平面图。 图（图（d d）图中含有子图（）图中含有子图（e e），图（），图（e e）图同构于图同构于K K3 3，3 3 （f f）。）。 注注：库库拉拉托托斯斯基基定定理理虽虽然然简简单单漂漂亮亮，但但实实现现起起来来并并不不容容易易，特特别别是是顶顶点点数数较较多多的的时时候候，还还有有许许多多这这方方面面的的研研究究工工作作要要做。做。5.35.3 对偶图对偶图 平平面面图图有有一一个个很很重重要要的的特特性性，任任何何平平面面图图都都有有一一个个与与之之对对应应的的平平面面图图，称称为为它它的的对对偶偶图图。下下面面提提到到的的平平面面图图均均以以它它的平面嵌入表示。的平面嵌入表示。 定定义义5.3.1 5.3.1 设设平平面面图图G G= =V V, ,E E有有r r个个面面R R1 1，R R2 2，R Rr r，则则用用下下面面方方法法构构造造的的图图G G*=*=V V*,*,E E* * 称称 为为G G的的 对对 偶偶 图图 ： （1 1）R Ri iG G，在在R Ri i内内取取一一顶顶点点v v* *i iV V* *，i i=1=1，2 2，r r。 （2 2）e eE E。 若若e e是是G G中中两两个个不不同同面面R Ri i和和R Rj j的的公公共共边边，则则在在G G* *中中画画一一条条与与e e交交叉叉的的边边（v v* *i i，v v* *j j）；）； 若若e e是是一一个个面面R Ri i内内的的边边（即即RiRi是是桥桥），则则在在G G* *中中画画一一条条与与e e交交叉叉的的环环（v v* *i i，v v* *i i）。）。 例例如如，下下图图（a a）和和（b b）中中，G G* *是是G G的的对对偶偶图图，G G的的边边用用实实线线表表示示，G G* *的的边边用用虚虚线表示，顶点用实心点表示。线表示，顶点用实心点表示。 定定义义5.3.2 5.3.2 若若平平面面图图G G与与其其对对偶偶图图G G* *同同构构，则称则称G G是自对偶图。是自对偶图。 例如例如，完全图，完全图K K4 4是是一个自对偶图。一个自对偶图。 定理定理5.3.1 5.3.1 设设G G* *是连通平面图是连通平面图G G的对偶图，的对偶图，n n* *，m m* *，r r* *和和n n，m m，r r分别是分别是G G* *和和G G的顶的顶点数，边数和面数，则点数，边数和面数，则n n*=*=r r，m m*=*=m m，r r*=*=n n，且，且d d（v v* *i i）= =dedeg g（R Ri i），），i i=1=1，2 2，r r。 证证明明: : 由由定定义义5.3.15.3.1对对偶偶图图的的构构造造过过程程可可知知，n n*=*=r r，m m*=*=m m和和d d（v vi i）= =dedeg g（R Ri i）显显然然成成立立，下下证证r r*=*=n n。因因为为G G和和G G* *均均是是连连通通的的平平面面图图，所所以以由欧拉公式有由欧拉公式有 n n- -m m+ +r r=2=2 n n*-*-m m*+*+r r*=2 *=2 由由n n*=*=r r，m m*=*=m m可得可得r r*=*=n n。证毕。证毕 由由于于平平面面图图G G的的对对偶偶图图G G* *也也是是平平面面图图，因因此此同同样样可可对对G G* *求求对对偶偶图图，记记作作G G*，如如果果G G是是连连通通的，则的，则G G*与与G G之间有如下关系。之间有如下关系。 定定理理5.3.2 5.3.2 G G是是连连通通平平面面图图当当且且仅仅当当G G*同同构于构于G G。 证明证明略。略。 由由对对偶偶图图的的构构造造过过程程可可知知，平平面面图图G G的的任任何何两两个个对对偶偶图图必必同同构构。但但是是若若平平面面图图G G1 1和和G G2 2是是同同构构的的，其其对对偶偶图图G G* *1 1和和G G* *2 2未未必必同同构构。如如图图中中两两个个平平面面图图G G1 1和和G G2 2是是同同构构的的，但但由由于于G G1 1（如如图图（a a）所所示示）中中有有一一个个面面次次数数为为5 5，而而G G2 2（如如图图（b b）所所示示）中中没有这样的面，因此没有这样的面，因此G G1 1和和G G2 2不会同构。不会同构。 5.4 5.4 平面图着色平面图着色问题问题 在在地地图图上上，相相邻邻国国家家涂涂不不同同的的颜颜色色，最最少少需需要要多多少少种种颜颜色色？100100多多年年前前，有有人人提提出出了了“四四色色猜猜想想”，即即只只用用四四种种颜颜色色就就能能做做到到，但但一一直直无无法法证证明明，直直到到19761976年年美美国国数数学学家家才才用用电电子子计计算算机机证证明明了了这这一猜想。一猜想。 地地图图着着色色自自然然是是对对平平面面图图的的面面着着色色，利利用用对对偶偶图图，可可将将其其转转化化为为相相对对简简单单的的顶顶点点着着色色问问题题，即即对对图图中中相相邻邻的的顶顶点点涂涂不同的颜色。不同的颜色。 定定义义5.4.1 5.4.1 设设G G是是一一个个无无自自环环的的图图，给给G G的的每每个个顶顶点点指指定定一一种种颜颜色色，使使相相邻邻顶顶点点颜颜色色不不同同，称称为为对对G G的的一一个个正正常常着着色色。图图G G的的顶顶点点可可用用k k种种颜颜色色正正常常着着色色，称称G G是是kk可着色的。可着色的。 使使G G是是k k可可着着色色的的数数k k的的最最小小值值称称为为G G的的色色数数，记记作作（G G）。如如果果（G G）= =k k，则称则称G G是是kk色的。色的。 设设G G无无自自环环且且连连通通，如如果果有有多多重重边边，则则可可删删去去多多重重边边，用用一一条条边边代代替替，因因此此下下面面考考虑虑的的都都是是连连通通简简单单图图。有有几几类类图图的的色色数数是是很很容容易易确确定定的的，即：即： 定理定理5.4.1 5.4.1 （1 1）G G是零图当且仅当是零图当且仅当（G G）=1=1。 （2 2）对于完全图）对于完全图K Kn n，有，有（K Kn n）= =n n，而，而（ ）=1=1。 （3 3）对对于于n n个个顶顶点点构构成成的的回回路路C Cn n，当当n n为为偶偶数数时时，（C Cn n）=2=2；当；当n n为奇数时，为奇数时，（C Cn n）=3=3。 （4 4）对于顶点数大于）对于顶点数大于1 1的树的树T T，有，有（T T）=2=2。 到到现现在在还还没没有有一一个个简简单单的的方方法法可可以以确确定定任任一一图图G G是是nn色色 的的 。 但但 韦韦 尔尔 奇奇 鲍鲍 威威 尔尔（WelchPowellWelchPowell）给给出出了了一一种种对对图图的的着着色色方方法法，步骤如下：步骤如下： （1 1）将图）将图G G中的顶点按度数递减次序排列。中的顶点按度数递减次序排列。 （2 2）用用第第一一种种颜颜色色对对第第一一顶顶点点着着色色，并并将将与与已着色顶点不邻接的顶点也着第一种颜色。已着色顶点不邻接的顶点也着第一种颜色。 （3 3）按排列次序用第二种颜色对未着色的顶）按排列次序用第二种颜色对未着色的顶点重复（点重复（2 2）。用第三种颜色继续以上做法，）。用第三种颜色继续以上做法，直到所有的顶点均着上色为止。直到所有的顶点均着上色为止。 例例5.4.1 5.4.1 用韦尔奇用韦尔奇鲍威尔法鲍威尔法对下图进行图对下图进行图着色。着色。（1 1）各各顶顶点点按按度度数数递递减减次次序序排排列列：c c，a a，e e，f f，b b，h h，g g，d d。（2 2）对）对c c和与和与c c不邻接的不邻接的e e，b b着第一种颜色。着第一种颜色。（3 3）对）对a a和与和与a a不邻接的不邻接的g g，d d着第二种颜色。着第二种颜色。（4 4）对）对f f和与和与f f不邻接的不邻接的h h着第三种颜色。着第三种颜色。 定定理理5.4.1 5.4.1 如如果果图图G G的的顶顶点点的的度度数数最最大大的的为为（G G），则），则（G G）1+1+（G G）。）。 证明证明: :施施归纳于归纳于G G的顶点度数。的顶点度数。 当当n n=2=2时时，G G有有一一条条边边，（G G）=1=1，G G是是2 2可可着着色色的的，所所以以（G G）1+1+（G G）。假假设设对对于于n n-1-1个顶点的图，结论成立。个顶点的图，结论成立。 现现假假设设G G有有n n个个顶顶点点，顶顶点点的的最最大大度度数数为为（G G），如如果果删删去去任任一一顶顶点点v v及及其其关关联联的的边边，得得到到n n-1-1个个顶顶点点的的图图，它它的的最最大大度度数数至至多多是是（G G），由由归归纳纳假假设设，该该图图是是1+1+（G G）可可着着色色的的，再再将将v v及及其其关关联联的的边边加加到到该该图图上上，使使其其还还原原成成图图G G，顶顶点点v v的的度度数数至至多多是是（G G），v v的的相相邻邻点点最最多多着着 上上 （G G） 种种 颜颜 色色 ， 然然 后后v v着着 上上 第第1+1+（G G）种种颜颜色色，因因此此G G是是1+1+（G G）可着色的，故可着色的，故 （G G）1+1+（G G）。证毕）。证毕 定理定理5.4.15.4.1所所给出的色数的上界是很弱的，给出的色数的上界是很弱的，例如树例如树T T，（T T）=2=2，而，而（T T）可以很）可以很大。布鲁克斯（大。布鲁克斯（B Br rooook ks s）在）在19411941年证明年证明了这样的结果，使了这样的结果，使 （G G）=1+=1+（G G）的图只有两类：或）的图只有两类：或是奇回路，或是完全图。是奇回路，或是完全图。定理定理5.4.2 5.4.2 任何平面图是任何平面图是55可着色的。可着色的。 证证明明: :不不妨妨设设G G是是简简单单平平面面图图。施施归归纳纳于于G G的顶点数的顶点数n n。当。当n n55时结论显然成立。时结论显然成立。 假设对所有假设对所有n n-1-1个顶点的平面图是个顶点的平面图是5 5可可着色的着色的。 现现考虑有考虑有n n个顶点的平面图个顶点的平面图G G，由，由定理定理5.1.45.1.4可知，在可知，在G G中存在着顶点中存在着顶点v v0 0，d d（v v0 0）5 5。由归纳假设，。由归纳假设，G G- -v v0 0是是5-5-可着色的，可着色的，在给定了在给定了G G- -v v0 0的一种着色后，的一种着色后，将将v v0 0及其及其关关联的边加到原图中，得到联的边加到原图中，得到G G，分两种情况，分两种情况考虑：考虑： （1 1）如如果果d d（v v0 0）5 5，则则v v0 0的的相相邻邻点点已已着着上上的的颜颜色色小小于于等等于于4 4种种，所所以以v v0 0可可以以着着另另一一种种颜颜色色，是是G G是是5 5可着色的。可着色的。 （2 2）如如果果d d（v v0 0）=5=5，则则将将v v0 0的的邻邻接接点点依依次次记记为为v v1 1，v v2 2，v v5 5，并并且且对对应应v vi i着着第第i i色色，如如下下图图（a a）所示。）所示。 设设H H1313为为G G- -v v0 0的的一一个个子子图图，它它是是由由着着色色1 1和和3 3的的顶顶点点集集导导出出的的子子图图。如如果果v v1 1和和v v3 3属属于于H H1313的的不不同同分分支支，将将v v1 1所所在在分分支支中中着着色色1 1的的顶顶点点与与着着色色3 3的的顶顶点点颜颜色色对对换换，这这时时v v1 1着着色色3 3，这这并并不不影影响响G G- -v v0 0的的正正常常着着色色。然然后后将将v v0 0着色着色1 1，因此，因此G G是是5 5可着色的。可着色的。 如如果果v v1 1和和v v3 3属属于于H H1313的的同同一一分分支支，则则在在G G中中存存在在一一条条从从v v1 1到到v v3 3的的路路，它它的的所所有有顶顶点点着着色色1 1或或3 3。这这条条路路与与路路v v1 1v v0 0v v3 3一一起起构构成成一一条条回回路路，如如图图（b b）所所示示。它它或或者者把把v v2 2围围在在它它里里面面，或或者者同同时时把把v v4 4和和v v5 5围围在在它它里里面面。由由于于G G是是平平面面图图，在在上上面面任任一一种种情情况况下下，都都不不存存在在连连接接v v2 2和和v v4 4并并且且顶顶点点着着色色2 2或或4 4的的一条路。一条路。 现现在在设设H H2424为为G G- -v v0 0的的另另一一个个子子图图，它它是是由由着着色色2 2和和4 4的的顶顶点点导导出出的的子子图图，则则v v2 2和和v v4 4属属于于H H2424的的不不同同分分支支。于于是是在在v v2 2所所在在分分支支中中将将着着色色2 2的的顶顶点点和和着着色色4 4的的顶顶点点颜颜色色对对换换，v v2 2着着色色4 4，这这样样导导出出了了G G- -v v0 0的的另另一一种种正正常常着着色色，然然后后在在v v0 0着着色色2 2，同同样样可可得得G G是是5 5可着色的可着色的。 证毕证毕 上上面面结结果果称称为为五五色色定定理理, ,那那么么四四色色定定理理哪哪? ? I have to put all these into