离散数学10图的基本概念

第10章图的基本概念如何找到物流运输的最优路径？如何找到最优的网络通信线路？如果你想周游全国所有城市，如何设计旅游线路？化学化合物分析：结构是否相同？程序结构度量：程序是否结构相似？如何为考试分配教室，使得资源利用率最优？如何安排工作流程而达到最高效率？如何设计为众多的电视台频道分配最优方案？如何设计通信编码以提高信息传输效率？操作系统中,如何调度进程而使得系统效率最优？如何设计集成电路线路布局而达到最优效率？如何设计计算机鼓轮？七枚同重量硬币与一枚较轻的伪币，使用天平秤多少次就能找出伪币？如何设计下棋程序？n-皇后问题最少用几种颜色就能将世界地图都着色？如何使箱子尽可能装满物体？一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢？研究主题旅行商问题：TSP问题中国邮路问题地图着色问题：四色定理最短路径问题网络流匹配组合计数主要内容

1)图的基本术语；2)结点的度，子图，完全图；3)图的连通性；4)图的运算，图的矩阵表示及其性质；5)图的同构；6)

欧拉图与哈密尔顿图的性质及其应用。

10.1图论概述

图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。图论是有许多应用的古老学科，也一直以来都是一个热门学科，它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。10.2图与图模型例10.2

某学校共有10名教师，他们分别参加7个班级的讨论课，每个班级可能同时需要多位教师参加，有的教师可能需要参加多个班级的讨论，每个班级必须单独开展讨论课，则如何安排才使得所有班级在最短时间段内完成讨论课？讨论课的情况如下（Vi为班级编号，数字1-10为教师编号）：V6V5V4V2V3V7V1V1={1，2，3}，V2={1，3，4，5}，V3={2，5，6，7}，V4={2，6，7}，V5={4，7，8，9}，V6={8，9，10}，V7={1，3，9，10}。10.2图与图模型V6V5V4V2V3V7V1顶点集V={V1,V2,V3,V4,V5,V6,V7}边集E={<V1,V2>,<V1,V3>,<V1,V4>,<V1,V7>,<V2,V3>,<V2,V4>,<V2,V7>,<V3,V4>,<V3,V5>,<V4,V5>,<V5,V6>,<V5,V7>,<V6,V7>}图G=(V,E)的阶为7，图的规模为1310.2图与图模型

定义10.1

图G=(V,E)包括两个集合：结点集V(G)

：非空的对象的集合,V={v1,v2,…,vn}；边集E(G)

：有限的两个对象构成的V的无序对构成的集合。E={e1,e2,…,em};其中，每一条边都是集合V的二元子集，如边ei={u，v}，常常简记为uv或vu，其中u、v称为边uv的端点。10.2图与图模型

设V={v1，v2，v3，v4，v5},E=

则G=（V，E）是一个图。图(a).(b)分别给出了图G的图解方法。10.2图与图模型

节点集合V(G)的基数n表示图G的阶，边集合E(G)的基数m表示图G的规模，有时也将图G记作(n,m)。 在图G中，若边集E(G)=Ф,则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图（Trivialgraph）。N7V6V5V4V2V3V7V110.2图与图模型

结点集为空集的图为空图（EmptyGraph），并将空图记为。 阶为有限的图称为有限图(FiniteGraph)，否则称为无限图(InfiniteGraph)。10.2图与图模型:无向图环loop-->非简单图deg(v2)=4边e2关联结点v1、v2结点平行边/重边多重图孤立点悬挂边悬挂点分离边v3结点度为3,

deg(v3)=3v3v1v2e1e2(G)=4(G)=010.2图与图模型如果图中存在某两条边的端点都相同，则称该图为多重图(Multigraph)，该两条边称为平行边。如果一条边关联的两个结点是相同的结点，则称该边为圈或自环(Loop)。不存在平行边与圈的图即称为简单图(SimpleGraph)。

10.2图与图模型定义10.2

如果uv是图G的边，记为e，即uvE(G),则称结点u和v邻接(Adjacent),否则称结点u与v非邻接。与同一个结点关联的两条边称为邻接边。与结点v关联的边数称为结点v的度，记作deg(v)。与结点v关联的环对v的度数的贡献要计算两次。如果结点v的度为0，则称之为孤立点(IsolatedVertex)。一度的结点称为悬挂点（PendantVertex）。图G的所有结点度数的最小度数称为G的最小度，记作(G)，而所有结点度数的最大者称为G的最大度，记作(G)。各结点的度均相同的图称为正则图（RegularGraph）。各结点度均为k的正则图称为k-正则图。

