离散基础及数学 12

1离散数学第九章图的基本概念及其矩阵表示图论（GraphTheory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。2026/9/142图论的起源哥尼斯堡七桥问题：17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条普雷格尔（Pregel）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,b,c,d表示陆地。从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？2026/9/143图论的起源1736年瑞士大数学家列昂哈德•欧拉（LeonhardEuler）解决了这一问题，他用了科学研究中最一般的方法——抽象。用四个字母a,b,c,d表示四块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。2026/9/144图论的起源欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论的创始人。欧拉被称为图论之父，1736年也被称为“图论元年”。

图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。本章将首先讨论图论中的一些基本概念，继之阐述图的基本性质，而后介绍图的矩阵表示方法。2026/9/145主要内容图的基本概念子图和图的运算路径、回路、连通性图的矩阵表示欧拉图哈密尔顿图二部图、平面图网络树基础知识特殊图2026/9/1469.1图的基本概念图是由一些顶点和连接这些顶点的一些边所组成的离散结构。根据连接顶点对的边的种类和数目的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。2026/9/147图的种类

无论是无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。

2026/9/148图的基本概念

共边的点称为点邻接；共点的边称为边邻接。2026/9/149图的基本概念

例：无向图e1连接v1和v2，v1和v2邻接，e1和e2邻接。

2026/9/1410图的基本概念例：有向图v2和v1分别是e1的起点和终点，v2与v1邻接。2026/9/1411图的基本概念

2026/9/1412图的种类例：中国主要城市通讯图2026/9/1413图的种类类型边允许平行边允许自环简单图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是2026/9/1414图的同构从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达相同的结点和边的关联关系。2026/9/1415图的同构实际中，利用图的同构可以研究是否有可能用同样的方式画两个图。例如化学里，表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了。2026/9/1416图的同构

2026/9/1417图的同构

也就是说，两个同构的图有同样多的结点和边，并且映射f保持结点间的邻接关系，映射g保持边之间的邻接关系。

图同构的直观含义，是将其中一个图经过旋转、平移、拉伸等变形后与另一个图完全重合。2026/9/1418图的同构例：求证下图Ｇ和Ｈ同构。

2026/9/1419图的同构例：判断下列两图是否同构。上面两个图是同构的。我们只要构造双射函数f:{a1,b1,c1,d1,e1,f1}→{a2,b2,c2,d2,e2,f2}并且f(a1)=f2

,f(b1)=b2

,f(c1)=c2

f(d1)=d2,f(e1)=a2

,f(f1)=e2

f是个双射函数,并且保持了边的邻接关系．2026/9/1420上面两个图是同构的。我们只要构造双射函数f:{a1,b1,c1,d1,e1,f1}→{a2,b2,c2,d2,e2,f2}并且f(a1)=f2

,f(b1)=b2

,f(c1)=c2

f(d1)=d2,f(e1)=a2

,f(f1)=e2

f是个双射函数,并且保持了边的邻接关系．2026/9/1421图的同构判定两个图是否同构，已知的最好算法具有指数的最坏情形时间复杂度（对图的结点来说）。不过，解决这个问题的线性平均情形时间复杂度的算法已经找到，而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法。一个名叫NAUTY的最佳算法，目前可以在个人电脑上１秒之内判定带有100个结点的两个图是否同构。2026/9/1422图模型图可以用在各种模型里，用于不同的行业。栖息地重叠图：顶点表示物种，若两个物种竞争（他们共享某些食物来源），则用无向边连接表示他们的顶点。2026/9/1423图模型熟人图：可以用模型表示人与人之间的各种关系。顶点表示人，当两个人互相认识时，用一条无向边连接这两个人。据估计，世界上所有人的熟人图有超过60亿个顶点和可能超过1万亿条边。好莱坞图：好莱坞图用顶点表示演员，当两个顶点的演员共同出演一部电影时，就用一条无向边连接这两个顶点。根据无联网电影数据库，在2001年11月，好莱坞图有574724个顶点和超过1600万条边，这些顶点所表示的演员出现在292609部电影中。2026/9/14242026/9/1425图模型循环赛图：每个队其他所有队各有一次的比赛称为循环赛。其中每个顶点表示每个队，若a队击败b队，则有一条从a指向b的有向边。2026/9/1426图模型合作图：合作图可以用来为学术论文的合作者关系建立模型。顶点表示某个文章的某个作者（人），如果两个人合作论文，则用无向边连接这两个人。已经发现在数学研究论文上合作的合作图有超过337000个顶点和496000条边。网络图：互联网可以用有向图来建模，用顶点表示网页，若有从网页a指向网页b的链接，则做一条从a指向b的有向边。网络图几乎是连续变化的，几乎每秒都有新页面产生而又有其他页面被删除。目前网络图有超过10亿个顶点和几百亿条边。许多研究者正在研究网络图的性质，以便更好的理解网络的特性。2026/9/1427图模型优先图与并发处理：通过并发的执行某些语句，计算机程序可能执行的更快。但重要的是，要避免语句执行时还要用到尚未执行语句的结果。语句与前面语句的相关性可以表示成有向图。用顶点表示某个语句，若在a语句执行完之前不能执行b语句，则引出一个从a到b的有向边，这样的图称为优先图。2026/9/1428图模型2026/9/1429度

