离散数学图论

第八章图论图论起源：哥尼斯堡七桥问题：能否从一处出发，经过七座桥一次，又回到出发点？图论的应用非常广泛，主要有运筹学、网络理论、信息论、控制论、及计算机科学等等。世界数学难题——哥尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥,将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。

这就是哥尼斯堡七桥问题，一个著名的图论问题。

1727年在欧拉20岁的时候，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多人困惑的问题。欧拉并没有跑到哥尼斯堡去走走。他把这个难题化成了这样的问题来看：把二岸和小岛缩成一点，桥化为边，于是“七桥问题”就等价于下图中所画图形的一笔画问题了，这个图如果能够一笔画成的话，对应的“七桥问题”也就解决了。哥尼斯堡七桥问题

城的四个陆地部分分别表以A，B（大岛），C，D（小岛)，将陆地设想为图的顶点，把桥画成相应的边，

则问题等价于在图中从某一顶点出发找一条回径，通过它的每条边一次且仅一次，并回到原顶点。（你能否看出，此问题无解，即这样的走法不存在呢？）ABCD主要内容

1.图的基本概念2.路径与回路3.图的矩阵表示4.几种特殊的图5.无向树,有向树8.1图的基本概念

定义1

一个图G是一个三重组<V,E,

>，其中V是图G的顶点集合，E是图G的边集合，

是从边集E到顶点偶对集合的函数，即边与点的对应关系。例1设G=<V,E,

>,其中:V={a,b,c,d,e},E={e1,e2,e3,e4,e5,e6,e7}(e1)={a,d},(e2)={c,d},(e3)={b,d}(e4)={a,c},(e5)={b,c},(e6)={a,d},(e7)={b,b}则G可用图表示为:acbde1e2e3e4e5e6e7e基本概念若边e对应的是有序偶<a,b>，则称e为有向边。在画图形时，有向边<a,b>,就画一条从a出发箭头指向b的弧。有向边e称为弧，a叫弧e的起点，b叫弧e的终点，统称为端点。称e关联于顶点a和b；称a和b是邻接的。若边e对应的是无序偶{a,b},则称e为无向边。同样称a,b是端点，称e关联于顶点a和b；称a和b是邻接的。每一条边都是有向边的图，称为有向图。每条边都是无向边的图，称为无向图。

图中不与任何顶点邻接的点称为孤立点。全都是孤立点的图称为零图。关联于一个顶点的边称为自回路，也称为自圈。

在有向图中，若同始点和同终点的边多于一条，则这几条边称为平行边。

没有平行边和自圈的图称为：简单图。

在无向图中，两顶点间若多于一条边，则称这几条边为平行边。图G中，顶点的个数称为图G的阶

基本概念

定义2对图G的每条边都赋以一个数值的图，称为加权图。定义3

在有向图中，对于顶点v，以v为起点的边的数目，称为v的出度（引出次数）。记为：deg+(v),以v为终点的边的数目称为v的入度（引入次数）,记为：deg-(v)，

v的出度和入度之和称为v的度。记为deg(v)。即deg(v)=deg+(v)+deg-(v)

对于无向图，顶点v的度就是与v相关联的边的条数。孤立点的度为0.

约定：

含有n个顶点和m条边的图，记为（n,m）图。

定理1

设G是有m条边，则它的所有顶点的度之和为2m基本概念定理2

在图中，度为奇数的顶点有偶数个。定义4

各顶点的度都相同的图，称为正则图。各顶点的度都为k的图，称为k度正则图。对于n阶无向图，n-1度正则图称为n阶无向完全图。简称为n阶完全图。记为：Kn

（在完全图中，每两个顶点之间都有边相连）对于n阶有向图，若每个顶点的出度和入度都为n-1,则称之为n阶有向完全图。

图的同构

对于两个图G和G

,如果它们的顶点之间存在一一对应关系，而且这种关系保持了两顶点间的邻接关系（在有向图中，还保持了边的方向）和边的重数，则这两个图是同构的。同构的图除了点和边的名称不同外，实际上代表同样的组织结构。由于图形的顶点位置和连线长度都可任意选择，同一个图可能画出不同的形状来，因而引出图同构的概念。如下面两个图同构:abcdacbd图的运算

图的常见运算有并、交、差、环和，补图等。定义如下：定义5

