图与图论.docx
《图与图论.docx》由会员分享，可在线阅读，更多相关《图与图论.docx（26页珍藏版）》请在冰点文库上搜索。
图与图论
第二章图与网络
sl图与图论
图论是比较年轻的一个数学分支．1736年，欧拉写出了第一
篇关于图论的论文．在以后的二百年中，图论的发展比较缓慢．但
自从图论与大量的实际问题相结合。
在物理学，化学，计算机科学，
信息论，运筹学，控制论，社会科学（心理学、教育学等），经济管理
等各种学科中找到了广泛的应用，使图论在近三十年来得到了惊
人的发展．目前在图论领域中形成了两个不同的方向：
抽象图论
和最优化图论．前者着重研究图的性质，后者着重讨论与图有关
的最优化问题．我们主要讨论最优化方面的问题，因此，只对最基
本的图论概念作一些必要的介绍．最优化图论既可以算作图论的
一个研究方向，也可以看作运筹学最优化理论的一个组成部分．
图论的研究对象是图．这里的“图”是一个抽象的数学概念．
为了更好地理解这个概念，我们先讨论一些与国有关的例子．
例一哥尼斯堡七桥问题．
这是由欧拉进行研究的第一个图论问题．十八世纪时，属于
普鲁士的哥尼斯堡（现在叫加里宁格勒，属于苏联）位于普雷格尔
河的两岸，共有七座桥把河的两岸和河中的两个岛连接起来．图
2．1．1就是这七座桥的示意图．该城的居民热衷于解决这样一个
难题：
能不能一次把全部七座桥都走过而不重复．欧拉第一个证
明了这个问题是无解的．他的做法是这样的：
用人B、C、D四个
点分别代表河的两岸和两个岛，每一座桥用连接相应两点的一条
边表示，见图2．1．2．一次走遍七座桥的问题，就化为图2．1．2的一
笔画问题．欧拉给出了一个定理，解决了这个问题，
例二飞行员搭配问题．
第二次世界大战时，英国某飞行队由来自世界各地若干名飞
行员组成，飞行队的每架飞机必须由两名飞行员驾驶．但由于语
言和训练方式等种种原因，某些飞行员适合同机飞行，而某些飞行
员不能同机飞行．当时要解决的问题是怎样搭配飞行员，才能使
配成对的飞行员最多．
这个问题也可以化为图论问题．每个飞行员用一个顶点来表
示．两个飞行员如果可以同机飞行，就在相应顶点之间连一条边，
这样就得到一个图．飞行员搭配问题就可以归结为在图上找一边
集，在这些边两两没有公共顶点的前提下，要求边集中包含的边数
目最多．
例三竞赛的表示问题．
有A、B、CJ四个篮球队进行循环赛，结果如下：
A胜B、C；
B叭0、pZc全负；p胜A／．这个循环赛的结果可以用图2．1．3
来人＼用A、b、c、U四点表币四个队，在进行比赛的自个队之间
一
过一条带箭头的边．箭尾连着胜队，箭头指向负队．从图2．1．3
我们很容易看出各队胜负的情况．利用表示竞赛的图，我们可以
汇入研字各神有夭克贷规叨蜒，w川广旺W旧＊＊二日————”””‘”””“
湘定各队的名次等．
例四渡河问题．
这是个古老的智力游戏问题，但是可以用图论的方法来解决．
有一个人（M），带着狼（W），羊（S），菜o）过河．只有一条
／J、船，人每次过河只能带一样东西．如果人不在，狼就要吃羊，或
学优要吃菜．问人怎样渡河才能保证三样东西都安全带过河去？
留在原岸的所有可能情况一共有16种，我们可以用二进制数表示
（1表示在原岸，0表示带到对岸）
0of0
（2）1101
00of
（1）1110
0000（0）1111
容易看出第3／、7产、9＊2这6种情况是不允许的．现在我
们可以作一个10个点的图．如果通过人一次渡河，可以使两种情
况互相转换，就在这两个顶点之间连一条边，得到的图见图2．1．4．
从图中我们可以找到两种渡河路线：
＠、＠、＠－。
＠、＠、＠、＠、＠
和
＠一＠一③、＠一＠一＠一＠、＠
从这个例子可以看出，用图论的方法虽然可能步骤多些，但
思考方法却比较简单．而且可以发现很多表面上不同问题的相同
实质．
例五再看一个智力测验题是如何用图论来表示的．
老王师傅有两个机灵的徒弟小李和小干．有一天老王师傅需
要一个螺丝，他为了测验两个徒弟看谁更机灵，就把所要螺丝的直
径告诉了小李，把长度告诉了小于，并告诉他们互相不许交谈，看谁
能把他想要的螺丝从工作台上找出来．小李和小于来到工作台一
看，台上共有五种螺丝，规格分别为公3。
10、边4。
10、必5。
10、
g4。
12、矽4X15．小李、小于低头想了一会，又互相看了一下，不
约而同地把手伸向同一种螺丝，把它拿给了老王师傅．老王师傅很
满意．问：
老王师傅要的螺丝是什么规格的了
我们作一个图，三个顶点表示三种直径，g3、矽4、gs，另三个
顶点表示三种长度：
10、12、15·每一种螺丝用图上相应一条边表
示．从图2·1．5中可以看出直径为必3、o5的螺丝只有一种，如
果师傅要的是这两种螺丝中的某一种，小李不用犹豫就能拿起螺
92因此师傅告诉小李的直径一定是政4．同理，师傅告诉小子的
长度一定是10·这个问题是这类
问题中最简单的一个，不用图论
方法、分析起来还不太困难．但也
可以看出，‘用图论方法比较直观
易措．
例六有机化学中，烷烃的分子式为C。
HZ。
＋2，每个烷烃分子
中每个C原子是四价，H原子是一价．每个烷烃分子可以用一个
连通的图来表示：
每个C原子有四条相邻的边，每个H原子只连
接一条边．因此n个C原子之间必须用。
一1条边把它们互相连
接起来．当。
一5时，可能的连接方式有三种（图2．1．6），它们对
应于三种戊烷的同分异构体．用图论的方法，可以给化学中分子
结构的探讨带来很多方便．
例七设J一｛l，2，…，。
｝是个有限集，在J的元素之间定义
了编序“＜”．我们定义：
如果元素6力而且不存在元素正满足
！
＜k力则称j是6的直接后继元，记为6力．作一个图，每个顶
点对应于J的一个元氯如果6＜j，则在6＊之间连接一条带箭
头的直线，箭尾离开i，箭头指向j．设J表示某工程的各道工序，
6力表示工序j必须在工序7完成后才能开始工作．则上述表
示偏序的图就称为该工程的一个工序图．在理论上，偏序图可以
用来研究偏序的各种性质．例如可以用偏序图来研究代数中“格”
的性质．在实践上，工序图对生产实践有很大作用．例如在统筹
方法的研究中，工序图就是不可缺少的工具．
上面的一些例子告诉我们，在各个不同的领域中都可以涉及
到图的概念．因此图论是非常有用的一种数学工具．
上面的例子中，有些图中的边是有方向的，有些图的边是没有
方向的（对称的）．前一种图称为有向图，后一种图称为无向图．下
一节我们将给出图的较为严格的定义．
gZ无向图与有向图
一个无向图G由非空顶点集V和边集E构成，V与E之间满
足一定的对应关系，我们记为G一（厂，E）．
集合V一切1，。
2，…，。
n），集合E一kl，eZ，…，e。
＞都是有限集．
V中的元素称为G的顶点J中的元素称为G的边．
G的每一条边都必须与G的一对顶点相对应，通常记作e。
一（。
；，。
。
）．对无向图来说，这两个顶点的次序是没有关系的．因
此，同一条边也可以记作e。
一（。
j，。
J。
；，。
。
称为e。
的端点，有时
也说e。
与顶点。
；，。
。
关联．如果两条边与同一个顶点关联，我们就
说这两条边是相邻的．同样，如果两个顶点关联同一条边，我们也
说这两个顶点是相邻的．
如果一条边的两个端点是同一个顶点，我们就称它为坏．如
果有两条边，它们的端点是同一对顶点，我们就称它们为平行边或
重边．没有坏也没有平行边的图称为简单图．在大部分情况下，
我们都只考虑简单图．在上节的几个例子中，除了例一的图2．1．2
外＊J｝他例子涉及的图都是简单图．在本书中如果不特别中明，我
们提到的图均指简单图．
一个图可以直观地用平面上的一个图形来表示：
每个顶点用
平面上的一个点表示，而每条边用连接它的端点的一条线来表
示，就象我们在上节中所做的那样．在这里，线是直的还是弯的，
线与线之间是否相交，我们并不关心，我们只关心每一条线连接了
哪两个顶点．很明显，同一个图可以用平面上的不同图形来表示．
图2．2．l的…）和的）表示的是同一个图，但它们表面上看起来差
别很大．
图也可以用矩阵来表示．假设一个图G一（V，E）的顶点个数
6VI—n，边的数目旧I一。
我们可以用一个。
x。
的0－1矩阵
A一（。
；／来表示一个不含有环的图．矩阵的每一行依次对应一个
顶点；第一行对应。
；，第二行对应的，……，相应地每一列对应于
一条边．设边e。
＝（。
；，。
》，则在矩阵的第论列中我们令a；。
一ajjc
二l，第》列的其他元素都为0，用公式表示即：
（1，顶点v；与边e。
关联
〔0，顶点。
；与边e。
不关联
这样得到的0－1矩阵A一（a；／称为图G的关联矩阵．很显
然，如果矩阵的元素可以是2，我们很容易把关联矩阵推广到含有
环的图的情况．
如果不重视边集E中边的次序，我们可以用对称的。
阶0－1
方阵来记录一个图，方阵的每一行和每一列都对应于一个顶点．
元素
＊，顶点。
；与。
。
相邻
〔0，i一j或0；与。
。
不相邻
这样的矩阵称为图G的邻接矩阵．当G不是简单图时，我们
可以用a；。
表示以。
；为端点的环的个数，用a；。
O大力表示以。
；，
。
。
为端点的边的条数．图2．2．1所对应的关联矩阵和邻接矩阵
见图2．2．2和图2．2．3·
81O283C4C5C6676869610Oll
UIZllo0001000－
U，0010110000
0。
01010000100
U400011010010
U。
0000000111
U。
0000011000of
图2．2．2图的关联矩阵
OIPZP3P4P6D6
Ulllllolo7
0，1100111
5’
U。
1100110
D。
！
0
0。
1111100
D。
LOIOIO0
图2．2．3图的邻接矩阵
如果给图的每条边规定一个方向，我们就得到有向图．有向
边又称为弧．有向图通常记为D一（VA）．A是图中的弧的集合，
每一条弧与一对有序的顶点相对应，与无向图类近，也记为a。
二
…；户／．这里山称为a。
的始端，儿称为a。
的末端或终端．a。
称
为山的出弧，称为…的入弧．在无向图的情形下，k；／王与
…。
／＊表示相同的一条边，但在有向图的情形下，它们表示不同
的弧．
把有向图D一（厂，A）的所有弧的方向都去掉，得到的边集用
E表示，就得到与有向图D对应的无向图G一（厂，E）．G称为有
向图D的基本国或底图．利用D的基本图，我们就可以把很多针
对无向图的概念、方法推广到有向图．
用平面上的图形表示有向图的基本方法与无向图是一样的，
只要在每一条弧的末端加一个箭头就可以了．这样的表示方法已
经在上节图2．1．3中用过了．
我们可以把无向图关联矩阵的概念推广到有向图．这里我们
需要进一步区分弧的始端和末端．将关联矩阵元素a；。
的定义修
改如下：
（1，顶点。
；为弧a。
的始端
a。
j一（0，顶点。
；与弧a。
不关联
I—1，顶点。
；为弧a。
的末端
就得到有向国的关联矩阵．
有向图的邻接矩阵的定义与无向图基本一致，有向图D一（厂，
A）的邻接矩阵A＝（au）定义如下：
（1，弧（U；，U卜EA
〔0，弧（。
；，。
J了A
显然，无向图的邻接矩阵是对称的，而有向图的邻接矩阵一般
不对称．
把无向图G一（厂，E）的每一条无向边
e一（。
；，w）三B
代之以一对有向弧：
Q一，i，。
j）EA
a一（。
。
，，；）三A
这样就得到一个相应的有向图D一（V，A）．无向图G与它相应的
有向图D显然有相同的邻接矩阵．这是一种常用的把无向图化为
有向图的方法，这种变换方法的直观意义是很明显的．如果我们
把边看作道路，无向边表示两个方向都能通行的路．有向弧表示
只允许单向通行的路，那末一条双向路显然可以看作两条平行的
单向路．
既有有向弧又有无向边的图称为混合图．如果我们要考虑一
个城市的街道图，有些街道允许双向通行，有些街道是单行线，这
样就得到一个混合图．混合图的情况比较复杂，在本书中一般不
予以讨论．仅在第五章第三节中有一个混合图的实例．
g3i的子图与图的收缩
设G一（VJ）和G’一（V’，E’）都是图，而且VZV’，EZE’，那
末G’称为图G的子图．
子图的概念在实践中是很有用的．例如我们把整个北京市的
街道表示为一个图G，则北京市西城区的街道组成的图就可以看
作图G的一个子图．同样，北京市所有有公交车辆行驶的街道所
组成的图也可看作图G的一个子图
设e是G的一条边，从G中删去e得到的图记为G—e·G一。
显然是G的子图．
设O’一（V’，E’）是O＝（V，E）的子图，如果V’一V，则G’称为
G的支撑子图．O’可看作是从G中删去若干条边，但保留所有的
顶点得到的结果．设EI是E的子集，从图G中删去见得到的图
有时记为G—EI．G的支撑子图都可以记为G—EI的形式．
没有边与之关联的顶点称为图的孤立顶点．一般说来，图的
子因可以看作先从原图中删去若干条边，再删去苦干个孤立顶点
得到的最后结果．
litV是图G的顶点集合，VtV是V的子集．令E’是E中所
有两个端点都在V’中的边集合．即
在一k’卜’＊B；e’一件i，，入。
；＊厂，。
斥W）
则G的子图G’一（厂’，E’）称为山顶点子集V’生成的点导出子图，
记为G’一G（V’）．
记V”一V＼V’．G（V’）可以看作是从G中删去所有V”中的顶
点及所有与V”顶点关联的边所得到的图．从G的邻接矩阵中删
2；所有V”顶点所对应的行和列，就可以得到G（V’）的邻接矩阵．
设E’ME是边集E的子集．所有与E’关联的顶点所组成的
1＼Iii已为V’，则G’一（V’，E’）称为由边子集E’生成的边导出子
图．记为G’一G（E’）．
记E”一E＼E’．G（E’）可以看作是从G一E”中删去所有孤立
顶点所得到的图．从G的关联矩阵中删去所有E”中的边所对应
的列，再从剩下的矩阵中删去元素全为0的行，就得到G（E’）的关
联矩阵．
下面的图2．3．1表示了图的各种子图的一个例子．图2．3．l
（a）表示原图G，O）表示G的一个支撑子图，O）是G的一个点导
出子图，O）是G的一个边导出子图．
图的子图可以说是对图进行删除运算所得的结果．相反地，
可以对图进行加边，加点，以生成新的、更复杂的图，这里就不—一
细说了．
对图的另一种重要运算称为图的收缩．设e6E是图G一（V。
用的任意一条边，e的两个端点为。
’，。
”．我们从原图中删去。
’、
计’，同时增加一个新的顶点y格称为／、d’收缩后产生的人造顶
点）。
于是得到一个新的顶点集厂’：
厂’一（叶切’，V”》U切）
对原来图的边集也要进行改造，即把原来所有与。
’、。
”关联的边
都改为与9关联，原来不与。
’、V”关联的边不变．记改造后的
边集为E’．这样生成的新图G’一（V’，E’）称为图G对于边e的收
缩．用记号G’一O·e来表示．
容易发现，即使O是简单图，G’一G·e也可能产生重边及环，
特别进行多次收缩后更是如此．
G·e的关联矩阵很容易从G的关联矩阵得到．记G的关联矩
阵为A一（a；入e一（vs，。
；），从A中删去第s行和第t行，增加一行
对应于顶点y（无妨将9对应行定在8行），则相应元素修改如下：
11；；．IMS．SMt
U’a．＜O。
，．s，。
s＝S
新的矩阵（a’．。
）即为G·e的关联矩阵A’．A’比A少一行．
图2．3．2表示一个图收缩的结果．加）中的边e一（3，5）收缩。
e变成一个环，原来的边（2，3），（2，5）变成一对平行边．（3，4），
（4，5）也变成一对平行边．收缩后的图见（b）
在有些应用中规定G·e不包括e变成的环．这样，在G·e对
应的关联矩阵中，还要删去e对应的那一列．
G·e的邻接矩阵也可以从G的邻接矩阵修改得到，方法与关
联矩阵类似．
对图的收缩可以有一个很自然的电子线路理论的解释．我们
把图G设想为一个电路图，边e设想为电路的一个支路，当此支路
两端发生短路时，得到的图就是G。
e．
上面讨论的是无向图中一条边的收缩，可以类似地讨论多条
边的收缩及有向图的收缩．
s4i的连通性与图的割集
设G一（V，E）是一个无向图，考虑由O的顶点和边交替组成
的有限序列：
W。
Z。
OIPIO2D263…GkUk
去以7）；；，v；恰好是e；的端点（1＜6＜U，我们称W是一条从。
。
到
i’。
的途径。
。
和。
。
分别称为W的起点和终点，而其他顶点称为
这径W的内部顶点，W中包含的边的数目k称为W的长度．
对于简单图来说，两点之间的边至多一条，因此可以把W简单
写成G的顶点的序列：
W＝DODIUZ…Uk
这里只要求。
；1与。
；相邻．
序列中顶点不重复出现的途径称为路，显然，如果在G中存在
以。
0为起点、。
。
为终点的途径，则一定存在以。
。
为起点，。
。
为终
点的路．
。
0一。
。
且具有正长度的途径称为闭途径．如果只有起点与终
点相同，而其它顶点都不相同，这样的闭途径称为圈，或者回路．对
于圈来说，任何一点都可以看作起点和终点，圈通过每个点都只有
一次。
考虑G中任意一对顶点…，…，如果G中存在一条连接U。
的
路，我们就说。
、。
两点是连通的。
很容易证明，顶点的连通性质在
G的顶点集合V上定义了一个等价关系．它具有反身性、对称性
和传递性．囚此它把顶点集合V划分为W个等价类，即
V＝VIUVZU…UV。
每个等价类中任意两个顶点都是连通的，而不同等价类中的
顶点都是不连通的．同样显然的是，每一条边的一对端点一危属
于同一个等价类．
我们分别考虑广，厂，…，人生成的点导出子图以；），
G（V。
），…，G（V。
），它们分别称为G的一个连通分支．显然G的每
一条边都一定属于G的某一个连通分支．
当G只有一个连通分支时，我们称G是连通的．这时G的任
意两个顶点都可以用一条路来连接．G的每个连通分支显然是连
通的．
与连通性紧密联系的一个概念是割集，在本节的最后一不j，
我们假定G一（厂，E）是一个连通图．
设e是G的一条边．假如O是连通的，但去掉e后，G—e是
不连通的，我们称e是G的割边．
不是所有的图都有割边，割边与图中的圈的概念有密切的联
系．容易证明，图的割边一定不在图的任何圈上，而一条边不是割
边，它一定属于图的某一个圈．
把割边的概念加以推广，就得到边割的概念．设E’是E的子
集，如果G连通而G—E’不连通，E’就称为G的一个边割．G的
极小边割称为G的割集（所谓E’是G的极小边割，就是指E’是O
的边割，但E’的任何真子集都不是G的边割）。
同样显然的是：
6
的割边是一个割集，而且G的任何边割部至少包含一个G的割集．
升，OM上，人们往往不严格地区分边割和割集，但通常不难从
上下又把它们区别开来．
没J和P是图G一（V，E）的顶点集合V的一个非空对分，即
S问j一一、o，SUT—V．S？
都非空，我们把E中所有一个端点属
于S，另一个端点属于T的边组成的集合记为
CS，利一（刮。
三E，e一（。
；，。
J，，；三凡。
。
三T）
我们不它为0的［S，利边割。
显然O的「尸，＊」边割一定是0的边
；礼因为G一【ST」一定不连通〔S，Ti边割与割集之间的关系可
以由下【5的定理来保证．
定理2．4．l设G是连通图，则G的C凡Ti边割是割集，当且
仅当名和T的点导出子图以），O叮）都是连通的。
这个定理的证明从定义出发立即能得到，我们把它留给读者
作非司．这个定理的最大作用是给出了割集构造的一个明确的
刻义
下面再介绍一个「凡购边割与圈的关系的定理：
定理2．4．2设C和「S，Ti分别为图G的圈和边割，则
ICn［S，T］Z。
0（mod2）
．这个定理的证明也留给读者．
关于连通、路、圈、割集的定义可以直接推广到有向图、由干
有向图的弧有方向，我们可以进一步定义有向路、有向圈等等．读
者可以自行给出它们的定义。
ss几类重要的囹和网络
本节介绍一些重要的图类．
只有顶点没有边的图称为空图．设简单图G一（VE）的顶点
数0V3—n．如果G的任意一对顶点都相邻，则G称为n阶完全
图，用符号K。
来表示．不难看出K。
共有。
（n—1）／2条边．
记EI／是完全图K。
＝（厂，E）的边集E的一个剖分，即EIU
EZ—E，E；nEZ一①．我们可以构造两个简单图：
GI一（厂，EI），GZ
一（厂，E。
），称它们互为补图．显然。
个顶点的空图可以看作是。
阶完全国的补图．
设。
是图G一（厂，E）的一个顶点，与0关联的G的边数称为。
在G中的度数，记为d。
（。
）．在不引起混淆的情况下，可以简单地
记为d（。
）。
是G的孤立点，就相当于d（。
）一0．G的顶点的最
大度数和最小度数通常分别记为
A”）一1。
GXd。
。
）
veV
和
6（G。
mind。
。
）
tlCV
显然，对。
阶的简单图来说，A（G）＜n—1．
满足A（G）一6（G）一k的图称为尼正则图．容易看出Kn是
。
一1正则图，而且简单正则国的补图也是正则图．所有点的度数
之和与图的边数有一个很明显的简单关系，我们把它写成下面的
定理．
定理2．5．二图G一（厂用的顶点度数与边数满足下面的
等大：
Zd（。
）＝2旧I
关于有向图也有一个与定理2．5．1类似的结果．
有向图D一（厂，A）中，顶点O所关联的出弧的条数称为0在
D中的出度，记为d。
M。
所关联的人弧的条数称为。
在D中般
人度，记为db（…．出度和人度也可以简单记为d“（。
）和d－（…．
定理2．5．2在有向图D一（厂，A）中
Zd“（V一Zd－。
）＝Al
U6F’U6V
我们再来介绍一类在理论卜和空降卜都根责西始回去。
＿。
＿，J；J。
j－。
l＿。
＿＿＿卜b二二luW人法J二创川仪】色安的囹．如呆欧
G的顶点集合V存在一个刻分8和T．一的＿的。
＿。
，。
＿一
个端点属于S，而另一个端点属于T，G就称为M分图（有的书也
称为瑞图）．二分图有时也记为
G一（ST，E）
注意边集E恰是二分图G的［S，Ti边割．因此二分图的另一
个等价定义是：
S和J的点导出子图G（S），G瞩）都是空图．
在本章第一节所举的图的例子中，图2．1．4和图2．1．5都是
二分图．仔细研究一下可以发现，图2．1．6也是二分图．由此可
以看出二分图的重要性．下面给出刻划二分图特征的～个定理：
定理2．5．3G是二分图，当且仅当G不含有长度为奇效的
圈（简称为奇圈）．
这个足理的证明比前面几个字及西路十四排一此士祆旦。
—。
＿＿。
。
＿·。
。
。
。
Dulw／LIo6贵阳N山地一竺．王安是在
足理的充分性排明中．＄olg》＆＄④0xA＄。
。
。
。
，。
t、。
。
，；；
”—””’””“刀‘土—w个，抗们J希晏报摊图G不含奇圈的条件，构造出
集合J和T来．在假宁oi＄涌（tMt3Malll；＿，、；——。
。
。
。
的一个顶点地根据其它顶点至顶占。
的是板路仁冷的支烟M—
以把顶点进行剖分，这样的剖分就满足我们的要求．详细的证明
升级会员 