《离散数学课件第5章》由会员分享，可在线阅读，更多相关《离散数学课件第5章（89页珍藏版）》请在金锄头文库上搜索。
1、1离散数学Discrete Mathematics Chapter 5graph theory 3CHAPTER 5 GraphsCHAPTER 5 Graphs 5.1 Introduction to Graphs 5.1 Introduction to Graphs 图的概述图的概述图的概述图的概述5.2 Graph Terminology 5.2 Graph Terminology 图的术语图的术语图的术语图的术语5.3 Representing Graphs and Graph Isomorphism5.3 Representing Graphs and Graph Isomorphi
2、sm图的表示和图的同构图的表示和图的同构图的表示和图的同构图的表示和图的同构 5.4 Connectivity 5.4 Connectivity 连通性连通性连通性连通性5.5 Euler and Hamilton Paths 5.5 Euler and Hamilton Paths 欧拉通路和哈密顿通欧拉通路和哈密顿通欧拉通路和哈密顿通欧拉通路和哈密顿通路路路路5.6 Planar Graphs and Graph Coloring 5.6 Planar Graphs and Graph Coloring 平面图与着平面图与着平面图与着平面图与着色色色色5.7 Trees 5.7 Trees
3、 树树树树42024/8/22一、一、Euler Paths Konigsberg Seven Bridge Problem Konigsberg Seven Bridge Problem 哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题C CA AB BD D52024/8/22Terminologies:nEuler Circuit 图图G里的欧拉回路是包含着里的欧拉回路是包含着G的每一条边的简单回路的每一条边的简单回路.nEuler Path 图图G里的欧拉通路是包含着里的欧拉通路是包含着G的每一条边的简单通路的每一条边的简单通路 nEuler Graph A graph
4、 contains an Euler circuit. 判别定理：无向图判别定理：无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通图，是连通图，且且G中没有奇度顶点。中没有奇度顶点。 (充要条件充要条件)证明（反证法）：证明（反证法）： 设设C=(e1=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是图中是图中最大的回路。最大的回路。 假设假设C不是不是Euler回路。则图回路。则图G如下图所示：如下图所示：CC或 图是连通的，则顶点不可能出现下面的情况：C图中任意结点的度均为偶数，有如下所示：C与假设矛盾， C是Euler回路。C82024/8/22Necessary an
5、d sufficient condition for Euler circuit and pathsNecessary and sufficient condition for Euler circuit and paths欧拉回路和欧拉通路的充要条件欧拉回路和欧拉通路的充要条件欧拉回路和欧拉通路的充要条件欧拉回路和欧拉通路的充要条件 【 Theorem 1】连通多重图具有欧拉回路当且仅当它的每个顶连通多重图具有欧拉回路当且仅当它的每个顶点都有偶数度点都有偶数度Proof:(1)Necessary condition必要条件必要条件 G has an Euler circuit Every v
6、ertex in V has even degree Consider the Euler circuit.u the vertex a which the Euler circuit begins withu the other vertex92024/8/22 (2) sufficient condition We will form a simple circuit that begins at an arbitrary vertex a of G.nBuild a simple path x0=a, x1, x2,xn=a.nAn Euler circuit has been cons
7、tructed if all the edges have been used. otherwise,nConsider the subgraph H obtained from G. Let w be a vertex which is the common vertex of the circuit and H. Beginning at w, construct a simple path in H. 102024/8/22【 Theorem 2】 连通多重图具有欧拉通路而无欧拉回路，连通多重图具有欧拉通路而无欧拉回路，当且仅当它恰有两个奇数度顶点当且仅当它恰有两个奇数度顶点Exampl
8、e 1 Konigsberg Seven Bridge Problem哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题C CA AB BD DSolution: The graph has four vertices of odd degree. Therefore, it does not have an Euler circuit.欧拉回路欧拉回路112024/8/22Example 2 Determine whether the following graph has an Euler path. Construct such a path if it exists.判断
9、下判断下图是否是否具有欧拉通路，如果存在构建一条通路具有欧拉通路，如果存在构建一条通路BCDEFGHIJASolution: The graph has 2 vertices of odd degree, and all of other vertices have even degree . Therefore, this graph has an Euler path.122024/8/22Example 2 Determine whether the following graph has an Euler path. Construct such a path if it exists
10、.BCDEFGHIJASolution: The graph has 2 vertices of odd degree, and all of other vertices have even degree . Therefore, this graph has an Euler path.The Euler path:A,C,E,F,G,I,J,E,A,B,C,D,E,G, H,I,G,J 欧拉回路求解方法欧拉回路求解方法（Fleurys algorithm ）：）： (1)可从任一点出发去掉连接此点的一边。可从任一点出发去掉连接此点的一边。 (2)依序去掉相连的边但必须注意下列两条件：依序
11、去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。例例: 求出下图的一条求出下图的一条Euler回路。回路。v1v2v5v3v4v6v7v8v9解：首先看图中是否有解：首先看图中是否有Euler回路，即看每个顶点的度是否都是回路，即看每个顶点的度是否都是偶数。偶数。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存
12、在所以存在Euler回路。回路。 可以任意一个顶点为起点，这里以可以任意一个顶点为起点，这里以v2为起点为起点:v1v2v5v3v4v6v7v8v9依序去掉相连的边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。可去也。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v9依序去掉相连的边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的、如果某边去掉后会导致某点无连通的 边，则
13、此顶点亦可去。边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。(1)先去掉(v2,v4)v1v2v5v3v4v6v7v8v91例子11解答4依序去掉相连的边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。(2)接着去掉(v4,v3)v1v2v5v3v4v6v7v8v912依序去掉相连的边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉
14、后会导致某点无连通的、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。(3)接着去掉(v3,v2)v1v2v5v3v4v6v7v8v9123依序去掉相连的边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v9123v1v2v5v3v4v6v7v8v912345678依序去掉相连的
15、边但必须注意下列两条件：依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。、去某边后不能造成图形的不连通。这时，如果去掉(v6,v5)将导致图不连通v1v2v5v3v4v6v7v8v91234567891011121314V2-v4-v3-v2-v1-v4-v5-v9-v6-v8-v9-v7-v6-v5-v2Euler回路：从上例可知， Euler回路不唯一。232024/8/22Euler circuit and paths in directed gra
16、phs Euler circuit and paths in directed graphs 有向图中的欧拉回路与欧拉通路有向图中的欧拉回路与欧拉通路有向图中的欧拉回路与欧拉通路有向图中的欧拉回路与欧拉通路 A directed multigraph having no isolated vertices has an Euler circuit if and only if 一一个个没没有有孤孤立立顶点点的有向多重的有向多重图含有欧拉回路的充要条件是：含有欧拉回路的充要条件是： - the graph is weakly connected 弱弱连通的通的 - the in-degree a
17、nd out-degree of each vertex are equal 每个每个顶点的出度和入度相等点的出度和入度相等 242024/8/22A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if一个没有孤立顶点的有向多重图含有欧拉通路但不含欧拉一个没有孤立顶点的有向多重图含有欧拉通路但不含欧拉回路的充要条件是：回路的充要条件是： - the graph is weakly connected 弱弱连通的通的 - the in-d
18、egree and out-degree of each vertex are equal for all but two vertices, one that has in-degree 1 larger than its out-degree and the other that has out-degree 1 larger than its in-degree. 除去两个顶点外每个顶点的出度和入度相等，其中除去两个顶点外每个顶点的出度和入度相等，其中一个顶点的出度比入度大一个顶点的出度比入度大1，另一个顶点的入度比出度，另一个顶点的入度比出度大大1.252024/8/22Example
19、 3 Determine whether the directed graph has an Euler path. Construct an Euler path if it exists.acbddeg-(v)deg+(v)a12b22c22d32 Hence, the directed graph has an Euler path.Solution:262024/8/22Application Application A type of puzzle Draw a picture in a continuous motion without lifting a pencil so th
20、at no part of the picture is retraced. The equivalent problem: Whether the graph exist an Euler path or circuit. For example,272024/8/22二、二、Hamilton paths and circuit 哈密顿通路和回路哈密顿通路和回路 Hamiltons puzzle282024/8/22 A Hamilton path in a graph G is a path which visits ever vertex in G exactly once. 哈密顿通路
21、是一个访问图哈密顿通路是一个访问图G中每个顶点次数有且仅有一次的通路中每个顶点次数有且仅有一次的通路 A Hamilton circuit (or Hamilton cycle) is a cycle which visits every vertex exactly once, except for the first vertex, which is also visited at the end of the cycle. 哈密顿回路，仅访问每个顶点一次，但除去始点，这个始点同样哈密顿回路，仅访问每个顶点一次，但除去始点，这个始点同样也是终点。也是终点。 If a connected g
22、raph G has a Hamilton circuit, then G is called a Hamilton graph. 如果一个连通图如果一个连通图G含有含有哈密顿回路，那么哈密顿回路，那么G是哈密顿图是哈密顿图 Note: 定义适用与所有类型的有向图和无向图定义适用与所有类型的有向图和无向图.292024/8/22 The The sufficient sufficient condition condition for for the the existence existence of of Hamilton Hamilton path path and and Hamilt
23、on circuitHamilton circuit哈密顿通路和哈密顿回路存在的充分条件哈密顿通路和哈密顿回路存在的充分条件【 Theorem 3】 DIRACTHEOREM 狄拉克定理狄拉克定理如果如果G是带是带n个顶点的连通简单图，其中个顶点的连通简单图，其中 n=3，则，则G有哈密顿有哈密顿回路的充分条件是每个顶点的度都至少为回路的充分条件是每个顶点的度都至少为 n/2【 Theorem 4】ORETHEOREM 奥尔定理奥尔定理If G is a simple graph with n vertices with n=3 such thatdeg(u)+deg(v) = n for e
24、very pair of nonadjacent vertices u and v in G , then G has a Hamilton circuit.如果如果G是带是带n个顶点的连通简单图，其中个顶点的连通简单图，其中n=3 ，并且对于，并且对于G中中每一对不相邻的顶点每一对不相邻的顶点u和和v来说，都有来说，都有deg(u)+deg(v) = n ，则则G有哈密顿回路。有哈密顿回路。302024/8/22 The necessary condition for Hamilton path and Hamilton circuit The necessary condition for
25、 Hamilton path and Hamilton circuitFor undirected graph:The necessary condition for the existence of Hamilton path:nG is connected;nThere are at most two vertices which degree are less than 2.The necessary condition for the existence of Hamilton circuit: nThe degree of each vertex is larger than 1.
26、Hamilton回路回路定义：若图定义：若图G存在一条回路存在一条回路P，它通过，它通过G的每个顶点各一次的每个顶点各一次又回到起点，则这回路称为又回到起点，则这回路称为G的的Hamilton回路回路。若图若图G中存在中存在Hamilton回路，则称回路，则称G为为Hamilton图图。在图在图G中，若存在通过每个顶点各一次的道路，则称这条道中，若存在通过每个顶点各一次的道路，则称这条道路为路为Hamilton道路道路。定理定理(充分条件充分条件) ：设简单图：设简单图G的顶点数为的顶点数为n(n3)，若若G中任意一对顶点中任意一对顶点vi、vj，恒有，恒有d(vi)+d(vj)n-1，则图则
27、图G中至少有一条中至少有一条Hamilton道路。道路。推论推论(充分条件充分条件) ：若任意一对顶点：若任意一对顶点vi、vj，恒有，恒有d(vi)+d(vj)n，则图，则图G中至少有一条中至少有一条Hamilton回路。回路。下面证明下面证明Hamilton道路的存在。道路的存在。证明：证明：(1)先证明先证明G是连通的。是连通的。 假设假设G不连通，则不连通，则G至少有两个连通分量。设其中一部分至少有两个连通分量。设其中一部分有有n1个顶点，另一部分有个顶点，另一部分有n2个顶点。分别在两部分各选一个顶点。分别在两部分各选一个顶点个顶点v1、v2， G是简单图，所以：是简单图，所以： d
28、(v1) n11 ，d(v2) n21， d(v1)+d(v2) n1 n2 2n1。 与假设与假设d(vi)+d(vj)n-1矛盾，所以矛盾，所以G连通。连通。(2)再证明存在再证明存在Hamilton道路：道路： 假设假设G中有一条从中有一条从v1到到vL道路道路 T=(v1,v2,vL)是图中的最长是图中的最长道路，即起点道路，即起点v1和终点和终点vL不和不和T之外的顶点相邻。之外的顶点相邻。 (a)如果如果Ln，即，即T是包含所有顶点的道路，即是包含所有顶点的道路，即T是是Hamilton道路，得证。道路，得证。 (b)若若Ln且且v1和和vL相邻，则存在包含相邻，则存在包含T的回路
29、；的回路；v1v2vpvLvL-1 若若Ln且且v1和和vL不相邻，则根据条件不相邻，则根据条件d(vi)+d(vj)n-1，有如下图，有如下图示：示：v1v2vp-1vLvp所以存在包含T的回路。Hamilton定理证明3 (c)证明存在比T更长的道路：与假设矛盾，重复（a）（c），在有限步内一定得到包含所有顶点的Hamilon道路。v1v2vp-1vLvpvk 则根据条件d(vi)+d(vj)n-1，有如下图示：372024/8/22Example 5 There are seven people denoted by A, B, C, D, E, F, G. Suppose that t
30、he following facts are known. A-English (A can speak English.)B-English, ChineseC-English, Italian, RussianD-Japanese, ChineseE-German, ItaliaF-French, Japanese, RussianG-French, German How to arrange seat for the round desk such that the seven people can talk each other?382024/8/22(1)Construct grap
31、h V=A,B,C,D,E,F,G, E=(u,v)|u,v can speak at least one common language. Solution:A-English (A can speak English.)B-English, ChineseC-English, Italian, RussianD-Japanese, ChineseE-German, ItaliaF-French, Japanese, RussianG-French, GermanA AB BC CD DE EF FGG(2) If there is a H circuit, then we can arra
32、nge seat for the round desk such that the seven people can talk each other. H circuit: A,B,D,F,G,E,C,AABDFGEC中国邮路问题中国邮路问题 中国邮路问题中国邮路问题(Chinese postman problem)，是我国数学家管梅谷于是我国数学家管梅谷于1960年首次提出的。年首次提出的。问题描述：问题描述： 设邮递员从邮局出发，遍历他所管辖的每一条街设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。道，将信件送到后返回邮局，求所走的路径最短。中国邮路问
33、题的图论模型为：中国邮路问题的图论模型为： 设设G=(V,E)是连通图，而且对于所有的是连通图，而且对于所有的e E都赋以都赋以权权c(e)0，求从点，求从点v0 V出发，通过所有边至少一次最后返回出发，通过所有边至少一次最后返回v0的回路的回路C，使得，使得 达到最小。达到最小。邮局v1v2v3v4v5v634521426351v0问题分析：问题分析：（1）如果道路正好是一个）如果道路正好是一个Euler图，则容易求解，用图，则容易求解，用Fleury算算法求出一个法求出一个Euler回路即可；回路即可；（2）如果不是）如果不是Euler图，则加上如干重复边，使之变成图，则加上如干重复边，使
34、之变成Euler图，然后求图，然后求Euler回路。回路。现在问题的现在问题的关键：关键：如何加重复边！如何加重复边！中国邮路问题是中国邮路问题是Euler回路的近似求解。回路的近似求解。定理：设E* E是使W(E*)= 达到最小 的重复边集合，当且仅当对于Ga图的任一回任一回 路路 ，恒有W( E*)W(E( )-E*)E*是重复边集合Ga是加重复边以后的Euler图E*=(v2,v3)E(C)=(v1,v2),(v1,v3)(v2,v3 )(v2,v4 )(v3,v4)v1v3v23234v42中国邮路构造算法中国邮路构造算法设已经知道度为奇数的顶点为设已经知道度为奇数的顶点为v1,v2,
35、v2h第一步第一步：添加重复边添加重复边：i从从1到到h，引从，引从v2i-1到到v2i的链的链Pi，并对，并对Pi的每条边附加的每条边附加1条重复边；条重复边；第二步第二步：检查重复边检查重复边：检查图：检查图G的每条边，使得每条的每条边，使得每条边最多有边最多有1条重复边，得到图条重复边，得到图G，G中重复边集记为中重复边集记为E(0)；第三步第三步：设初值k0；(a)若E(k)对于回路 有 ，则E(k1)=E(k) E( )，kk1，转(a)；(b)输出E(k)， E(k)便是最优集。n 第四步第四步：用Fleury算法求出Eluer回路。例例 求出下图中以求出下图中以v1为起点的一条中
36、国邮路。为起点的一条中国邮路。v1v2v3v4v6v5v751322325433解：其中解：其中v2，v3，v4，v5，v6，v7顶点的度都是奇数，引入顶点的度都是奇数，引入重复边。重复边。第一步第一步：添加重复边：添加重复边： i从从1到到h，引从，引从v2i-1到到v2i的链的链Pi，并对，并对Pi的每条边附加的每条边附加1条重复边；条重复边；v1v2v3v4v6v5v751322325433E(0)=(v2,v3),(v4,v5),(v6,v7)第二步第二步：检查重复边：检查图：检查重复边：检查图G的每条边，使得每的每条边，使得每条边最多有条边最多有1条重复边，得到图条重复边，得到图G，
37、G中重复边集中重复边集记为记为E(0)；下面看回路下面看回路 ：v2-v3-v7-v2 其中其中E( )=(v2,v3),(v2,v7),(v3,v7)E(0)=(v2,v3),(v4,v5),(v6,v7) 5 224 E(1)E(0) E( )(v2,v7),(v3,v7),(v4,v5),(v6,v7)v1v2v3v4v6v5v751322325433E(1)= (v2,v7),(v3,v7),(v4,v5),(v6,v7)下面看回路下面看回路 ： v4-v5-v6-v7-v4 其中其中E( )=(v4,v7),(v4,v5),(v5,v6 ),(v6,v7) 437 235 E(2)E
38、(1) E( )(v2,v7),(v3,v7),(v4,v7),(v5,v6)v1v2v3v4v6v5v751322325433v5E(2)= (v2,v7),(v3,v7),(v4,v7),(v5,v6)下面看回路 ： v3-v4-v7-v3 其中E( )=(v3,v4),(v4,v7),(v3,v7) E(3)E(2) E( )(v2,v7),(v3,v4),(v5,v6) 224 3v1v2v3v4v6v751322325433最后利用Fleury算法求出一个Euler回路： v1-v2-v3-v4-v3-v7-v2-v7-v4-v5-v7-v6-v5-v6-v1E(3)= (v2,v7
39、),(v3,v4),(v5,v6)v1v2v3v4v6v5v751322325433练习：求下图中一条中国邮路：练习：求下图中一条中国邮路：v1v6v2v3v7v4v5343322274152CHAPTER 5 GraphsCHAPTER 5 Graphs 5.1 Introduction to Graphs 5.1 Introduction to Graphs 图的概述图的概述图的概述图的概述5.2 Graph Terminology 5.2 Graph Terminology 图的术语图的术语图的术语图的术语5.3 Representing Graphs and Graph Isomorp
40、hism5.3 Representing Graphs and Graph Isomorphism图的表示和图的同构图的表示和图的同构图的表示和图的同构图的表示和图的同构 5.4 Connectivity 5.4 Connectivity 连通性连通性连通性连通性5.5 Euler and Hamilton Paths 5.5 Euler and Hamilton Paths 欧拉通路和哈密顿通欧拉通路和哈密顿通欧拉通路和哈密顿通欧拉通路和哈密顿通路路路路5.6 Planar Graphs and Graph Coloring 5.6 Planar Graphs and Graph Color
41、ing 平面图与着平面图与着平面图与着平面图与着色色色色5.7 Trees 5.7 Trees 树树树树 平面图平面图 1、若图可以画在一个曲面上，任意两边都不相交（端点除外），称图、若图可以画在一个曲面上，任意两边都不相交（端点除外），称图G被嵌入在曲面上被嵌入在曲面上。 2、如果曲面是平面、如果曲面是平面称称G是是可平面图可平面图。 3、如果图已经画在平面上，称图、如果图已经画在平面上，称图G为为平面图平面图。图a图b图c可平可平面图面图平面平面图图非平面图非平面图6 平面图1 4、若有一个简单的平面图，再加一条边就是不可平面，、若有一个简单的平面图，再加一条边就是不可平面，则称之为则称之
42、为最大平面图最大平面图。再加一条边就再加一条边就不是平面图了。不是平面图了。6 平面图2 5、平面图的边把图、平面图的边把图G所在的平面划分为若干个区域，所在的平面划分为若干个区域，每个区域称为图每个区域称为图G的的面面； 6、包围每个面的回路称为面的、包围每个面的回路称为面的边界边界； 7、回路的边数称为面的、回路的边数称为面的次数次数。 容易发现，平面图容易发现，平面图G每增加每增加1条边，图条边，图G总的边数和面数总的边数和面数都增加都增加1。边界面6 平面图3 8、欧拉公式定理（、欧拉公式定理（必要条件必要条件）：如果平面连通）：如果平面连通图图G有有n个顶点，个顶点，m条边，条边，d
43、个区域，则个区域，则 nmd2 证明：设图证明：设图G是有是有n个顶点一棵树，则个顶点一棵树，则 mn1，d1，这时，这时nmd2成立。成立。 G每增加每增加1条边，即条边，即m增加增加1，这时，这时d也增加也增加1。 所以所以 (顶点数顶点数)(边数边数)(域数域数)2 不变。不变。 证毕。证毕。6 平面图6 Kuratowski图K(2)图K(2)图又称二分图二分图二分图是什么？ 如果图的顶点集可以分为两个互不相交的子集，子集内结点互不邻接，则此图称为二部图二部图。K(1)图6 平面图7 定理：定理：K(1) ，K(2)不是平面图。在不是平面图。在K(1) ，K(2)的边加上若干顶点所形成
44、的图也不是平面图的边加上若干顶点所形成的图也不是平面图。与这些图同构的图分别叫与这些图同构的图分别叫K(1)型图和型图和K(2)型图型图,统称为统称为K型图。型图。6 平面图8 Kuratowski定理定理 图图G是平面图的是平面图的充要条件充要条件是：是：G图不图不存在任何子图为存在任何子图为K(1) 图或图或K(2)图。图。 证明较繁，在此不多述。证明较繁，在此不多述。 根据根据Kuratowski定理，可以断定：定理，可以断定：所有所有树树都是平面图。都是平面图。 边的着色问题边的着色问题 定义定义：给图：给图G的边着色，使得有共同顶点的边的边着色，使得有共同顶点的边异色的最少颜色数，称
45、为异色的最少颜色数，称为边色数边色数。边色数=3一、边的着色问题课程考试安排问题；课程考试安排问题； 用顶点用顶点v1,v2,vn表示表示n门课程，若其中两门课门课程，若其中两门课i,j被同被同时选，则时选，则vi,vj间连一条边。间连一条边。一、边的着色问题3定理定理：二分图：二分图G的边色数图中顶点的最大度。的边色数图中顶点的最大度。x1x2y1x3x4x5y2y3y4y5一、边的着色问题3定理定理(Vizing 1964)：若图：若图G为简单图，图中顶点最大度为为简单图，图中顶点最大度为d，则，则G的边色数为的边色数为d或或d+1。x1x2y1x3x4x5y2y3y4y5单星妖怪第一类图
46、第一类图第二类图第二类图一、边的着色问题4 边的着色问题可以转化为顶点的着色问题。边的着色问题可以转化为顶点的着色问题。 顶点的着色问题顶点的着色问题 定义定义：给图：给图G的顶点着色，使得相邻的顶点异色的最少颜的顶点着色，使得相邻的顶点异色的最少颜色数，称为色数，称为图图G顶色数顶色数，简称，简称色数色数；记作；记作(G)。(G)=2二、顶点的着色问题物资存储问题；物资存储问题；四色猜想：四色猜想： 平面图的色数不大于平面图的色数不大于5。二、顶点的着色问题1色数的性质：色数的性质：（1）图）图G只有孤立点时，只有孤立点时，(G)=1；（2）n个顶点的完全图个顶点的完全图G有有(G)=n；二
47、、顶点的着色问题1（3）若图）若图G是是n个顶点的回路，则个顶点的回路，则 (G)=2 n为偶数为偶数 =3 n为奇数；为奇数；二、顶点的着色问题1（4）图）图G是顶点数超过是顶点数超过1的树时，的树时，(G)=2；二、顶点的着色问题1（5）若图）若图G是二分图，则是二分图，则(G)=2。x1x2y1x3x4x5y2y3y4y5二、顶点的着色问题2 定理：定理： 图图G=(V,E)的色数的色数(G)=2的充要条件是：的充要条件是：(1)|E|1；(2)G不存在边数为奇数的回路。不存在边数为奇数的回路。二、顶点的着色问题2定理定理：若图：若图G=(V,E)，d=maxd(vi),vi V，则，则
48、(G)d+1。顶点着色算法顶点着色算法 下面给出顶点着色的算法下面给出顶点着色的算法(假定假定G的顶点为的顶点为v1,v2,vn;用来染色的颜色为用来染色的颜色为c1,c2,cn)： （1）对）对i=1,2,n,作作Ci=c1,c2,ci； （2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ck； （3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck； （4）转到（）转到（2），直到所有顶点都着色为止。），直到所有顶点都着色为止。三、顶点着色的算法例对下图顶点进行着色。对下图顶点进行着色。例例v1v2v3v4v5v7v6三
49、、顶点着色的算法例解（1）对i=1,2,n,作Ci=c1,c2,ci；解解v1v2v3v4v5v7v6C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7三、顶点着色的算法例解1 （2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一的第一种颜色种颜色ck；解解C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4
50、,c5,c6,c7v1v2v3v4v5v7v6c1三、顶点着色的算法例解2（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；解解v1v2v3v4v5v7v6c1C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C2=c2 C3=c2, c3 C7=c2,c3,c4,c5,c6,c7 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 三、顶点着色的算法例解3（4）转到（）转到（2），直到所有顶点都着
51、色为止），直到所有顶点都着色为止（2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ck解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2三、顶点着色的算法例解4（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,
52、c6C7=c2,c3,c4,c5,c6,c7c2C3=c3 三、顶点着色的算法例解5解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）转到（）转到（2），直到所有顶点都着色为止），直到所有顶点都着色为止（2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ckc3三、顶点着色的算法例解6解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5
53、C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；c3C5=c2,c4,c5 C1=c1,c2,c4 三、顶点着色的算法例解7解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）转到（）转到（2），直到所有顶点都着色为止），直到所有顶点都着色为止（2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ckc3
54、c1三、顶点着色的算法例解8解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；c3c1三、顶点着色的算法例解9解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）转到（）转到（2），直到所有顶点都着色为止），直到所有顶点都着色为止（
55、2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ckc3c1c2三、顶点着色的算法例解10解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；c3c1c2C6=c3,c4,c5,c6 三、顶点着色的算法例解11解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,
56、c5,c6C7=c2,c3,c4,c5,c6,c7c2（4）转到（）转到（2），直到所有顶点都着色为止），直到所有顶点都着色为止（2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ckc3c1c2c3三、顶点着色的算法例解12解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3）对顶点）对顶点vi的所有邻接点的所有邻接点vj(ji)，作，作Cj= Cj-ck；c3c1c2C7=c2,c4,c5,c6,c7 c3三、顶点着色的算法例解13解解v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c4,c5,c6,c7c2（4）转到（）转到（2），直到所有顶点都着色为止），直到所有顶点都着色为止（2）标顶点）标顶点vi (i=1,2,n)的颜色集的颜色集Ci的第一种颜色的第一种颜色ckc3c1c2c3c2本节内容到此结束本节内容到此结束