10.2图与图模型

定义10.3

如果图的每条边是二结点构成的有序对，则该图称为有向图(DirectedGraph)，上文所定义的图都是无向图(UndirectedGraph)。有向图中边uv与vu是两条不同的边，对于边uv，称u为始点，v为终点。

有向图中，结点v的度分为入度，即与该结点相关联并以该结点为终点的边的数目，以及出度,即与该结点相关联并以该结点为始点的边的数目,分别记作deg+(v)，deg-(v)。

10.2图与图模型：有向图边e2(有向边<v1,v2>)关联结点v1、v2结点

(顶点)孤立点悬挂边悬挂点分离边v3结点度为3,出度为1,入度为2v3v1v2e1e210.2图与图模型v1v2e1e2v1v2e1e2无向图有向图10.2图与图模型

练习1

设G=(V,E)是一无向图，V={v1,v2,…,v8}，E={(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v4,v3),(v7,v8)}

（1）画出G的图解；（2）指出与V3邻接的结点，以及和V3关联的边；（3）指出与(v2,v3)邻接的边和与(v2,v3)关联的结点；（4）该图是否有孤立结点和孤立边？（5）求出各结点的度数，并判断是否是完全图和正则图？（6）该(n,m)图中，n=？，m=？定理10.1（欧拉定理）在任何图中，结点度的总和等于边数的两倍。该定理也被称为握手定理，被认为图论第一定理，可以用于证明图的相关性质。

推论10.1

在任意图中，奇数度的结点个数为偶数。

V6V5V4V2V3V7V110.2图与图模型边数=?结点度的总和=?例10.3

设G=<V;E>，|V|=n,|E|=m，证明：(G)≤2m/n≤(G)。

V6V5V4V2V3V7V110.2图与图模型(G)=？(G)=？每个顶点的平均度数=？例10.4

请证明：有向图中，所有结点出度之和等于所有结点入度之和。10.2图与图模型所有结点出度之和=？所有结点入度之和=？10.2图与图模型

练习2

设G=(V,E)有12条边，有6个度为3的结点，其余结点的度数均小于3，问G中至少有多少个结点？10.2图与图模型V1V5V3V4V2图G图G2V5V3V4V2V1G2为G的子图。

10.2图与图模型

定义10.4

令图G=（V，E），称(V′,E′)为G的子图（Subgraph），当

(1)VV且EE；

(2)对任意eE，则与e相关联的结点u,vV。若G是G的子图,则称G是G的超图/母图，记作GG。 若GG且G≠G(即VV或EE)，则称G是G的真子图。 若GG且VV，则称G是G的生成子图（SpanningSubgraph）。 设V1V,且V1≠，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称为结点集V1导出的导出子图（DerivedSubgraph）。 设E1E,且E1≠，以E1为边集，以E1中边关联的结点的全体为结点集G的子图，称为边集E1导出的导出子图。

10.2图与图模型真

生成真

非生成真

非生成真

非生成10.2图与图模型显然，子图或导出子图可以通过删除一些结点或一些边得到。

10.2图与图模型例10.9

下图所示的图中，G1是G的由结点导出的导出子图，G2为G的由边集导出的导出子图。V5V3V4V2V1V3V4V2V1由边集导出的导出子图G2图G2图G图G1由结点导出的导出子图G1V5V3V4V2V110.2图与图模型(a)(b)(c)(a)为四个结点的完全图，(b)不是完全图，(c)是有向完全图。10.2图与图模型

定义10.5

设G=<V,E>是n阶图,若G中任何结点都与其余的n1个结点相邻，则称G为n阶完全图(CompleteGraph)。记作Kn。设D=<V,E>为n阶有向图,若对于任意的结点,u,vV(u≠v),既有有向边<u,v>,又有<v,u>，则称D为有向完全图。

容易得到如下重要结论：

Kn的边数|E(Kn)|=n(n-1)/2，且对于一般的n个结点的图G其边数|E(G)|≤n(n-1)/2。10.2图与图模型

定义10.6

