第2 编图论第4 章

1第2编图论第4章几种特殊图24.1欧拉图—欧拉图、哈密顿图、平面图、对偶图。•一笔画问题：欧拉通路或欧拉回路。4.1.1欧拉图定义1在无向连通简单图中，通过图中每边一次且仅一次并行遍每个结点的一条通路(回路)，称为该图的一条欧拉通路(回路)。存在欧拉回路的图称为欧拉图。无欧拉通路或欧拉回路欧拉通路欧拉回路3定理1无向连通图G是欧拉图的充分必要条件是G不含奇数度结点。推论非平凡连通图G含有欧拉通路的充分必要条件是G最多有两个奇数度结点。例下列图是否可以一笔画出来.AB×√√4定理2连通有向图G含有欧拉回路的充分必要条件是G中每个结点的入度等于出度；连通有向图G含有欧拉通路的充分必要条件是除两个结点外，其余每个结点的入度等于出度，这两个结点中一个结点的入度比其出度多1，另一个结点的入度比其出度少1。54.2哈密顿图4.2.1哈密顿图定义2经过图中每个结点一次且仅一次的通路(回路)，称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。哈密顿图哈密顿图无哈密顿通路存在哈密顿通路6•哈密顿图的必要条件和充分条件.定理3设无向图G=V,E是哈密顿图，V1是V的任意非空子集，则W(G－V1)≤|V1|.其中:|V1|:V1的元素(结点)个数.G－V1:G删去V1中的点及与这些点关联的所有边后，剩下的图。W(G－V1):G－V1的分枝数。•定理是必要条件，用以否定是哈密顿图。反之，条件成立，哈密顿回路不一定存在。7v1v2v3v4v5G取V1={v1,v3}P(G－V1)=3|V1|=2，由定理3可知不是哈密顿图。v2v4v5G－V18例GBAC取V1={A,B,C},G－V1|V1|=3,P(G－V1)=4,P(G－V1)不≤|V1|.∴G不是哈密顿图。9性质*⑴哈密顿路是简单路.哈密顿路有n－1条边；哈密顿回路有n条边。(设G有n个点)⑵G中某点度为0无哈密顿路和回路。G中某点度为1无哈密顿回路。⑶G中某点度为2与该点相连的两边必在哈密顿回路中。**⑷由⑶判定的必须出现的边已构成回路，而回路外还有其它点无哈密顿回路。10•⑴用来计算边数。•⑷判断无哈密顿回路。比较有用。例2判断有无哈密顿回路由⑷无回路.11定理4设G=V,E为无向简单图,如果G中每对结点度数之和大于等于|V|，则在G中存在一条哈密顿回路。例右图每对结点度数之和=8≥|V(G)|=8,由定理4G是哈密顿图。左图每对结点度数之和=6≥|V(G)|=6，由定理4G是哈密顿图。•是充分条件，不是必要条件。12•定理4的条件不成立，也可能是哈密顿图。例:右图每对结点度数之和=4|V|=6,但G显然是哈密顿图。定理5|V|≥3的完全图kn为哈密顿图；有向图看作无向图时含有子图kn，则有向图中含有哈密顿通路。13例举出满足下列条件具有6个点的图。⑴无哈密顿回路，无欧拉路。⑵有哈密顿回路，无欧拉路。⑶无哈密顿回路，有欧拉路。⑷有哈密顿回路，有欧拉路。⑴⑵⑶⑷14讨论题判断各图是否为哈密顿图，并说明原因，若是哈密顿图，请画出哈密顿回路。×××√√15√√××164.3平面图在印刷电路版等方面有应用.定义3设无向图G=V,E，如果能够把G的所有结点和边画在平面上，使得任何两边除公共结点外没有其它交叉点，则称G为可嵌入平面图，或称G是可平面图，可平面图在平面上的一个嵌入称为平面图。否则称G为非平面图。•有些图虽然有相交的边，如果经改画后可以不相交，这样的图仍是平面图。17例G可改画为所以G是平面图。•二个典型的非平面图.K5K3,318定义4G是一连通平面图，由图的边所包围的并且其内部不包含图的结点和边的区域称为G的一个面，包围该面的各边所组成的回路称为这个面的边界，面边界回路的长度称为该面的次数，记为deg(r)。v1r0v2v3v4v5v6v7v8v9v10r1r2r3r4如图10个结点,13条边,5个面r0,r1,r2,r3,r4,deg(r1)=5,deg(r2)=6,deg(r3)=3,deg(r4)=1,deg(r0)=11,r0为无限面，r1,r2,r3,r4为有限面。19定理6平面图中，所有面的次数之和是其边数的两倍。定理7(欧拉公式)设连通平面图G=V,E，共有v个结点，e条边和r个面，则有v－e+r=2.20定理8G为有v个结点e条边的简单连通平面图，若v≥3，则e≤3v－6.证:∵对任意面ri,都有deg(ri)≥3,因此有r∑deg(ri)≥3r.(r为面数)i=1由定理6可得:2e≥3r.即r≤2e/3.由欧拉公式得出2=v－e+r≤v－e+2e/3.2≤v－e/3,6≤3v－e∴e≤3v－6.■•用以判断非平面图(必要条件)。21例证明K5不是平面图。K5证:∵e=10,v=5,3v－6=9.即e=10不≤3v－6=9.由定理8得K5不是平面图。K3,3例由定理8不能判断K3,3是非平面图。∵e=9,v=6,3v－6=12.即e≤3v－6.但是由其它方法能判断K3,3不是平面图。■22定义5如果两个图G1和G2同构，或者通过反复插入或去掉2度结点后，G1和G2同构，则称G1和G2是2度结点内同构的，也称G1和G2是同胚的。定理9(库拉托夫斯基定理)一个图是平面图的充分必要条件是它不含与K3,3或K5在2度结点内同构的子图。234.4对偶图与着色最早起源于对地图的着色，相邻国家着不同的颜色，最少需用多少种颜色？对图形着色可分为对结点着色、对边着色和对面着色。后两者可转化为对结点着色。如果图G着色时采用了n种颜色，就称G为n-色的，n称为G的着色数，记为(G)。24对图G结点着色的韦尔奇鲍威尔法(1)将G中的结点按度数递减的次序排列；(2)用第一种颜色对第一点着色，并按排列次序对与第一点不相邻的每一点着同样的颜色；(3)用第二种颜色对尚未着色点重复(2)，再用第三种颜色对尚未着色点重复(2)，直到所有的点都着上颜色为止。25例1试用韦尔奇鲍威尔法对右图进行着色。HAGBCDEF解：(1)按度数递减的次序排列各点CABFGHDE54444322(2)用颜色●对C和不相邻的A,G着色；(3)用颜色●对B和不相邻的D,E,H着色；(4)用颜色●对F着色。所以图G是3色的，(G)=3。26定理10对于完全图kn，有(kn)=n。证：在kn找不到不相邻的两个结点，所以每一个结点要占用一种颜色。■定理11连通平面图G=V,E至少有三个结点，则必有一点uV，使得deg(u)≤5.证：设|V|=v,|E|=e，若G的每个结点都有deg(u)≥6，则由握手定理，2e=deg(u)≥6v，得e≥3v3v－6，与定理8矛盾。■定理12任意平面图最多是5-色的。27•利用对偶图可以把对面着色的问题转化为对点着色的问题。定义6给定平面图G=V,E,F1,F2,...,Fr为G的面，构造图G*=V*,E*满足：1)每一面Fi内部画一结点vi*V*；2)若两面Fi,Fj有公共边ek,作边ek*=(vi*,vj*)且与ek相交；3)当且仅当ek只是面Fi的边界时，vi*存在一个环ek*与ek相交。则称图G*为G的对偶图。28黄色的图即为原图的对偶图。29•若G*是G的对偶图，则G也是G*的对偶图。•一个连通的平面图的对偶图也是平面图。•G的面着色问题转化成了G*点着色问题。定义7如果平面图G的对偶图G*同构于G，则称G为自对偶图。例如：30可见原图为自对偶图。