设图G1=<V1,E1>和图G2=<V2,E2>。（1）G1与G2的并：记为:

G1∪G2=<V1∪V2,E1∪E2>（2）

G1与G2的交：记为：

G1∩G2=<V1∩V2,E1∩E2>（3）

G1与G2的差：定义为图：G3=<V3,E3>,E3=E1-E2,V3=(V1-V2)∪{E3中边与V3所关联的点}。记为：G1-G2（4）G1与G2的环和，记为

G1

G2=G1∪G2-G1∩G2子图与补图

定义6

设G=<V,E>,G

=<V

,E

>都是图，如果非空集合V

V或E

E，则称G

是G的子图；如果V

V

或E

E，则称G

是G的真子图；如果V

=V,E

E,则称G

是G的生成子图。

(3)为(1)的生成子图，(2)为(1)的真子图。

123补图定义7

设图G=<V,E>,若G是n阶无向图，则G的补图为：Kn

G。即为n阶完全无向图与G的差。若G是n阶有向图，则G的补图为：n阶有向完全图与G的差。

（这一节介绍了图的一些基本概念，如图的定义，图中顶点的度，图的所有顶点的度为边的2倍，且一个图中有偶数个奇顶点，简单图等的定义，图的运算，子图，补图的一些概念。要掌握这些简单的定义）8.2路径与回路

这一节将要引入路径的概念，以后还要引用简单路径、基本路径、简单回路、基本回路、及路径的长度概念及与路径相关的连通图，连通子图，及在有向图中的单向连通，强连通与弱连通的概念。求加权图中的最短路径的算法也是本节的一个重点。路径的基本概念定义1

给定图G=<V,E>，设G中顶点和边的交替序列：

=

0e1

1e2

2…el

l

若

满足：

i-1和

i是ei的端点(i=1,2,…l),则称之为从顶点

0到

l的路径，

0和

l分别称为此路径的起点和终点，

中边的数目称为

的长度。若

中的所有边互不相同，则称为简单路径。若

中所有顶点

0,

1,

2,…,

l互不相同，则称此路为径为基本路径。

当

0=

l时，

称为回路。若回路中所有的边互不相同，则称此回路为简单回路。通过各顶点不超过一次的回路为基本回路。路径长度定义2

路径P中所含边的条数称为路径P的长度。

长度为0的路径就是单独的点。定理：在一个具有n个顶点的简单图中，如果存在v1到v2的路径，则存在从v1到v2的长度不大于n-1的基本路径。如果从v1到v2的路径P不是基本路径，即表示里边有重复的点，那么删去P中所有的回路，直到没有重复点为止，即变为基本路径。而每个点至多在这基本路径中出现一次。所以这基本路径的长度至多为n-1.

设vi,vj是两个不同顶点，若存在从vi到vj的路径，则称vi,vj是连接的，称连接的所有路径中长度最小者为vi,vj的最短路径，最短路径的长度称为vi,vj之间的距离，记为d(vi,vj)，若不存在连接的路径时，定义d(vi,vj)=

连通图

定义3

设G=<V,E>，且vi,vj

V.如果存在从vi到vj的路径，则称从vi可达vj.(因vi

可看作长度为0的路径，即从vi可达vi,即任何顶点都是自己可达)。定义4在无向图中，如果任何两个顶点都可达，则称之为连通图。如果G的子图是连通图，称之为连通子图。一个无向图如果不是连通图，就是由若干个连通子图构成。定义5在有向图G中，如果在任两个顶点中，存在从一个顶点到另一个顶点的路径，则称图G为单向连通的。如果在G中，任何两个顶点都互相可达，则称G为强连通的。如果它的基础图（底图）是连通的，则称之为弱连通的。显然，强连通的，也是单向连通的，也是弱连通的。强分图（单向分图，弱分图）定义6在有向图G=<V,E>中，G′是G的子图，若G′是强连通的（单向连通的，弱连通的），且没有包含G′的更大的强连通子图（单向连通子图，弱连通子图），则称G′是G的强分图（单向分图，弱分图）图的连通性的应用有向图的连通性问题在计算机中是经常用到的。例1

此例说明图的连通性在计算机中的应用设At={P1,P2,P3,P4}是t时刻运行的程序集合，Rt={r1,r2,r3,r4}是t时刻所需的资源集合。