若图G的结点可以分为两个非空集合V1，V2，G中的边的端点分别属于V1，V2，则称G为二分图（BipartiteGraph），可简记为G(V1，V2)。若V1中结点与V2中结点均邻接且V2中结点与V1中结点也均邻接，则称G为完全二分图（CompleteBipartiteGraph），记为Km,n，m,n分别是V1，V2的基数。

10.2图与图模型v1v3v2v4v6v5v1v3v2v4v6v5二分图完全二分图V1，={v1,v3,v5},V2={v2,v4,v6}10.2图与图模型v1v6v2v3v5v1v3v2v4v6v4v5图(a)图（b）图(a)是二分图,图（b）是图(a)的另一种表示。10.3路径与图连通性例10.11

在右图中，1)通道：aebcaebd。2)通道：beacbd（迹）。3)通道：acbe（路）4）通道：acbea（环）。abedc10.3路径与图连通性图论中的许多概念和应用都与对图的遍历有关，即是从一个结点u出发，到达与之相邻接的结点，在从该邻接结点出发到达其邻接的结点，依次类推，最后可以到达图中的某结点v，从而就得到一条从u到v的通路。从

u到v的通路W的表示：W:u=v0,v1,v2,…,vk=v，k0。 通路W常表示为u-v通路。这些结点序列中任意相邻的结点在图中是邻接的关系，称结点vi（i=0，1,…,k）以及边(vi,vi+1)(i=0,1,…,k-1)为通路W上的结点与边。10.3路径与图连通性如果通路上首尾结点相同，则称该通路是闭的(Closed)，否则称该通路是开的(Opened)。如果通路上没有相同的边，则称该通路为迹(Trail)，如果迹上的开始结点与结束结点相同，则称之为回路(Circuit)，如果通路上没有相同的结点，则称该通路为路或路径(Path)，有n个结点的路常记作Pn。

如果回路上除了开始结点与结束结点没有相同的结点，则称之为环(Cycle)。10.3路径与图连通性通路遍历过的边的数目为通路的长度，如果通路长度为0，则称之为平凡通路（TrivialWalk）。两结点u，v间的路可能不只一条，将其中的最短的路称为u，v间的距离。如果一条通路W上有k+1个结点，即W:u=v0,v1,v2,…,vk=v，k≥0。则由于W上的边是由W上相邻结点(vi,vi+1)(i=0,1,…,k-1)构成，因此W上有k条边，即W的长度为k。如果一条环C上有k+1个结点，即C:v0,v1,v2,…,vkv0，k≥0.则由于C上的边是由C上相邻结点(vi,vi+1)(i=0,1,…,k-1)以及（vk,v0）构成，因此C上有k+1条边，即C的长度为k+1。10.3路径与图连通性10.3路径与图连通性

定理10.2

如果图G上存在一条u-v通路，则必然存在一条u-v路；如果G上存在一条闭通路，则必然存在一条回路(环)。这是因为，如果通路上存在相同的结点vi,vj，则可将vi,vj之间的一段通路删除，并合并vi，vj为一个结点，从而得到一条更短的u-v通路。如果所得到的u-v通路上还存在相同的结点，则可以依此继续执行删除操作，最终一定可以得到一条没有相同结点的u-v通路，也就是一条u-v路。类似地，如果G上存在一条闭通路，则必然存在一条回路（环）。

10.3路径与图连通性例10.11

在右图中，1)找出一条包含图所有结点的通道；2)找出一条包含图所有结点的迹；3)找出所有a-d路，并求出其长度；4)找出图中所有的环。解

1)包含图所有结点的不是迹的通道：aebcaebd。2)包含所有结点的迹：beacbd。3)a-d路：aebd,acbd,长度均为3。4)环：acbea，长度为4。abedc找一条回路，且该回路不是环。V5V3V4V2V1图G10.3路径与图连通性

例10.12

每个结点的度数至少为2的图必包含一个回路。证明设P是图G中最长路经中的一条，并设其长度为m,P的一个端点为u。考察G中与u关联的边，由于G中每个结点的度至少为2，故u必关联一条不在P上的边e，从而e的另一个端点v必然在P上，否则，将这个结点加入P上，则可以得到更长的路。于是，P上u到v的的路与边e构成回路。

uvP2145832610ABCDEF10.3路径与图连通性

例10.13

下图所示的带权图中，求A到其余结点的最短路径。