注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。2026/9/1430度例：计算下图中各结点的度。2026/9/1431度定理：在无向图中，所有节点的度数之和等于边数的2倍。

证：因为每条边给图G带来两度，设图G有m条边，所以图G共有2m度等于图G的所有结点的度数之和。定理：在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。2026/9/1432度例：结点的度。2026/9/1433结点定义：度数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。定理：任何图都有偶数个奇结点。

定义：度为0的结点称为孤立结点，度为1的结点称为端点。2026/9/1434一些特殊的简单图零图：结点都是孤立结点的图称为零图。平凡图：一阶零图称为平凡图。圈图（Cn(n≥3)）：是由n个顶点v1,v2,…,vn以及边{v1,v2},{v2,v3},…,{vn-1,vn},{vn,v1}组成的。2026/9/1435一些特殊的简单图轮图：对n≥３来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图Wn。2026/9/1436一些特殊的简单图正则图：所有结点的度均为自然数d的无向图称为d度正则图。2026/9/1437

一些特殊的简单图注意：完全无向图的任意两个不同结点都邻接。一至五阶完全无向图2026/9/1438一些特殊的简单图注意：完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。

一至三阶完全有向图2026/9/1439一些特殊的简单图

2026/9/1440特殊类型的图的一些应用局域网：在一座大楼里，像小型计算机和个人电脑这样的计算机，以及像打印机这样的外设，可以用局域网来连接。有三种常见的局域网拓扑结构。2026/9/1441用度的概念判断图的同构两个图同构必须满足的必要条件是：(1)顶点个数相同(2)边数相同(3)度数相同的顶点个数相同(4)K度顶点的导出子图同构判定图的同构比较难，但是却可以通过上述四点证明图不同构。2026/9/1442用度的概念判断图的同构例：判断下列两图是否同构。2026/9/1443用度的概念判断图的同构例：判断下列两图是否同构。上面两个图不是同构的，因为左图中２度结点都和两个３度结点相关联，而右图中的２度结点和一个３度结点相关联还和一个２度结点相关联。2026/9/14449.2子图和图的运算

2026/9/1445子图

2026/9/1446子图

例：(b)是(a)的子图、真子图和生成子图，(c)是(a)的由{1,2,3,4}导出的子图。2026/9/1447子图

2026/9/1448图的运算

2026/9/1449图的运算

2026/9/1450图的运算

2026/9/1451图的运算并不是任何两个图都有交、并和环和。如上图

，(a)和(b)没有交和并，因为边e1在(a)中连接v1和v2，而在(b)中连接v2和v3。

2026/9/1452图的运算

(1)证：设G1和G2同为有向图，若同为无向图也可同样证明。

2026/9/1453图的运算

对于存在唯一的可同样证明。2026/9/1454图的运算

2026/9/1455图的运算Ｅ′＝｛g｝,

′={

g,{v1,v3}}2026/9/1456上面的例子中，(a)和(b)分别为G1和G2,则图c,d,e分别是(G1∪

G2)-{v5,v6},(G1∪

G2)-{g,h},G2+E′

′其中Ｅ′＝｛g｝

′={

g,{v1,v3}}图的运算2026/9/14579.3路径、回路和连通性

2026/9/1458

2026/9/1459路径和回路路径和回路例：分析下列无向图

2026/9/1460路径和回路例：分析下列有向图在该有向图中，1c4b1c4是路径，但不是简单路径；1a1c4是简单路径，但不是基本路径。从1a1c4中去掉闭路径1a1就得到基本路径1c4可以看出，从2至1存在多条路径，如果4到2的箭头反向，从1至2就没有路径。