P1据有r4且请求资源r1;P2据有r1且请求资源r2和r3P3据有r2且请求资源r3，P4据有资源r3且请求资源r1和r4

则资源分配图可表示如下：r3r2r1r4P2P1P41P31P4P2

显然，当且仅当分配图Gt包含多于一个顶点的强分图时，计算机系统在t时刻死锁。显然图示状态是死锁状态。以后我们可用矩阵方法来识别是否包含多于一个顶点的强分图。求加权图中的最短路径问题

定义7

设图G=<V,E,

>。若W:E

R

,则称<G,W>为加权图。若e∈E,称W(e)为边e的加权长度。路径中所有边的加权长度之和称为该路径的加权长度。从顶点v到顶点s的路径中加权长度最小者称为从v到s的最短路径。最短路径的加权长度为从v到s的加权距离。若从v不可达s,则称它们的加权距离为

Dijkstra算法Dijkstra给出了求从顶点s至顶点t的加权距离的如下算法：1）若v≠s,则

（v）=

,否则

（v）=0；T=V（顶点集合）

//初如化顶点的值,初如化集合T

2)在T中寻找

值最小的顶点u.3）如果u=t,则算法结束。4)考虑在集合T中且与u邻接的顶点v,若

（v）>

（u）+W(e)(e连接u和v)，则修改顶点v的

值。即

（v）=

（u）+W(e)(要考虑所有在T中又与u邻接的点)5）T=T-{u}(不再考虑顶点u)；转向2

当算法结束时，

（t）即为从s到t的加权距离。

Zhengjin,CentralSouthUniversity23Zhengjin,CentralSouthUniversity24Zhengjin,CentralSouthUniversity25Zhengjin,CentralSouthUniversity26Zhengjin,CentralSouthUniversity27Zhengjin,CentralSouthUniversity28Zhengjin,CentralSouthUniversity29Zhengjin,CentralSouthUniversity30Zhengjin,CentralSouthUniversity31Zhengjin,CentralSouthUniversity32Zhengjin,CentralSouthUniversity338.3图的矩阵表示

定义1设G=<V,E>是无向图，且无平行边，其中V={v1,v2,…,vn},定义一个n

n的矩阵A,其中各元素aij为：

1如果<vi,vj>

E

aij=0如果<vi,vj>

E

称这样的矩阵为图G的邻接矩阵。（即若两点间有边相连，则对应的为1，无边相连，则对应的为0）

图的邻接矩阵设图G如右图所示，则其邻接矩阵为：A=bde1e2e3e4e5e6e7eac有向图的矩阵表示与无向图相对应，有向图也有类似的矩阵表示。如右图：v2v3v4v1A=有向图的邻接和可达性矩阵性质1A不一定是对称矩阵。性质2A的第i行元素之和为:deg+(vi)，的第j列元素之和为deg-(vj).定义设v1,v2,…,vn是简单有向图的顶点，则称P是G的可达矩阵，其中：Pij=

1若vi,vj可达0,若vi,vj不可达有向图的可达性矩阵特点性质1P是以0，1为元素的矩阵，其主对角线上的元素全为1，但不一定是对称的。性质2设A是G的邻接矩阵，则(还记得关系的幂运算吗?！！)

P=A0∨A1∨…∨An-1性质3

（1）P的元素全为1是为强连通的充分必要条件（2）P

PT的元素全为1是为单向连通的充分必要条件。（3）可从P∧PT中是否含有方块矩阵（全为1的小矩阵），判断图D中是否含有强分图。关于有向图的连通性，对于具体的图直接从图形进行判定。

8.4几种特殊图1欧拉图

2哈密顿图

3

二部图

4

平面图

欧拉图

定义1

设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉路径；如果欧拉路径还是回路，则称此回路为欧拉回路。具有欧拉回路的无向图G称为欧拉图。定义2

设D是连通有向图，则称经过G的每条边一次并且仅一次的有向路径为有向欧拉路径；如果有向欧拉路径是有向回路，则称此有向回路为有向欧拉回路。具有有向欧拉回路的有向图D称为有向欧拉图。

例1