ABCDEF2145832610ABCDEF求A到其余结点的最短路径。

ABCDEF∞∞∞42ABCDEF1012∞32初始基于A→B最短路径2更新最短路径:A→C,D,E,FABCDEF812∞32基于A→C最短路径3更新最短路径:A→D,E,FFABCDE8101432基于A→D最短路径8更新最短路径:A→E,F基于A→E最短路径10更新最短路径:A→F2145832610ABCDEF求A到结点F的最短路径。

2145832610ABCDEF10.3路径与图连通性Dijkstra最短路径算法输入：一个带权图G，G的任意两个结点间有路径存在，G中任意边(v,x)的权值w(v,x)>0；结点a与z输出：L(z)，从结点a到z的最短路径长度1ProcedureDijkstra(G)2 For所有结点x≠a

3

L(x)=∞;L(x)表示a到x的最短路径长度4 Endfor;5

L(a)=0;6T=V(G);7 S=;

10.3路径与图连通性8While(z∈T)9 从T中找出具有最小L(v)的结点v;10 For所有与v相邻的结点x∈T11

L(x)=min{L(x),L(v)+w(v,x)}12 EndFor13 T=T-{v};14 S=S∪{v};15 EndWhile16EndProcedure

10.3路径与图连通性

连通图非连通图10.3路径与图连通性

定义10.5

如果图G中结点u到v有一条路径，则称结点u到v是可达的（Accesible）或连通的（Connected）。结点u到其自身也定义为连通的。

定义10.6

如果图G的任何两个结点都是相互可达的，称G是连通的（Connected）,并称G为连通图(ConnectedGraph)。对于有向图G，如果G的任何两个结点都是相互可达的，则称有向图G是强连通的；如果G的任何两个结点中，至少从一个结点到另一个结点是可达的，称有向图G是单向连通的；如果G的有向边被看作无向边时是连通的，称有向图G是弱连通的。

10.3路径与图连通性

容易判断，强连通图必定是单向连通图，单向连通图必定是弱连通图。连通图非连通图强连通图单向连通图弱连通图10.3路径与图连通性

练习4

已知关于a,b,c,d,e,f,g的下述事实：

a说英语；

b说英语和西班牙语；

c说英语、意大利语和俄语；

d说日语和西班牙语；

e说德语和意大利语；

f说法语、日语和俄语；

g说法语和德语；试问：上述7人中是否任意两人都能交谈（如果必要，可由其余5人中所组成的译员链帮忙？）A={王一,王二,张一,张二,张三,李一,李二,李三,李四}儿子孙子重孙子王一王二张一张二张三李一李二李三李四李一李三李二李四王一王二张一张三张二A上的亲属关系满足自反性、对称性、传递性，一个等价关系决定A的一个分类：

{王一,王二},{张一,张二,张三},{李一,李二,李三,李四}10.3路径与图连通性若将图中两个结点间的连通性看作图的结点间的一种关系，容易判定图中两个结点间的连通性是一个等价关系， 因为结点u到u是连通的满足自反性；若u到v是连通的，则v到u也是连通的，满足对称性；若u到v连通，v到w连通，则u到w存在一条通路，从而存在一条u到w的路径，故u到w是连通的，满足传递性。 但对于有向图，结点间的连通性不满足对称性。10.3路径与图连通性45e3123e2e1V={1，2，3，4，5}图上的连通关系R={(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2),(4,4),(5,5),(4,5),(5,4)}是一个等价关系，决定V的一个分类：{1，2，3}，{4，5}10.3路径与图连通性

现在可以利用结点的连通性对图G的结点集进行划分，于是利用这个划分可以得到G的多个连通子图，如

G[v]=(V[v],E[v]),

是结点v所在的一个连通子图，其中，V[v]={x|x到v可达}，E[v]为V[v]中结点在G中相应的边之集合。

G[v]具有一个特点，即不存在一个G的真子图G′,G[v]为G′的真子图,且G′也是G的连通子图。称G[v]为G的连通分支或连通分图（ConnectedComponent）,也称为极大连通子图。

10.3路径与图连通性

例10.15

如果图G恰有两个不同的奇数度的结点u，v，那么u到v必定是可达的。

证明如果u到v不可达，那么G不是连通的，u与v必分属于两个连通分支G1，G2，而G1，G2是G的子图，且都恰有一个奇数度结点。与推论10.1矛盾。因而u到v是可达的。

