离散数学图论省公共课一等奖全国赛课获奖课件.pptx

第七章第七章图论图论7.1 图基本概念7.2 路与回路7.3 图矩阵表示7.4 欧拉图和汉密尔顿图7.5 平面图7.6 对偶图与着色7.7 树与生成树1第1页第七章 图论 教学目标及要求：教学目标及要求：深刻了解和掌握图相关概念和表示。教学内容：教学内容：图基本概念、路与回路、图矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树。教学重点：教学重点：图、路、图矩阵表示、平面图、树与生成树。教学难点：教学难点：树与生成树。2第2页图论图论图论是近年来发展快速而又应用广泛一门新兴学图论是近年来发展快速而又应用广泛一门新兴学科。科。图论最早起源于一些数学游戏难题研究。如：哥图论最早起源于一些数学游戏难题研究。如：哥尼斯堡七桥问题、迷宫问题等。尼斯堡七桥问题、迷宫问题等。1847年，克希霍夫用图论分析电路网络，最早将年，克希霍夫用图论分析电路网络，最早将图论应用于工程科学。图论应用于工程科学。图论内容十分丰富图论内容十分丰富,它是一门应用性很强学科。它是一门应用性很强学科。计算机科学、网络理论、信息论、运筹学、语言计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具学、物理、化学等都以图作为工具,来处理实际来处理实际问题和理论问题。问题和理论问题。3第3页图论图论现实世界中许多状态是由图形来描述现实世界中许多状态是由图形来描述,我们用点表示我们用点表示事物事物,用点之间是否有连线表示事物之间是否有某种用点之间是否有连线表示事物之间是否有某种关系关系,于是点以及点之间若干条连线就组成了图。于是点以及点之间若干条连线就组成了图。当我们研究对象能够被抽象为离散元素集合和集合当我们研究对象能够被抽象为离散元素集合和集合上二元关系时上二元关系时,用关系图进行表示和处理是很方便。用关系图进行表示和处理是很方便。图可分为图可分为有限图有限图和无限图两类和无限图两类,本书只研究有限图本书只研究有限图,即即顶点和边都是有限顶点和边都是有限集合。集合。4第4页7.1 图基本概念图基本概念离散数学研究图是不一样于几何图形、机械图形离散数学研究图是不一样于几何图形、机械图形另一个数学结构另一个数学结构,不关心不关心图中图中顶点位置顶点位置、边长短和边长短和形状形状,只关心只关心顶点与边联结关系。顶点与边联结关系。以下列图（以下列图（a）和（）和（b）abcde1e2e6e4e3e5（a）abcde1e6e2e4e3e5（b）abcde1e2e6e4e3e55第5页（1）定义定义:一个图一个图G是一个三元组是一个三元组,其其中中V(G)为顶点集合为顶点集合,E(G)是边集合，是边集合，G是从边集是从边集E到到结点偶对集合上函数。结点偶对集合上函数。讨论定义：讨论定义：(a)V(G)=V1，V2，Vn为有限非空集合为有限非空集合,Vi称为结点称为结点,简称简称V是点集。是点集。(b)E(G)=e1，em为有限边集合为有限边集合,ei称为边，称为边，每个每个e ei i是连结是连结V中某两个顶点中某两个顶点,称称E E为边集。为边集。(c)可用可用e或或e(vi,vj)，来表示图边，这么，来表示图边，这么可把图简化成：可把图简化成：。7.1 图基本概念图基本概念6第6页（2）每一条边都是无向边图称无向图。）每一条边都是无向边图称无向图。每一条边都是有向边图称有向图。每一条边都是有向边图称有向图。bcdabcda假如图假如图G中现有没有向边中现有没有向边,又有有向边又有有向边,则称该图为混合图。本课程不讨论混则称该图为混合图。本课程不讨论混合图。合图。7.1 图基本概念图基本概念7第7页例：对有向图可表示为：例：对有向图可表示为：，其中其中a、b、c、d,则：，则：，=a，b，c，d，,7.1 图基本概念图基本概念8第8页（3）在一个图中，若两个结点有一条有向边或者一）在一个图中，若两个结点有一条有向边或者一条无向边关联条无向边关联,则这两个结点成为则这两个结点成为邻接点邻接点。孤立结点：孤立结点：在一个图中不与任何结点相邻接结点，在一个图中不与任何结点相邻接结点，称为孤立结点。以下列图中结点称为孤立结点。以下列图中结点v5。（4）零图：零图：仅由孤立结点组成图称为零图。仅由孤立结点组成图称为零图。v1v2v3v4v57.1 图基本概念图基本概念9第9页（5）平凡图：平凡图：仅由一个孤立结点组成图称为平凡图。仅由一个孤立结点组成图称为平凡图。邻接边：邻接边：关联于同一结点两条边称为邻接边。关联于同一结点两条边称为邻接边。（6）自回路（环）：自回路（环）：关联于同一结点一条边称为自关联于同一结点一条边称为自回路。回路。以下列图，中（c，c）是环 acba7.1 图基本概念图基本概念10第10页（7）度数：度数：在图在图G=中，与结点中，与结点v（v V）关联边数，称为该结点度数，记作关联边数，称为该结点度数，记作deg（v）。）。约定：约定：每个环在其对应结点上度数增加每个环在其对应结点上度数增加2。ABCED7.1 图基本概念图基本概念最大度最大度,记为：记为：（G G）最小度最小度,记为：记为：（G G）11第11页定理定理1：每个图中，结点度数总和等于边数两倍。即每个图中，结点度数总和等于边数两倍。即证：证：每条边必关联两个结点，而一条边给于关联每每条边必关联两个结点，而一条边给于关联每个结点度数为个结点度数为1。故上述定理成立。故上述定理成立。7.1 图基本概念图基本概念12第12页定理定理2：在任何图中，度数为奇数结点必定是偶数个。在任何图中，度数为奇数结点必定是偶数个。证：设证：设V1和和 V2分别是分别是G中奇数度数和偶数度数结点集，中奇数度数和偶数度数结点集，则由上述定理有：则由上述定理有：因为因为 是偶数之和，必为偶数，而是偶数之和，必为偶数，而 是偶数。故是偶数。故得是得是 偶数，即偶数，即 是偶数。是偶数。7.1 图基本概念图基本概念13第13页（8）入度，出度：）入度，出度：在有向图中，射入一个结点边数称在有向图中，射入一个结点边数称为该结点入度。由一个结点射出边数称为该结点出为该结点入度。由一个结点射出边数称为该结点出度。度。结点出度与入度结点出度与入度和和是该结点是该结点度数度数。定理：定理：在任何有向图中，全部结点入度和等于全部在任何有向图中，全部结点入度和等于全部结点出度之和。结点出度之和。7.1 图基本概念图基本概念14第14页bcda证：证：每一条有向边必对应一个入度和出度，若一个结点含每一条有向边必对应一个入度和出度，若一个结点含有一个入度或出度，则必关联一条有向边，所以，有向图中有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度和等于边数，各结点出度和也是等于边数，所以，各结点入度和等于边数，各结点出度和也是等于边数，所以，任何有向图中，入度之和等于出度和。任何有向图中，入度之和等于出度和。7.1 图基本概念图基本概念15第15页（9）连接于同一对结点间多条边称为是平行。连接于同一对结点间多条边称为是平行。定义：定义：含有平行边任何一个图称为多重图。含有平行边任何一个图称为多重图。不含有平行边和环图称作简单图。不含有平行边和环图称作简单图。（10）完全图：）完全图：简单图简单图G=中，若每一对结点间都有边中，若每一对结点间都有边相连，则称该图为完全图。相连，则称该图为完全图。a abc（a）a abc（b）（c）a abcd7.1 图基本概念图基本概念16第16页定理定理4：n个结点无向完全图边数为：个结点无向完全图边数为：证实：在有证实：在有n个结点无向完全图中，任意两点间都有个结点无向完全图中，任意两点间都有边连接，边连接，n个结点中任意取两点组合为：个结点中任意取两点组合为：故有故有n个结点无向完全图边数为个结点无向完全图边数为7.1 图基本概念图基本概念17第17页（11）补图：）补图：给定一个图给定一个图G，由，由G中全部结点和全部中全部结点和全部能使能使G成为完全图添加边组成图，称为成为完全图添加边组成图，称为G相对于完相对于完全图补图，或简称为全图补图，或简称为G补图。记作。补图。记作。以下列图，（以下列图，（a）和（）和（b）互为补图。）互为补图。（a）（b）7.1 图基本概念图基本概念18第18页（12）子子图图：设设图图G=，假假如如有有图图G=，且，且EE，VV，则称，则称 G 为为 G 子图。子图。以下列图，（以下列图，（b）、（）、（c）都是（）都是（a）子图。）子图。（a）bcdhgafe（b）bcdhgfe（c）bcdhgaf7.1 图基本概念图基本概念19第19页（13）生生成成子子图图：假假如如G子子图图包包含含G全全部部结结点点，则则称称该子图为该子图为G生成子图。生成子图。以下列图，（以下列图，（b）、（）、（c）都是（）都是（a）生成子图。）生成子图。（a）（c）7.1 图基本概念图基本概念20第20页（14）定义：）定义：设图设图G=及图及图G=，假如存在一一对应映射，假如存在一一对应映射g：viv i且且e=（vi，vj）是）是G一条边，当且仅当一条边，当且仅当e=（g（vi），），g（vj）是）是 G 一条边，则称一条边，则称G与与G 同构，记作同构，记作G G。两个图同构充要条件是：两个图结点和边分别存在着两个图同构充要条件是：两个图结点和边分别存在着一一对应关系，且保持关联关系。一一对应关系，且保持关联关系。7.1 图基本概念图基本概念21第21页dbea（a）u3u4u2u1（b）存在着一一对应映射存在着一一对应映射g：g(a)=u3，g(b)=u1，g(c)=u4，g(d)=u2，且有：且有：,分分别与别与,一一对应一一对应7.1 图基本概念图基本概念22第22页两图同构一些两图同构一些必要条件必要条件：（1）结点数目相同。）结点数目相同。（2）边数相等。）边数相等。（3）度数相同结点数目相同）度数相同结点数目相同这几个条件不是两个图同构充分条件。下两图，满足上这几个条件不是两个图同构充分条件。下两图，满足上述三个条件，但并不一样构述三个条件，但并不一样构7.1 图基本概念图基本概念23第23页7.2 路与回路路与回路定义：在图定义：在图G=中，设中，设v0，v1，vnV,e1,e2 en E，其中其中ei是关联于结点是关联于结点vi-1,vi边，结点与边边，结点与边交替序列交替序列v0 e1 v1 en vn称为联结称为联结v0到到vn路路。v1v4v5v2v3e1e2e3e4e5e6e7e8v1v4v5v2v3e1e2e3e4e5e6e7e8v0v3v4v1v2e1e2e3e4e5e6e7e824第24页路其它概念路其它概念（1）V0和和vn分别称作分别称作路起点与终点路起点与终点。（2）一条路中全部边数目称作）一条路中全部边数目称作路长度路长度。（3）若）若V0=vn则路称作则路称作回路回路。（4）一条路中全部边均不相同，则此路称作）一条路中全部边均不相同，则此路称作迹迹。（5）一条路中全部结点均不相同，则此路称作）一条路中全部结点均不相同，则此路称作通通路路。（6）对于回路，除）对于回路，除V0=vn外，其余结点均不相外，其余结点均不相同，则此路称作同，则此路称作圈圈。v0v3v4v1v2e1e2e3e4e5e6e7e87.2 路与回路路与回路25第25页路表示方法：路表示方法：(a)结点表示法：结点表示法：(b)边表示法：边表示法：例：给出有向图，求例：给出有向图，求起始于，终止于起始于，终止于路路7.2 路与回路路与回路26第26页定理：定理：在一个含有在一个含有n个结点图中，假如从结点个结点图中，假如从结点vj到结点到结点vk存在一条路，则从从结点存在一条路，则从从结点vj到结点到结点vk必存在一条小必存在一条小于于n-1条边路。条边路。推论推论：在一个含有：在一个含有n个结点图中，假如从结点个结点图中，假如从结点vj到结点到结点vk存在一条路，则从从结点存在一条路，则从从结点vj到结点到结点vk必存在一条条必存在一条条边数小于边数小于n通路。通路。7.2 路与回路路与回路27第27页无向图结点连通性无向图结点连通性定义定义设图为无向图，且设图为无向图，且，若从，若从vi到到vj存在任何一条路径话，则称存在任何一条路径话，则称vi到到vj是连通。是连通。有向图结点可达性有向图结点可达性定义定义设图为简单有向图，且设图为简单有向图，且，若从，若从vi到到vj存在任何一条路径话，则称存在任何一条路径话，则称vi到到vj是可达。是可达。7.2 路与回路路与回路28第28页图连通性：图连通性：（1）连通性与非连通性：连通性与非连通性：一个无向图，假如它任何两结点间均是连通，则称图一个无向图，假如它任何两结点间均是连通，则称图G是连通，不然是非连通。是连通，不然是非连通。一个有向图，忽略边方向后得到无向图，若是连通，则一个有向图，忽略边方向后得到无向图，若是连通，则称该有向图为连通图，不然称非连通图。称该有向图为连通图，不然称非连通图。（a）（b）abcdabcd7.2 路与回路路与回路29第29页（2）强连通，单向连通，弱连通强连通，单向连通，弱连通 有向图有向图G：（简单有向图）：（简单有向图）假如假如G任何两结点间均是相互可达，则称图任何两结点间均是相互可达，则称图G是是强连通强连通。假如假如G任何两结点间最少有一个结点到另一结点是可达。则称任何两结点间最少有一个结点到另一结点是可达。则称G是是单向连通单向连通。假如忽略边方向，将它看成无向图后，图是连通，则称该图为假如忽略边方向，将它看成无向图后，图是连通，则称该图为弱弱连通连通。7.2 路与回路路与回路30第30页定理定理一个有向图是强连通充要条件是：它包含一个回路，该回路最少包含每个结点一次。7.2 路与回路路与回路31第31页定义定义设，为一简单有向图，且是子图。含有强连通性质最大子图称为强分图；含有单侧连通性质最大子图称为单侧图；含有弱连通性质最大子图称为弱分图。例：7.2 路与回路路与回路32第32页定理定理在任一简单有向图，中，有向图每一个结点位于且只位于一个强分图之中。7.2 路与回路路与回路33第33页定义定义设无向图设无向图G=是连通图是连通图,若存在若存在V1 V,使图使图G删删除了除了V1中全部结点后中全部结点后,所得子图是不连通，所得子图是不连通，而对于任意而对于任意V2 V1，图图G删除了删除了V2中全部结点后中全部结点后,所得子图是连通，则称所得子图是连通，则称V1是是G点割集。点割集。若某一个结点组成一个点割集，则称该结点为割点。若某一个结点组成一个点割集，则称该结点为割点。在下列图中在下列图中,v2,v4,v3和和v5都是点割集都是点割集,v3和和v5都是割点。都是割点。注意注意,v1与悬挂顶点与悬挂顶点v6不在任何割集中。不在任何割集中。7.2 路与回路路与回路34第34页定义定义设设G为无向连通图且为非完全图为无向连通图且为非完全图,则称则称(G)=min|V1|V1为为G点割集点割集为为G点连通度点连通度,简称连通度。简称连通度。(G)简记为简记为。要求要求:完全图完全图Kn(n 1)点连通度为点连通度为n-1；非；非连通图点连通度为连通图点连通度为0；7.2 路与回路路与回路35第35页定义定义设无向图设无向图G=是连通图是连通图,若存在若存在E1 E,使图使图G删除了删除了E1中全部边后中全部边后,所得子图是不连通，所得子图是不连通，而对于任意而对于任意E2 E1，图图G删除了删除了E2中全部边后中全部边后,所所得子图是连通，则称得子图是连通，则称E1是是G边割集。边割集。若某一条边组成一个边割集，则称该条边为割边或若某一条边组成一个边割集，则称该条边为割边或桥。桥。7.2 路与回路路与回路36第36页在下列图中在下列图中,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集都是割集,其中其中e6和和e5是桥。是桥。7.2 路与回路路与回路37第37页定义定义设设G为无向连通图且为非平凡图为无向连通图且为非平凡图,则称则称(G)=min|E1|E1为为G边割集边割集为为G边连通度。边连通度。要求要求:平凡图边连通度为平凡图边连通度为(G)=0；非连通图；非连通图边连通度也为边连通度也为0；7.2 路与回路路与回路38第38页定理定理对于任何无向图对于任何无向图G,有有:(G)(G)(G)。本定理证实略。本定理证实略。例例(1)给出一些无向简单图给出一些无向简单图,使得使得:=；(2)给出一些无向简单图给出一些无向简单图,使得使得:。解解(1)无向完全图无向完全图Kn和零图和零图Nn都满足要求。都满足要求。7.2 路与回路路与回路39第39页(2)在两个在两个Kn(n 4)之间放置一个顶点之间放置一个顶点v,使使v与两与两个个Kn中任意两个不一样顶点相邻中任意两个不一样顶点相邻,所得简单图满所得简单图满足要求。足要求。因为这么图中有一个割点因为这么图中有一个割点v,所以所以,=1(当当n=4时时,=3)；因为有两条边组成边割集因为有两条边组成边割集,所以所以,=2(当当n=5时时,=4)。7.2 路与回路路与回路40第40页7.3 图矩阵表示矩阵是研究图相关性质最有效工具，可利用图矩阵运矩阵是研究图相关性质最有效工具，可利用图矩阵运算求出图路径、回路和其它一些性质。算求出图路径、回路和其它一些性质。图邻接矩阵表示方法图邻接矩阵表示方法定义定义设，是简单图，其中设，是简单图，其中V=v1,v2,vn定义一个定义一个nxn矩阵矩阵A，并把其中各，并把其中各元素元素aij表示成：表示成：则称矩阵则称矩阵A为图为图G邻接矩阵。邻接矩阵。41第41页（1）零图邻接矩阵称为零矩阵，即矩阵中全部）零图邻接矩阵称为零矩阵，即矩阵中全部元素均为元素均为0；（2）在图邻接矩阵中，）在图邻接矩阵中，行中行中1个数就是行中对应结点出度个数就是行中对应结点出度列中列中1个数就是列中对应结点入度个数就是列中对应结点入度7.3 图矩阵表示例：设图，以下列图所表示例：设图，以下列图所表示讨论定义：讨论定义：42第42页矩阵计算矩阵计算：能够用来计算两结点间路能够用来计算两结点间路径长度。径长度。定理：设定理：设A(G)是图是图G邻接矩阵，则邻接矩阵，则(A(G)l中中i行行j列元素列元素aij(l)等于等于G中联结中联结vi与与vj长度为长度为l路数目。路数目。7.3 图矩阵表示43第43页表示表示i和和j之间含有长度为之间含有长度为2路径数，路径数，表示表示i和和j之间含有长度为之间含有长度为3路径数，路径数，表示表示i和和j之间含有长度为之间含有长度为4路径数，路径数，7.3 图矩阵表示44第44页bij表示从结点表示从结点vi到到vj有长度分别为有长度分别为1，2，3，4不一样路径总数。不一样路径总数。此时，此时，bij 0，表示从，表示从vi到到vj是可达是可达。7.3 图矩阵表示45第45页定义定义设，是简单有向图，设，是简单有向图，其中其中|V|=（），定义一个），定义一个矩阵矩阵P，它元素为：，它元素为：则则P称为图称为图G可达性矩阵。可达性矩阵。由由矩阵可计算出可达性矩阵，其方法是：矩阵可计算出可达性矩阵，其方法是：若若中（中（i,j）是非）是非“0”元素，则对应元素，则对应，不然，不然7.3 图矩阵表示46第46页定义定义设无向图，设无向图，其中其中，。，。令则称则称B为无向图为无向图G完全关联矩阵完全关联矩阵7.3 图矩阵表示47第47页例：7.3 图矩阵表示48第48页7.4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图哥尼斯堡七桥问题：哥尼斯堡七桥问题：18世纪在哥尼斯堡城世纪在哥尼斯堡城(今俄罗斯加里宁格勒今俄罗斯加里宁格勒)普莱格尔普莱格尔河上有河上有7座桥，将河中两个岛和河岸连结，如图座桥，将河中两个岛和河岸连结，如图1所表示。所表示。城中居民经常沿河过桥散步，于是提出了一个问题：能否城中居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍一次走遍7座桥，而每座桥只许经过一次，最终仍回到起座桥，而每座桥只许经过一次，最终仍回到起始地点。这就是七桥问题，一个著名图论问题。始地点。这就是七桥问题，一个著名图论问题。49第49页于是于是“七桥问题七桥问题”就等价于图中所画图形一笔画问题了。就等价于图中所画图形一笔画问题了。欧拉欧拉注意注意到不存在一次走遍到不存在一次走遍7座桥，而每座桥只许经过座桥，而每座桥只许经过一次走法。一次走法。陆地是桥梁连接地点，不妨把图中被河隔开陆地看成陆地是桥梁连接地点，不妨把图中被河隔开陆地看成A、B、C、D，4个点，个点，7座桥表示成座桥表示成7条连接这条连接这4个点线，如图所表示。个点线，如图所表示。50第50页基本概念基本概念1、欧拉图：、欧拉图：给定无孤立结点图给定无孤立结点图G，若存在一条路，经，若存在一条路，经过图中每边一次且仅一次，该条路称为过图中每边一次且仅一次，该条路称为欧拉路欧拉路；若；若存在一条回路，经过图中每边一次且仅一次，该回存在一条回路，经过图中每边一次且仅一次，该回路称为路称为欧拉回路欧拉回路。含有欧拉回路图称为含有欧拉回路图称为欧拉图欧拉图。v2v3v4v1C（V1、V2、V3、V1、V4、V3）51第51页定理定理定理定理1：给定无向连通图：给定无向连通图G，G是是欧拉图欧拉图，当且仅，当且仅当图中每个结点都是当图中每个结点都是偶数度偶数度结点。结点。定理定理2：无向图：无向图G有一条有一条欧拉路欧拉路，当且仅当，当且仅当G是是连连通通，且有，且有零个零个或或两个两个奇数度结点。奇数度结点。v2v3v4v152第52页例：从图中找一条从图中找一条欧拉路欧拉路。解解 奇数度顶点是奇数度顶点是:v1和和v9。v1,v2和和v4,v6是桥。是桥。L=v1,v2,v3,v4,v5,v2,v4,v6,v7,v8,v9,v10,v6,v8,v10,v7,v9 是一是一条欧拉路。条欧拉路。53第53页欧拉图欧拉图定义：定义：给定有向图给定有向图G，经过图中每边一次且仅一次一条单，经过图中每边一次且仅一次一条单向路（回路），称作单向欧拉路（回路）。向路（回路），称作单向欧拉路（回路）。定理定理3：有向图有向图G含有一条单向欧拉回路，当且仅当是连通，含有一条单向欧拉回路，当且仅当是连通，且每个结点入度等到于出度。且每个结点入度等到于出度。一个有向图一个有向图G中含有中含有单向欧拉路单向欧拉路，当且仅当它是，当且仅当它是连通连通，而，而且除且除两个结点外两个结点外，每个结点，每个结点入度入度等于等于出度出度，但这两个结点，但这两个结点中，一个结点入度比出度小中，一个结点入度比出度小1，一个结点入度比出度大，一个结点入度比出度大1。54第54页欧拉回路问题既是一个欧拉回路问题既是一个有趣游戏有趣游戏问题问题,又是一个有又是一个有实用价值实用价值问题。问题。邮递员普通邮递路线是需要邮递员普通邮递路线是需要遍历一些特定街道遍历一些特定街道,理想地理想地,他他应该走一条欧拉路应该走一条欧拉路,即即不重复地走遍图中每一条边不重复地走遍图中每一条边。有邮递任务是有邮递任务是联络一些特定收发点联络一些特定收发点,不要求走遍每一条边不要求走遍每一条边,只要求不重复地遍历图中每一个顶点只要求不重复地遍历图中每一个顶点,此时此时感兴趣是图中顶感兴趣是图中顶点点,这就是下面研究汉密尔顿图。这就是下面研究汉密尔顿图。55第55页汉密尔顿图汉密尔顿图1859年年,爱尔兰数学家汉密尔顿爱尔兰数学家汉密尔顿(Halmiton)提出一个提出一个“周游周游世界世界”游戏游戏,它把图它把图(a)所表示正十二面体二十个顶点看成所表示正十二面体二十个顶点看成是地球上二十个城市是地球上二十个城市,要求旅游者从某个城市出发要求旅游者从某个城市出发,沿棱沿棱走过每个城市一次且仅一次走过每个城市一次且仅一次,最终回到出发点最终回到出发点。(b)图中粗图中粗线所组成回路就是问题答案线所组成回路就是问题答案ab56第56页二、汉密尔顿图二、汉密尔顿图1、定义：定义：给定图给定图G，若存在一条通路，经过图中每，若存在一条通路，经过图中每个结点恰好一次，这条通路称作个结点恰好一次，这条通路称作汉密尔顿路汉密尔顿路。若存在一条回路，经过图中每个结点恰好一次，若存在一条回路，经过图中每个结点恰好一次，这条回路称作这条回路称作汉密尔顿回路汉密尔顿回路。含有汉密尔顿回路。含有汉密尔顿回路图称作图称作汉密尔顿图汉密尔顿图。57第57页例：(a)存在汉密尔顿回路存在汉密尔顿回路,(a)是汉密尔顿图。是汉密尔顿图。(b)存在汉密尔顿通路但不存在汉密尔顿回路存在汉密尔顿通路但不存在汉密尔顿回路,(b)不是汉密尔顿不是汉密尔顿图。图。(c)不存在汉密尔顿通路且不存在汉密尔顿回路不存在汉密尔顿通路且不存在汉密尔顿回路,(c)不是汉密尔不是汉密尔顿图。顿图。（a）（b）（c）58第58页欧拉图、欧拉回路和汉密尔顿图、汉密尔顿回路之欧拉图、欧拉回路和汉密尔顿图、汉密尔顿回路之间间区分区分。(1)欧拉回路是简单回路欧拉回路是简单回路,而而汉密尔顿图是基本回路汉密尔顿图是基本回路。简单回路：简单回路：各边全不相同回路。各边全不相同回路。基本回路：基本回路：除终点与始点外，各结点全不相同回除终点与始点外，各结点全不相同回路。路。(2)欧拉图欧拉图遍历边遍历边,而而汉密尔顿汉密尔顿图图遍历顶点遍历顶点。59第59页汉密尔顿图汉密尔顿图2、定理：定理：若图若图G=含有汉密尔顿回路含有汉密尔顿回路(路路)，则，则对于结点集对于结点集V每个非空子集每个非空子集S(真子集真子集S)有：有：W（G-S）|S|成立，其中成立，其中W（G-S）是）是G-S中连通分支数。中连通分支数。(必要条件必要条件)。v1v2v7v3v5v8v4v6取取S=v1，v4v2v7v3v5v8v660第60页汉密尔顿图汉密尔顿图3、定理：定理：设图设图G是有是有n个结点简单图，若个结点简单图，若G中每一对结中每一对结点度数之和大于等于点度数之和大于等于n-1，则，则 G 中存在汉密尔顿路。中存在汉密尔顿路。（充分条件充分条件不是不是必要条件必要条件）61第61页汉密尔顿图汉密尔顿图4、定理：定理：设图设图G是有是有n个结点简单图，若个结点简单图，若G中每一对结中每一对结点度数之和大于等于点度数之和大于等于n，则，则 G 中存在汉密尔顿回路。中存在汉密尔顿回路。（充分条件充分条件不是不是必要条件必要条件）62第62页7.5 平面图先看一个例子：先看一个例子：有六个结点图如右，有六个结点图如右，试问：能否转变成与其等价，试问：能否转变成与其等价，但没有任何交线平面上图？但没有任何交线平面上图？定义定义设设G=是一个无向图，假如能够把是一个无向图，假如能够把G全部结点和边画在平面上，且使得任何两条全部结点和边画在平面上，且使得任何两条边除了端点外没有其它交点，就称边除了端点外没有其它交点，就称G是一个平是一个平面图。面图。45663第63页讨论定义：讨论定义：（1）原来在平面上图形）原来在平面上图形似交叉，但经过若干次似交叉，但经过若干次改画后，变成符合定义改画后，变成符合定义所要求图；所要求图；7.5 平面图64第64页（3）并非全部图经过处理之后都可变为平面图。）并非全部图经过处理之后都可变为平面图。怎样判断一个图是否为平面图，介绍以下几个方怎样判断一个图是否为平面图，介绍以下几个方法：法：1.观察法：观察法：找出基本循环，将交叉边分别放置在基本循环内找出基本循环，将交叉边分别放置在基本循环内或外而防止交叉。或外而防止交叉。7.5 平面图65第65页2欧拉定理：欧拉定理：定义定义设设G是一连通平面图，由图中边所包围区是一连通平面图，由图中边所包围区域，且在该区域内既不包含图结点，也不包含域，且在该区域内既不包含图结点，也不包含图边，这么区域称为图边，这么区域称为G面面。包围一个面诸边称为此面边界。包围一个面诸边称为此面边界。面面积为有限者称为有限面，面面积为无限者面面积为有限者称为有限面，面面积为无限者称为无限面。称为无限面。例：例：7.5 平面图66第66页注：一个面边界回路长度称作是该面次数，记为：注：一个面边界回路长度称作是该面次数，记为：deg(r)定理定理1：一个有限平面图，面次数之和等于其边：一个有限平面图，面次数之和等于其边数两倍。数两倍。证证实实：对对于于G中中每每一一条条边边e，e或或是是两两个个面面公公共共边边，或或是是在在一一个个面面中中为为悬悬挂挂边边被被作作为为边边界界计计算算两两次次，故故定理成立。证毕定理成立。证毕7.5 平面图67第67页定理定理2(欧拉定理欧拉定理)设图设图G是一个是一个n个结点个结点,m条边连条边连通平面图，它面数为通平面图，它面数为r，则有欧拉公式：，则有欧拉公式：nmr2。证实证实:用归纳法用归纳法 m=0时，时，G为平凡图，为平凡图，n=1，r=1，公式成立。，公式成立。7.5 平面图68第68页设设m=k-1（k1）时公式成立，现在考虑）时公式成立，现在考虑m=k时时情况。因为在连通图上增加一条边仍为连通图，情况。因为在连通图上增加一条边仍为连通图，则有三种情况：则有三种情况：（1）所增边为悬挂边，此时）所增边为悬挂边，此时G面数不变，面数不变，顶点数增顶点数增1，公式成立。，公式成立。（2）在图任意两个不相邻点间增加一条边，）在图任意两个不相邻点间增加一条边，此时此时G面数增面数增1，边数增，边数增1，但顶点数不变，公，但顶点数不变，公式成立。式成立。（3）所增边为一个环，此时）所增边为一个环，此时G面数增面数增1，边数增边数增1，但顶点数不变，公式成立。，但顶点数不变，公式成立。7.5 平面图69第69页定理3:设G是连通（n，m）平面图且每个面次数最少为l（l3），则 证实证实:由定理由定理1(r为G面数)再由欧拉公式 n-m+r=27.5 平面图70第70页于是有故 7.5 平面图71第71页定理定理4:设图设图G是一个是一个n个结点个结点,m条边连通简单平条边连通简单平面图，若面图，若n33则则m3n-6。上述定理给出了是平面图必要条件，若不满足这上述定理给出了是平面图必要条件，若不满足这些条件，则一定不是平面图。些条件，则一定不是平面图。例：例：7.5 平面图72第72页证证实实：因因为为G是是n3连连通通简简单单平平面面图图，所所以以G每每个个面面最最少少由由3条条边边围围成成，即即l 3，代代入入定定理理3，得，得m3n-6证毕证毕7.5 平面图73第73页推推论论1:若若连连通通简简单单平平面面图图G不不以以K3为为子子图图，则则m2n-4。证证实实:因因为为G中中不不含含K3，所所以以G每每个个面面最最少少由由4条边围成，即条边围成，即l4，代入定理，代入定理3，得，得m2n-4证毕证毕7.5 平面图74第74页推论推论2K5和和K3，3是非平面图。是非平面图。证证实实:假假设设K5是是平平面面图图，由由定定理理4可可知知应应有有m3n-6，而而当当n=5，m=10时时，这这是是不不可可能，所以能，所以K5是非平面图。是非平面图。假假设设K3，3是是平平面面图图，因因其其不不含含子子图图K3，由由推推论论1可可知知，当当n=6，m=9时时，m2n-4是是不可能，所以不可能，所以K3，3是非平面图。证毕是非平面图。证毕7.5 平面图75第75页3库拉托夫斯基（库拉托夫斯基（Kuratowski波兰数学家）定理：波兰数学家）定理：给定两个图，做以下工作：给定两个图，做以下工作：(1)在（在（a）图左边中间联线上插入一个度数为）图左边中间联线上插入一个度数为2结点，结点，则把一条边分成了二条边；则把一条边分成了二条边；(2)在（在（b）图左边图中去掉一个度数为）图左边图中去掉一个度数为2结点，则把二结点，则把二条边变成一条边。条边变成一条边。此二项工作不会影响图平面性。此二项工作不会影响图平面性。7.5 平面图76第76页定义定义设设G1、G2是二个图，假如它们是同构，是二个图，假如它们是同构，或能够经过重复插入或删除度数为或能够经过重复插入或删除度数为2结点，使结点，使得得G1和和G2同构，则称同构，则称G1、G2为为2度结点内同度结点内同构。构。例：以下二对图是度数为例：以下二对图是度数为2结点同构结点同构2度结点内同构度结点内同构7.5 平面图77第77页定理定理（Kuratowski定理）即库拉托夫斯基定定理）即库拉托夫斯基定理理设设G是一个图，当且仅当是一个图，当且仅当G不包含任何在度数为不包含任何在度数为2结点内与结点内与K3,3和和K5图同构子图时，则图同构子图时，则G才是平才是平面图。面图。这一定理给出了一个图是平面图充要条件。这一定理给出了一个图是平面图充要条件。7.5 平面图78第78页【例】【例】证实图中（证实图中（a）和（）和（d）不是平面图。）不是平面图。解解:图图(a）是著名彼得森（）是著名彼得森（Pertersen）图，去掉其）图，去掉其中两条边后得子图（中两条边后得子图（b），该子图同构于），该子图同构于K3，3（c）。所以彼得森图不是平面图。图（）。所以彼得森图不是平面图。图（d）图中含）图中含有子图（有子图（e），图（），图（e）图同构于）图同构于K3，3（f）。）。库库拉拉托托斯斯基基定定理理即即使使简简单单漂漂亮亮，但但实实现现起起来来并并不不轻轻易易，尤尤其其是是顶顶点点数数较较多多时时候候，还还有有许许多多这这方方面研究工作要做。面研究工作要做。7.5 平面图79第79页7.5 平面图80第80页1.对偶图对偶图平平面面图图有有一一个个很很主主要要特特征征，任任何何平平面面图图都都有一个与之对应平面图，称为它对偶图。有一个与之对应平面图，称为它对偶图。定定义义1设设平平面面图图G=V,E有有r个个面面R1，R2，Rr，若若有有图图G*=V*,E*满满足足下下述条件：述条件：（1）RiG，内内部部有有且且仅仅有有一一个个结结点点v*iV*，i=1，2，r。7.6 对偶图与着色81第81页（2）若若e是是G中中两两个个不不一一样样面面Ri和和Rj公公共共边边，则则存存在在且且仅仅存存在在一一条条边边e*kG*,使使e*k=（v*i，v*j），且与且与e相交；相交；（3）若若e是是一一个个面面Ri内内边边，则则在在G*中中有有一一条条与与e交交叉环（叉环（v*i，v*i）。）。则称则称G*为为G对偶图，对偶图，G*与与G互为对偶图。互为对偶图。7.6 对偶图与着色82第82页7.6 对偶图与着色比比如如，图图（a）和和（b）中中，G*是是G对对偶偶图图，G边边用用实实线线表表示示，G*边边用用虚虚线线表表示示，顶顶点点用用实实心心点点表表示。示。83第83页2.着色问题着色问题在在地地图图上上，相相邻邻国国家家涂涂不不一一样样颜颜色色，最最少少需需要要多多少少种种颜颜色色？100多多年年前前，有有些些人人提提出出了了“四四色色猜猜测测”，即即只只用用四四种种颜颜色色就就能能做做到到，但但一一直直无无法法证证实实，直直到到1976年年美美国国数数学学家家才才用用电子计算机证实了这一猜测。电子计算机证实了这一猜测。地地图图着着色色自自然然是是对对平平面面图图面面着着色色，利利用用对对偶偶图图，可可将将其其转转化化为为相相对对简简单单顶顶点点着着色色问问题，即对图中相邻顶点涂不一样颜色。题，即对图中相邻顶点涂不一样颜色。7.6 对偶图与着色84第84页定定义义2设设G是是一一个个无无自自环环图图，给给G每每个个顶顶点点指指定定一一个个颜颜色色，使使相相邻邻顶顶点点颜颜色色不不一一样样，称称为为对对G一一个个正正常常着着色色。图图G顶顶点点可可用用k种种颜颜色色正正常常着着色色，称称G是是k可着色。可着色。使使G是是k可可着着色色数数k最最小小值值称称为为G色色数数，记记作作(G)。假如。假如(G)=k，则称，则称G是是k色。色。7.6 对偶图与着色85第85页到到现现在在还