判断下列图形是否为欧拉图或有向欧拉图。（1）为欧拉图。abcdfecfgha为欧拉回路。（2）中存在有向欧拉路径abcdac，没有有向欧拉回路，非有向欧拉图。

(3）为有向欧拉图。abcacda为有向欧拉回路。

abcdefghbacdabcd欧拉路径与欧拉图的充要条件

定理1

无向图G有欧拉路径的充分必要条件是：G为连通图，并且G仅有两个奇度顶点或者无奇度顶点。从定理可见：（1）当G是仅有两个奇度顶点的连通图时，G的欧拉路径必以此两个顶点为端点。（2）当G是无奇度顶点的连通图时，G必有欧拉回路。

推论

G为欧拉图的充分必要条件是：G为无奇度顶点的连通图。

有向欧拉图定理2

有向图D有有向欧拉路径的充分必要条件：是D为连通图，并且所有顶点的出度与入度都相等，或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个的出度与入度之差为1，另一个出度与入度之差为-1．

推论有向图D为有向欧拉图的充分必要条件是D为连通图，并且所有顶点的出度和入度都相等。

哈密尔顿图定义1

设G是无向图，则称经过每个顶点一次且仅一次的路径为哈密尔顿路径。如果哈密尔顿路径是回路，则称其为哈密尔顿回路。具有哈密尔顿回路的图，称为哈密尔顿图。由定义可知：具有哈密尔顿路径的图是连通的；哈密尔顿路径是基本路径；（点不重复）哈密尔顿回路是基本回路。

注：虽然哈密尔顿回路问题与欧拉回路问题在形式上极为相似，但是，到目前为止，人们还没有找到哈密尔顿图（或有向哈密尔顿图）的充分必要条件．

欧拉图和哈密尔顿图小结

对于邮路问题：如果想要通过每个街道一次，则最好走一条欧拉路（遍历各边且一次的简单路径）如果想要通过每个收发点一次，则最好走一条哈密顿路（遍历各点且一次的基本路径）。/link?url=lzL7dG8i0vt-D11Imb5dCfjNelrMimxDIXdPQTZVkVyNAxyMpzbi83oydJW621nGr98v9CcH2lt1LNMVKp0QVik8buxEyqBayYeaNyoser7

（图模型s，珠子问题)二部图（二分图）定义1

设无向图G=<V,E>的顶点集合V可以划分成两个子集V1和V2,使得Vi中的任何两个顶点都不邻接（i=1,2）,则称G为二部图，V1和V2称为G的互补顶点子集。即二部图G中的每一条边e的一个端点在V1中，另一个端点在V2中。

显然，二部图不会有自圈。如下图所示，都是二部图定理1无向图G=<V,E>为二部图的充分必要条件为：G中所有回路的长度均为偶数。证明：必要性。设G中有回路C:(v0,v1,v2,…,vk,v0)。因G是二部图，设v0在V1中，则v1,v3,v5，…,vk（k为奇数）在V2中，而C的长度为k+1,故C的长度为偶数。

充分性。设G是连通图（否则，对其连通子图证明）。设G只含偶数长度的回路。任取V中顶点v0,定义V1,V2如下：V1={v

v到v0的距离为偶数}V2=V-V1假设存在一条边（vi,vj）,而vi,vj同属于V1,或者同属于V2.假设都在V1中，（设在V2中也可类似证明），则从vi到v0的距离为偶数，从vj到v0的距离也为偶数，所以回路（v0,…,vi,vj,…,v0）的长度为奇数。这与已知相矛盾，所以假设不成立，即V1,V2就是满足条件的划分。所以G是二部图。平面图定义1一个无向图G=<V,E>，如果能把它图示在一个平面上，边与边只在顶点处相交的图称为平面图。否则称G为非平面图。下图所示为平面图（因可将其表示成右图形式，边与边只要端点处相交）

K3,3和K5都是非平面图平面图的面定义2:在平面上画出的边不在非顶点处相交的平面图G的图形称为G的平面表示。在平面图G的一个平面表示中，以G的边为边界的连通区域称为G的该平面表示的面。如果面的面积是有限的，则称为有限面，如果面的面积是无限的，则称为无限面。显然，平面图只有一个无限面。

右图中有4个面（其中有一个无限面）。平面图的欧拉公式

一个连通平面图的任何平面表示的面的数目都是一样的，它是图本身固有的性质。定理1