10.3路径与图连通性定理10.3

设G是一(n，m)图，G有ω个分图，则n-ω≤m≤(n-ω)(n-ω+1)/210.3路径与图连通性练习5

在任何n(n≥2)个顶点的简单图G中，至少有两个顶点具有相同的度。

证明如果G有两个或更多孤立顶点，那么它们便是具有相同的度的两个顶点。

如果G恰有一个孤立顶点，那么我们可对有n–1个顶点但没有孤立顶点的G’（它由G删除孤立顶点后得到）作讨论；如果G有分图，则也可以直接对分图进行讨论。因此，不妨设G没有孤立顶点，那么G的n个顶点的度数应是：1，2，3，…，n–1这n–1种可能之一，显然，必定有两个顶点具有相同的度。10.3路径与图连通性练习6

给定简单图G=<V,E>，且|V|=n，|E|＞(n-1)(n-2)/2，试证G是连通图。试给出|V|=n，|E|=(n-1)(n-2)/2的简单无向图G=<V,E>是不连通的例子。

10.3路径与图连通性点割集{1，5}126735e1e3e2e4e7e8e64e9e526735e3e4e7e8e64e92673e7e8e64e910.3路径与图连通性126735e1e3e2e4e7e8e64e9e5{e4,e5}是边割集126735e1e3e2e7e8e64e9e5126735e1e3e2e7e8e64e910.3路径与图连通性

v4是割点10.3路径与图连通性

定义10.9

设S为图G的结点集V的子集，称S为G的点割集（CutSetofVertex）,如果从G中删除S中的所有结点后G的连通分支数增加，但S的任何真子集均无这一特性。当点割集为单元素集合{v}时，v称为割点（CutVertex）。

设S为连通图G边集E的子集，称S为G的边割集（CutsetofEdge），如果从G中删除S的所有边后G的连通分支数增加，但S的任何真子集均无这一特性。当割集为单元素集{e}时，称e为桥(Bridge)或割边（CutEdge）。

10.3路径与图连通性{1，5}是点割集，2是割点，3是割点，{4，7}不是点割集。{e1,e3}是边割集，{e4,e5}是边割集，{e6,e8}是边割集，e9是割边。126735e1e3e2e4e7e8e64e9e510.3路径与图连通性例10.18

试证明：图G的任一边，若其不是割边，则必出现于G的某一环里。

证明设图G的边e=(vi，vj)不是分割边，去掉e后，与vi相连接的接点集为V1，与vj相连接的结点集为V2，由割边定义知，V1∩V2≠。因而存在一结点v∈V1∩V2，使得在去掉e后，vi与v有路相连，v与vj有路相连。于是vi与vj有路相连接，因而必存在一条连接vi与vj的路P=vi，v1，v2，…，v，…，vj，从而P与边(vi，vj)组成一个环。

10.5图的表示与图的同构1

图的表示在集合论中，曾经用关系矩阵来表示关系，事实上，图也是一种关系的表示，但用计算机来分析一个图时，矩阵是其更为形式化的表示方法，这里主要讨论邻接矩阵。构造一个图的邻接矩阵是很容易的，可以通过下面的例子来分析。10.5图的表示与图的同构

例10.21

构造下图中图G的邻接矩阵。顾名思义，邻接矩阵就是表示图结点的邻接关系的矩阵，邻接矩阵与图是一种一一对应关系。首先，需要确定图结点的顺序，本题中为a，b，c，d，e。接着，矩阵的元素(ij)表示第i个结点与第j个结点的邻接关系，这里用1或0来表示，如果邻接，则(ij)为1，否则为0。于是得到图G的邻接矩阵

aedcbA(G)=

10.5图的表示与图的同构

A(G)2==

以A(G)2中d行c列的元素为例，其值是A(G)中第d行与A(G)中第c列运算得到，即

=1∙1+0∙1+1∙0+0∙1+1∙1=2

aedcb10.5图的表示与图的同构10.5图的表示与图的同构

定理9.7

如果A是一个图G的邻接矩阵，那么An（n=1，2，3，…）中元素(ij)等于从结点i到结点j的长度为n的路径的数目。10.2图与图模型u1u3u2u4u6u5图(a)v1v6v2v3v5v4图（b）定义映射f:{u1,u2,u3,u4,u5,u6}