2026/9/1461路径和回路注意：单独一个结点v也是路径，它是长度为0的基本路径。因此，任何结点到其自身总存在路径。在无向图中，若从结点v至结点v'存在路径，则从v'至v必存在路径。而在有向图中，从结点v至v'结点存在路径，而从v'至v却不一定存在路径。设路径和，用P1P2记路径2026/9/1462路径和回路例：“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？人狼羊菜人狼羊人狼菜人羊菜人羊狼菜狼菜羊空2026/9/1463路径和回路例：“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？人狼羊菜人狼羊人狼菜人羊菜人羊狼菜狼菜羊空2026/9/1464路径和回路例：“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？人狼羊菜人狼羊人狼菜人羊菜人羊狼菜狼菜羊空2026/9/1465路径和回路解：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到上图。这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。容易看出，只有两条简单路符合要求，即：（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。对于简单路（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。对于简单路（2）的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；人回来；带羊过河。上述的两种方案都是去4次、回3次，且不会再有比这更少次数的渡河办法了。2026/9/1466路径和回路定理：设v和v'是图G中的结点。如果存在从v至v'的路径，则存在从v至v'的基本路径。

2026/9/1467路径和回路定理：n阶图中的基本路径的长度小于或等于n-1。

证：在任何基本路径中，出现于序列中的各结点都是互不相同的。在长度为l的任何基本路径中，不同的结点数目是l+1。因为集合V仅有n个不同的结点，所以任何基本路径的长度不会大于n-1。对于长度为l的基本循环来说，序列中有l个不同的结点。因为是n阶图，所以任何基本循环的长度，都不会超过n综上所述，在n阶图中，基本路径的长度不会超过n-1。2026/9/1468路径和回路路径可以表示很多图模型中的有用信息：熟人关系图中的通路（最小世界原理）合作图中的通路（数学家的埃德斯数）好莱坞图中的通路（演员的培根数（著名演员凯文.培根））2026/9/1469路径和回路定理：设v是图G的任意结点，G是基本回路或有向基本回路，当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中出现两次外，其余结点和每条边都在该闭路径上恰出现一次。基本回路：回路中除始点和终点出现2次外，其余节点只出现一次。证：见书上。2026/9/1470路径和回路

2026/9/1471路径和回路

2026/9/1472路径和回路例：判断图(a)有没有有向回路。2026/9/1473连通性定义：设v1和v2是图G的结点。如果在G中存在从v1至v2的路径，则称在G中从v1可达v2或v1和v2是连通的，否则称在G中从v1不可达v2。对于图G的结点，用R(v)表示从v可达的全体结点的集合。

注意：在无向图中，若从v1可达v2，则从v2必可达v1；在有向图中，从v1可达v2不能保证从v2必可达v1。无论无向图还是有向图，任何节点到自身都是可达的。

2026/9/1474连通性

2026/9/1475连通性

2026/9/1476连通性

2026/9/1477连通图

2026/9/1478连通图无向图是连通的，当且仅当对于任意，。2026/9/1479连通图由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。

2026/9/1480连通图定义：设G是有向图。(1)如果G中任意两个结点都互相可达，则称G是强连通的。(2)如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。(3)如果G的基础图是连通的，则称G是弱连通的。2026/9/1481子图和分支定义：设G'是G的具有某种性质的子图，并且对于G的具有该性质的任意子图G''，只要G

G

，就有G'=G''，则称G'相对于该性质是G的极大子图。定义：无向图G的极大连通子图称为G的分支。定义：设G是有向图：（1）G的极大强连通子图称为G的强分支。（2）G的极大单向连通子图称为G的单向分支。（3）G的极大弱连通子图称为G的弱分支。2026/9/1482子图和分支定理：连通无向图恰有一个分支。非连通无向图有一个以上分支。定理：强连通（单向连通，弱连通）有向图恰有一个强分支（单向分支，弱分支）；非强连通（非单向连通，非弱连通）有向图有一个以上强分支（单向分支，弱分支）。

2026/9/1483子图和分支例：有4个强分支，即每个结点恰处于一个强分支中，而边不在任何强分支中。G有两个单向分支，即和。显然，处于两个单向分支中，G只有一个弱分支，即其本身。2026/9/1484子图和分支注意：无向图的每个结点和每条边都恰在一个连通分支中；有向图中，并不是每个边都恰在一个强分支中。在简单有向图中，每个结点每条边都恰在一个弱分支中。在简单有向图中，每个结点每条边至少位于一个单向分支中。2026/9/1485由结点集合{v1，v2，v3}，{v4}，{v5}，{v6}和{v7}形成的诱导子图都是强分支;由结点集合{v1，v2，v3，v4，v5}，{v7，v4，v5}和{v6，v5}所成的诱导子图都是单向分支；由结点集合{v1，v2，v3，v4，v5，v6，v7}形成的诱导子图是弱分支。子图和分支2026/9/1486资源分配图下面给出简单有向图的一个应用——资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。2026/9/1487死锁状态对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。2026/9/1488假设条件假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。2026/9/1489分析令Pt

={p1，p2，…，pm}表示计算机系统在时间t的程序集合，Qt