（欧拉公式）若n阶连通平面图G有m条边，它的一个平面表示有f个面，则

f=m-n+2

即：面数=边数-顶点数+2可用数学归纳法。

证明:（对边数m进行归纳）

(1)当m=0和m=1时，定理显然成立。

(2)假设定理对m–1条边的任何连通平面图均成立,设G是一具有n个顶点，m条边，f个面的连通平面图（m≥2）若G中没有环：则G是一棵树，f=1，且m=n–1，于是

n–m+f=n–（n–1）+1=2,即f=m-n+2。若G中有环，则去掉G的任一环上的一条边e，剩下的图G

仍连通，有n个顶点，f–1个面，m–1条边，由归纳假设G

中欧拉公式成立。因此n–（m–1）+（f–1）=2，即n–m+f=2即f=m-n+2。定理2

在n3的任何连通平面简单(n,m)图中成立

m3n-6证明：设(n,m)中有f个面(f=m-n+2),由于是简单图，所以每个面至少由3条边围成。而每一条边至多在两个面的边界中，因此2m3f

即2m3(m-n+2)

所以m3n-6

对于非连通图也有此结论成立。平面图的对偶图定义1给定平面图G的一个平面表示，在其每个面内取一点，如果两个面有m条公共边，则用m条线连接这两个面内取定的点，并使其分别与m条公共边相交，由这些点和连线组成的图形，称为G的该平面表示的对偶图。例：图G对偶图应用一例例：若将平面分为k个面，使每两个面都相邻，问k最大是多少？解：平面分为k个面，其平面图图形设为G,由于每两个面都相邻，则G的对偶图中有k个点，且每两个点之间都有连线，即G的对偶图是一个完全图。由于平面图的对偶图也是平面图，但我们知道，5阶完全图（K5）就是非平面图，所以k要小于5.但K4是平面图。所以k最大为4.

8.5无向树

定义1

不包含回路的连通图称为树，记为T．树是连通的且不包含回路的无向图．两棵以上的树称为森林.设T是树，度数为1的顶点称为树叶，度数大于等于2的顶点称为分枝点．由定义可知：（1）一个孤立点是一棵树。（2）树T中无自圈无平行边．（3）阶大于1的树是二部图。

树的性质性质1：设u,v是树T中的两个不同顶点，则u,v之间有且仅有一条路径，而且这条路径是基本路径．性质2:设u,v是T的两个顶点．如果u,v不邻接，则在T中添加边后(u,v)所得的图有且仅有一条回路，而且这条回路是基本回路．性质3：从树T中删除任意一条边后所得的图是不连通的．

性质4:设树T的顶点数为n（n＞2），则T至少有两片树叶（度为1的点）

性质5：

设T是有n个点，m条边的树，则m＝n—1证明：用关于n的数学归纳法证明。当n=1时，显然G没有边，即m=0假设对任意的k

2,当n<k时都有m=n-1.当n=k时，任取G中的一条边e，由G-e是非连通图知，G-e恰有两个分支G1和G2,设G1和G2分别有n1和n2个顶点，则根据归纳假设，G1和G2分别有n1-1和n2-1条边，而图G的边数为(n1-1)+(n2-1)+1=n1+n2-1=n-1即当n=k时，结论也成立。所以结论成立。

例1

设树T中有1个3度顶点，2个2度顶点，其余结点都是树叶，问T中有几片树叶？解设T有y片树叶，则

13+22+1y=2(1+2+y-1)

解此方程得y=3．即T有3片树叶．例2

设树T中有7片树叶，3个3度顶点，其余都是4度顶点，问T中有几个4度顶点？设T已有x个4度顶点，则4x+33+71=2(7+3+x-1)解此方程得x=1，即T的4度顶点只有1个

连通图的生成树定义2设G是连通图，如果T是G的生成子图，且是树，则称T是G的生成树,G的在T中的边称为树枝，不在T中的边称为T的弦.根据定义可得：

定理1

任何连通图G都至少有一颗生成树.在生成树问题中，我们主要考虑加权图的最小生成树（即求边的权值之和为最小的生成树）。求最小生成树（MST）的避圈法设图G是有m条边的n阶连通无向图，我们要求加权图<G,W>的最小生成树。首先：将G的m条边按