->{v1,v2,v3,v4,v5,v6},u1->v1,u2->v2,u3->v3,u4->v4,u5->v5,u6->v6图(a)与图(b)同构10.5图的表示与图的同构2

图的同构定义10.12

设图G1=<V1,E1>，G2=<V2,E2>，若存在双射f:V1V2，满足uV1，vV1，(u,v)E1当且仅当(f(u),f(v))E2，则称G1与G2同构，记作G1G2，f称为同构映射。如果讨论有向图的同构，则对应边的方向也必须一致。从图的同构的定义可知，二图同构则必有结点数相同，边数相同，两图中度数相同的结点的个数相同。还可以知道，图的同构关系是一种等价关系。

10.5图的表示与图的同构G1G2G3G4 G1与G2同构？ G1与G2不同构，原因在于G1中存在三结点两两相邻，而G2中不存在，因此不可能建立满足定义的双射关系。

G4与G2同构？ G4与G2不同构，原因在于G4中存在三结点两两不相邻，而G2中却不存在这样的情况。 G1与G3同构？

10.5图的表示与图的同构

G与G’同构？10.5图的表示与图的同构图的同构的判断主要是建立同构映射，如果能够建立，则同构的两个图除了结点符号相异外，结构上是完全一样的。因此，容易想到考虑用邻接矩阵来进行判断，即：图G1和G2是同构的当且仅当对某一结点的顺序，其邻接矩阵是一样的，最基本的方法是通过变换矩阵行、列元素的顺序来比较二邻接矩阵是否相等。尽管通过判断邻接矩阵来判断图是否同构是可行的，但在最坏情况下，其搜索空间将达到n!(n为结点数)，具有指数级算法复杂性。如果n很大，算法的效率是非常低的，甚至不可解。

10.5图的表示与图的同构从例10.23还可以看到，图G1和G2同构时，G1具有的特性P，G2也应该具备这个特性P。于是判断两个图G1和G2不同构的办法可以是：找到一个G1的特性P，G2并不具备。这样的一个特性称为不变量。如“有10个结点”、“有一个度数为k的结点”，以及例10.23中用到的“有k个结点两两相邻（或不相邻）”等等。如果能够找到一些可以简单测试的同构图具有且只有同构图具有的不变量，那么就可以非常容易的判断两个图是否同构。不幸的是，没有人能够成功找到这样一些不变量。10.5图的表示与图的同构

练习7

画出完全图K5的4条边的所有非同构的生成子图。10.5图的表示与图的同构

练习8画出所有具有5个结点3条边的互不同构的简单无向图。10.5图的表示与图的同构

练习9设G是具有3个结点的完全图，试问：（1）G有多少个子图？（2）G有多少个生成子图？（3）如果没有任何两个子图同构，则G的子图个数是多少？10.6欧拉图七桥问题问题

寻找走遍哥尼斯堡（KÖnigsberg）城的7座桥，且只许走过每座桥一次，最后又回到原出发点(图论源于游戏)

求解1736年瑞士大数学家欧拉（Leonhard•Euler）发表了关于“哥尼斯堡七桥问题”的论文（图论的第一篇论文）。10.6欧拉图研究方法——抽象用4个字母A、B、C、D代表4个城区,并用7条线表示7座桥。从而将哥尼斯堡七桥问题抽象为一个数学问题:即经过图中每边一次且仅一次的问题。ACDB10.6欧拉图

定义10.11

给定无孤立点图G， 若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路(EulerCircuit),称该图为欧拉图。 若存在一条迹，经过图中每边一次且仅一次，该条路称为欧拉迹(EulerTrail)，称该图为半欧拉图。10.6欧拉图

下图所给出的四个图，哪些是欧拉图？

YNYN10.6欧拉图

定理10.8

图G是欧拉图当且仅当G是连通的且每个结点的度数为偶数。证明先证必要条件：设G是欧拉图。α是G的一个欧拉回路。当α通过G的任一结点v时，α通过关联于v的两条边。若α通过v点k次，则α通过关联于v的2k条边。α是欧拉回路。因此α通过关联于v的2k条边即是关联于v的所有边且互不相同，即v的度数为2k。由v的任意性，必要性得证。

10.6欧拉图