Pt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt={r1，r2，…，rn}是系统在时刻t的资源集合。资源分配图Gt=<Rt，E>是有向图，它表示了时间t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，…，n。<ri，rj>表示有向边，<ri，rj>∈E当且仅当程序pk∈Pt已分配到资源ri且等待资源rj。2026/9/1490分析（续）例如，令Rt={r1，r2，r3，r4}，Qt={p1，p2，p3，p4}。资源分配状态是：p1占用资源r4且请求资源r1，p2占用资源r1且请求资源r2和r3，p3占用资源r2且请求资源r3，p4占用资源r3且请求资源r1和r4，于是，可得到资源分配图Gt=<Rt，E>如下图所示。2026/9/1491前例资源分配图能够证明，在时刻t计算机系统处于死锁状态iff资源分配图Gt中包含强连通分支。2026/9/1492割集有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生带有比原图更多的连通分支的子图，把这样的边叫做割边或者桥。2026/9/1493总结——路径的基本定义

2026/9/1494总结——关于路径的定理

2026/9/1495总结——可达和距离

2026/9/1496总结——连通性定义：如果无向图的任意两个结点都互相可达，则称G是连通的；否则称G是非连通的。定义：设G是有向图(1)如果G中任意两个结点都互相可达，则称G是强连通的。(2)如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。(3)如果G的基础图是连通的，则称G是弱连通的。2026/9/1497总结——子图和分支定义：设G'是G的具有某种性质的子图，并且对于G的具有该性质的任意子图G''，只要G

G

，就有G'=G''，则称G'相对于该性质是G的极大子图。定义：无向图G的极大连通子图称为G的分支。定义：设G是有向图：（1）G的极大强连通子图称为G的强分支。（2）G的极大单向连通子图称为G的单向分支。（3）G的极大弱连通子图称为G的弱分支。2026/9/1498总结——割集有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生带有比原图更多的连通分支的子图，把这样的边叫做割边或者桥。2026/9/14991009.4图的矩阵表示邻接矩阵

则称这样的矩阵A是图G的邻接矩阵。101邻接矩阵图的邻接矩阵不具有唯一性。

给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。102邻接矩阵例：写出下图的邻接矩阵，并计算各个节点的出度和入度。

103邻接矩阵

104邻接矩阵对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化即图的结点所有不同编序实际上仍表示同一个图换句话说，这些结点的不同编序的图都是同构的，并且它们的n!个邻接矩阵都是相似的今后将略去这种由于V中结点编序而引起邻接矩阵的任意性而取该图的任一个邻接矩阵作为该图的矩阵表示105邻接矩阵由邻接矩阵判断有向图的性质：如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。如果给定有向图是反对称的，则对于所有的i和j和i≠j而言，aij=1

蕴含aji=0。邻接矩阵

106107邻接矩阵逆图的邻接矩阵：

108

109

解：简单算法：原矩阵A中，第i行和第j行相交，有几个1，AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。110

111

解：简单算法：原矩阵A中，第i列和第j列相交，有几个1，ATA的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的入度。112邻接矩阵的幂

113邻接矩阵的幂例：114邻接矩阵的幂

115邻接矩阵的幂根据上述定理，可得出结论：

116邻接矩阵的幂

117邻接矩阵的幂解：118可达性矩阵

119可达性矩阵

路径矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；路径矩阵P并不能指明存在的所有路径。120可达性矩阵例：试构成下列有向图的路径矩阵P。

解：设邻接矩阵A=A1。在前面的例中，已经求出过矩阵的幂A2，A3和A4,A5。求出矩阵B5和路径矩阵P如下：

121可达性矩阵注意：对于具有n个结点的图而言，长度为n的路径不可能是基本路径。假定图中的每一个结点，从它本身出发总是可达的，由矩阵Bn-1构成路径矩阵P，或由矩阵Bn构成路径矩阵P，这两种方法都可以采纳。

122布尔矩阵定义：元素或为0或为1的任何矩阵，都称为比特矩阵或布尔矩阵。邻接矩阵也是布尔矩阵第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。123可达性矩阵首先构成矩阵A,A2,…,An，而后由他们构成矩阵Bn，再由矩阵Bn构成路径矩阵P，太麻烦了。为了减少计算工作量，应该设法使得不产生这些不必要的信息。生成路径矩阵P的简单方法：布尔矩阵法。

124可达性矩阵

注意：A(m)表示布尔矩阵，如果从vi到vj有长度为m的路径的话，A(m)矩阵中(i,j)元素为1；Am中(i,j)元素表示从vi到vj的长度为m的路径的个数。125可达性矩阵例：对于下述的有向图来说，试求出矩阵A(2),A(3),A(4)),A(5)和P。

126可达性矩阵

127可达性矩阵

128闭包

计算关系的可传递闭包等同于计算对应关系图的路径矩阵。129可达性矩阵判断强分图

130可达性矩阵判断强分图

1