再证充分条件：设G是连通图且所有结点度数为偶数，按如下步骤构造G的欧拉回路。1)从任一结点v0出发，取关联于v0的边(v0，v1)到v1，从v1取关联于v1的未通过的边(v1，v2)到v2，每条边只取一次，依此可得到一条通路。因为G的任意结点v的度数均为偶数，所以通路到达vi≠v0时，必存在关联于vi的未通过的边(vi，vi+1)没有出现在通路上。又G的边为有限条，所以最终总会有某个vk使vk=v0，即得到回路α，α中没有重复边。

10.6欧拉图

2)若α中包含G中所有边，α即为欧拉回路；反之，设G′为从G中去掉α中的边后所剩边及这些边关联的结点组成，H1，H2，…，Hk为G′的k个分图。对任一分图Hi，其所有结点度数均为偶数，Hi与α至少有一个结点重合，设为vi，对Hi从vi出发重复步骤(1)，得到回路α′i=vivi1…vi，将α′i并入α中，对于每个分图H1，…，Hk重复上述过程。

3)若经(2)得到的α包含G中的所有边，则α为欧拉回路；否则重复(2)直到构造出一条包含G中所有边的回路为止。

10.2欧拉图

练习10

判断下列各图，哪些有欧拉路？哪些是欧拉图？（a）(b)(c)10.6欧拉图

推论10.2

连通图G是半欧拉图，当且仅当G恰有两个奇数度结点。且图中的欧拉迹一定始于一个奇数度结点而止于另一个奇数度结点。

10.6欧拉图

例10.25

一笔画问题（笔不离开纸,不重复地画遍纸上图形的所有的边）请问下图中的各图能否一笔画出，如果不能，则需要几笔？

(a)(b)(c)10.6欧拉图

解一笔画问题其实可以转化为判断图中是否具有欧拉回路或欧拉迹的问题。上图的三个图都是连通图，图(a)存在欧拉回路，故可以一笔画出，并回到起始点；图(b)含有两个度数为奇数的结点，存在欧拉迹，也可以一笔画出，但需要从其中一个度数为奇数的结点出发，结束点在另一个度数为奇数的结点；图(c)含有六个奇数度的结点，不能一笔画出。10.6欧拉图

但可以三笔画出，因为可以将六个度数为奇数的结点分为三对，每对之间添加一条边，如下图中所示，虚线为添加的边。这样构造出的新图就存在欧拉回路，可以一笔画出。但其欧拉回路上存在三条添加的但不邻接的边，去除这三条边，则该欧拉回路被截断为三段，故需要三笔画出。

10.6欧拉图

例10.26

设某封闭式小区的路网结构如下图所示，请证明能否设计出一条路线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区大门处。

小区大门10.6欧拉图

解将该小区路网结构图用图论中的图来表示，如下图所示，其中，每个结点代表小区道路的交叉点，每条边代表道路。小区大门位于结点1处。由于所得到的图有两个结点度数为奇数（结点1与2），其它结点度数为偶数，因此，图中不存在欧拉回路，即不能设计出一条路线使得清洁车从小区大门出发完成清扫道路工作并回到出发地。

2110.6欧拉图

例11.27

中国邮路问题

中国邮路问题是我国数学家管梅谷先生在20世纪60年代提出来的。该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？

下面用图论的语言来描述：用图论的语言来描述，即在一个带权图G中，能否找到一条回路C，使C包含G的每条边最少一次且C的长度最短？

10.6欧拉图

该问题求解思路大体包括三个方面：

1)若G没有奇数度结点，则G是欧拉图，于是欧拉回路C是唯一的最小长度的投递路线。

2)若G恰有两个奇数度结点vi和vj，则G具有欧拉迹，且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最短路径。这样，最短邮路问题转化为求vi到vj的欧拉迹和vj到vi的最短通路问题。

3)若G中奇数度结点数多于2，则回路中必须增加更多的重复边(路径）。这时，怎样使重复边的总长度最小？已有定理给出了判定条件，若有兴趣请查阅相关文献。

10.6欧拉图

练习11确定n取怎样的值，n阶完全图Kn为欧拉图？10.6欧拉图

练习12证明：若无向图G是欧拉图，则G中无桥。定义10.15

给定图G，若存在一个环经过图中的每一个结点恰好一次，这个环称作哈密尔顿环（H-环），具有哈密尔顿环的图称为