第4篇-图论之基本概念

1、第4篇 图论 主讲人：任长安 计算机与信息科学系 2009.07,引言,图论是在民间游戏当中孕育和诞生的，作为数学的一个分支已有两百多年的历史。图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonhard Euler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。哥尼斯堡是东普鲁士的一座城，流经该城的Pregel河将城市分为彼此之间由七座桥相连接的四个部分，如图1（a）所示。当时，一些好奇的市民尝试这样一个有趣的游戏：从一个地方出发，通过每座桥一次且仅一次，最后回到出发地，这样的路线是否存在？,引言,欧拉在论文中给出了解决这个问题的很容易理解的简单证明，他将这个问题转化为图

2、1（b）所示的问题，将被河流分割的城市四个部分用点从A、B、C、D来表示，而将七座桥用称为边的线段来表示，于是问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题，当时来说，这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为“图论之父”。,引言,图1 哥尼斯堡七桥问题,引言,在欧拉之后，图论得到了迅速的发展。一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出

3、现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig) 发表了第一部集图论二百年研究成果于一书的图论专著有限图与无限图理论，这是现代图论发展的里程碑，标志着图论已经作为一门独立的学科。,引言,现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；

4、图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。现在，它已成为系统科学、管理科学、运筹学、化学、经济学、网络理论、信息论、控制论等学科和理论研究中的重要数学工具，受到数学界和工程技术界越来越多广泛的重视。,主要内容,1 图的基本概念及表示 2 图的应用 3 树,第8章 图的基本概念及表示,图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。我们所讨论的图（graph）与人们通常所熟悉的图，例如圆、椭圆、函数图标等是不相同的。图论中所谓的图是指某类具体离散事物集合和该集合中的每对事物间以某种

5、方式相联系的数学模型。如果我们用点表示具体事物，用连线表示一对具体事物之间的联系，那么，一个图就是由一个表示具体事物的点的集合和表示事物之间联系的一些线的集合所构成，至于点的位置和连线的长短曲直是无关紧要的。 本章主要介绍图论的基本概念、图的运算、连通性以及图的矩阵表示。,第8章 图的基本概念及表示,主要内容： 8.1 图的基本概念 8.2 图的运算 8.3 路径与图的连通性 8.4 图的矩阵表示,8.1 图的基本概念,例8.1 时间安排问题。某大学计算机学院的某教研组共有10名教师，他们分别参加7个班级的讨论课，每个班级可能同时需要多位教师参加，有的教师可能需要参加多个班级的讨论，每个班级必

6、须单独开展讨论课。参加各个班级讨论课的教师情况如下（数字为教师编号）： c1=1，2，3，c2=1，3，4，5，c3=2，5，6，7，c4=2，6，7，c5=4，7，8，9，c6=8，9，10，c7=1，3，9，10。 这样，一位教师如果给多个班级都授课，则在讨论课时间安排方面则不能冲突，如教师1不能同时参加班级c1与班级c2的讨论课。这种情况可以用图8.1直观地表示。,8.1 图的基本概念,图8.1 讨论课时间安排图,在图8.1中，共用了7个小圆圈来表示班级，圆圈之间的线段表示存在同一个教师参加该二班级的讨论课，这样就不能安排该二班级同时开展讨论课。显然，这就给上述问题构建了一个直观的图的模

7、型。,8.1 图的基本概念,如从图中容易看到：c1代表的班级不能与c2、c7代表的班级同时开展讨论课，因此，至少需要安排三个时段，而c1与c5，c6间没有边存在，因此c5、c6均可以与c1在同一时段开展讨论，但c5、c6之间有边存在，故只能c5、c6之一与c1可以在同一时段开展讨论课，等等，依此类推，可以得到各班级开展讨论课时段的安排，但显然，这是比较繁琐的工作，因此，需要一些图的术语来描述这个问题，而且如果能根据图的一些相关性质来设计一个好的算法才是最佳的选择。,8.1 图的基本概念,一、图的定义 定义8.1 由集合V和E组成的数学结构G=叫图。其中V=v1，v2，vn为结点的集合；E的元素

8、为 (vi,vj )，称为有向边(无向边)。并称vi与vj相关联(相邻)，若E，则称vi为始点，vj为终点。 由无向边构成的图称为无向图，由有向边构成的图称为有向图。,8.1 图的基本概念,定义8.2 如果两个结点之间有多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相邻结点a，b间平行边的条数称为边的重数。含有平行边或环的图称为多重图，不含平行边和环的图称为简单图。,8.1 图的基本概念,二、结点的度数 定义8.3 设图G是有向图，v是图G中的结点，以v为始点的有向边的条数称为v的出度，记个deg(v)；以v为终点的有向边的条数称为v的入度，记作deg(v)；结点v的度为出度

9、和入度之和，记为deg(v) 。 例如，计算图8.3中结点v的度数。 解： v的入度deg(v)=2， v的出度deg(v)=3， v的度deg(v)=5,图 8.3,8.1 图的基本概念,定义8.4 设图G是无向图，v是图G中的结点，所有与v关联的边的条数，称为点v的度数，记作deg(v)。 例如，计算图8.4中结点v的度数。 解：v的度deg(v)=4,图 8.4,8.1 图的基本概念,定理8.1 在任何有向图中，所有结点的入度之和等于所有结点出度之和。 证明：因为一条边产生一个入度和出度。 所以所有结点的入度之和等于出度之和(等于边数)。 定理8.2 在任何图中，所有结点的度数之和一定等

10、于边数的2倍。 证明：因为任何一条边都产生2个度，所以有 。,8.1 图的基本概念,定理8.3 在任何图中，度数为奇数的结点个数必为偶数。 证明：设V1和V2分别是G中偶数度数和奇数度数的结点集。 由于 是偶数之和，必为偶数。 而2|E|是偶数，故得 是偶数，即|V2|是偶数。,8.1 图的基本概念,三、完全图 定义8.5 对于简单无向图G，若G的任意两个结点之间都有边相连，称G为完全图，记为Kn，n为结点数。 例如，k3，k4，k5如图8.5所示， Kn的边数为：,图8.5,8.1 图的基本概念,定义8.6 对于有向图G，若看成无向图是完全图，则称为有向完全图。 例如，图8.6显示的就是一个

11、有向完全图。 例8.1 求解下列各题： 1) 无向完全图Kn有28条边， 则它的顶点数n为多少？ 2) 图G的度数列为2，2，3，5，6，则边数m为多少? 3) 图G有12条边，度数为3的顶点有6个，余者度数均小于 3，问G至少由几个顶点？,图 8.6,8.1 图的基本概念,1）因为无向完全图Kn的边数 ，故n=8。 2) 2m=deg(v)=2+2+3+5+6=18，可得m=9。 3)由deg(v)=2m=24，度数为3的顶点有6个占去18度，还有6度由其余顶点占有，而由题意，其余顶点的度数可为0，1，2，当均为2时所用顶点数最少，所以应有3个顶点占有此6度，即G中至少有9个顶点。,8.1

12、图的基本概念,例8.2证明在n（n2）个人的团体中，总有两个人在此团体中恰好有相同个数的朋友。 分析：以结点代表人，二人若是朋友，则在结点间连上一条边，这样可得无向简单图G，每个人的朋友数即该结点的度数，于是问题转化为：n阶无向简单图G中必有两个顶点的度数相同。 证明：用反证法。 设G中各顶点的度数均不相同，则度数列为0，1，2，n-1，说明图中有孤立顶点，与有n-1度顶点相矛盾（因为是简单图），所以必有两个顶点的度数相同。,8.1 图的基本概念,四、图的同构 定义8.7 设图G= 和G=，若存在双射f：VV且f(V)= V，(vi，vj)E当且仅当(f(vi)，f(vj) E(E当且仅当E)

13、， 则称图G和G同构，记作GG。 例，下面列出了一些同构图，如图8.7所示，,8.1 图的基本概念,构造映射g(vi)=vi(i=1，2，5，6)，可使(vi，vj)和(g(vi)，g(vj)一一对应，即两图同构。两图同构的必要条件：,图 8.7,8.1 图的基本概念,1) 结点数相等; 2) 边数相等; 3) 度数相同的结点数相等。 但不是充分条件。 如图8.8所示， 上图所示两图虽然满足结点数相等、边数相等和度数相同的结点数相等这三个条件，但并不同构。,8.2 图的运算,由于图由结点集、边集组成，也是一种关系的标识，因此对图可作种种与集合运算相类似的运算。通过对图的运算，可以得到一些具有实

14、际应用意义的新图，如许多网络拓朴结构是通过图的运算得到的。 一、图的基本运算 (1) 删除运算 从图G中删除一边e所得到的子图，记为G-e。从图G中删除一个结点v及其关联的边所得到的子图，记为G-v。类似地，G-E表示从G中删除边集E的子集E所得到的子图，记为G-E=(V，E-E)。G-V表示从G中删除结点,8.2 图的运算,集V的子集V以及与它们关联的边所得的子图。 (2)边收缩运算 设图G中边e=(vi，vj)，删去边e，并把vi与vj合并成一个新点vi-j，使原来与vi或vj关联的边变为与点vi-j关联的边，称边e被收缩，得到的新图称为G关于边e的收缩图，记为G/e或G/vivj。如图8

15、.9，图（b）是对图(a)的边（d，e）收缩后得到的图。,8.2 图的运算,(3) 并与和运算 设G1=(V1，E1)，G2=(V2，E2)是两个给定的图，则定义： G1与G2的并为G1G2=(V1V2，E1E2)； G1与G2的和G1+G2是在G1与G2的并的基础上需增加G1的每个结点与G2的每个结点连接得到的共计mn条边，m，n分别为G1，G2的阶。如图8.10所示，图(a)为K2K3，图(b)为K2+K3。,8.2 图的运算,图 8.10,8.2 图的运算,二、补运算 定义8.8 设G=为任意的n阶无向简单图，则由G的所有结点及使G成为完全图的添加边所组成的图，称为G的补图。记为 。 例

16、如，图G和其补图 如图8.11所示，,图8.11,8.2 图的运算,三、子图 定义8.9 给定图G1=和G2=，如果满足： 1)若V1V2 ，E1E2 ，E1中的边所关联的顶点均在V1中，则称G1为G2的子图。 2)若V1=V2 ，E1E2 ，E1中的边所关联的顶点均在V1中，则称G1为G2的生成子图或支撑子图。,8.2 图的运算,例，如图8.12所示， 从图中可看出，上图中G1和G2都是G的子图，但只有G2是G的生成子图。,图8.12,8.3 路径与图的连通性,右图是中国铁路交通图的一部分，如果一个旅客要从成都乘火车到北京，那么他一定会经过其它车站；而旅客不可能从成都乘火车到达台北。这就引出

17、了图的通路与连通的概念。,8.3 路径与图的连通性,一、 通路和回路 给定图G=中结点和边相继交错出现的序列=v0e1v1e2v2ekvk。 若中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点），i=1,2,k，则称为结点v0到结点vk的通路(Entry)。v0和vk分别称为此通路的始点和终点，统称为通路的端点。通路中边的数目k称为此通路的长度(Length)。当v0=vn时，此通路称为回路(Circuit)。,8.3 路径与图的连通性,若通路中的所有边互不相同，则称此通路为简单通路(Simple Entry)或一条迹；若回路中的所有边互不相同，则称此回路

18、为简单回路(Simple Circuit)或一条闭迹。 若通路中的所有结点互不相同（从而所有边互不相同），则称此通路为基本通路(Basic Entry)或者初级通路、路径；若回路中除v0=vk外的所有结点互不相同（从而所有边互不相同），则称此回路为基本回路(Basic Circuit)或者初级回路、圈。,8.3 路径与图的连通性,说明： 回路是通路的特殊情况。因而，我们说某条通路，它可能是回路。但当我们说一初级通路时，一般是指它不是初级回路的情况。 初级通路（回路）一定是简单通路（回路），但反之不真。因为没有重复的结点肯定没有重复的边，但没有重复的边不能保证一定没有重复的结点。 在不会引起误解

19、的情况下，一条通路v0e1v1e2v2envn也可以用边的序列e1e2en来表示，这种表示方法对于有向图来说较为方便。在简单图中，一条通路v0e1v1e2v2envn也可以用结点的序列v0v1v2vn来表示。,8.3 路径与图的连通性,例 8.3.1 判断下图G1中的回路v3e5v4e7v1e4v3e3v2e1v1e4v3、v3e3v2e2v2e1v1e4v3、v3e3v2e1v1e4v3是否是简单回路、初级回路？图G2 中的通路v1e1v2e6v5e7v3e2v2e6v5e8v4、v1e5v5e7v3e2v2e6v5e8v4、v1e1v2e6v5e7v3e3v4是否是简单通路、初级通路？并求

20、其长度。,8.3 路径与图的连通性,判断一条通（回）路是否是简单通（回）路、初级通（回）路，主要是看它有无重复的边、结点。 在图G1中，v3e5v4e7v1e4v3e3v2e1v1e4v3中有重复的边e4，因此它不是简单回路，也不是初级回路； v3e3v2e2v2e1v1e4v3虽然没有重复的边，但有重复的结点v2，因此只能是简单回路，而不是初级回路； 而v3e3v2e1v1e4v3中既没有重复的边，也没有重复的结点，因此既是初级回路，也是简单回路；,8.3 路径与图的连通性,在图G2 中，v1e1v2e6v5e7v3e2v2e6v5e8v4中有重复的边e6，因此它既不是简单通路，也不是初级通

21、路； v1e5v5e7v3e2v2e6v5e8v4虽然没有重复的边，但有重复的结点v5，因此只能简单通路，但不是初级通路； v1e1v2e6v5e7v3e3v4中既没有重复的边，也没有重复的结点，因此既是初级通路，也是简单通路。 至于通（回）路的长度就是其包含的边的数目，这只需要数一数就行了。,8.3 路径与图的连通性,在图G1中，v3e5v4e7v1e4v3e3v2e1v1e4v3是一条长度为6的回路，但既不是简单回路，也不是初级回路； v3e3v2e2v2e1v1e4v3是一条长度为4的简单回路，但不是初级回路； v3e3v2e1v1e4v3是一条长度为3的初级回路，也是简单回路；,8.3

22、 路径与图的连通性,在图G2中，v1e1v2e6v5e7v3e2v2e6v5e8v4是一条长度为6的通路，但既不是简单通路，也不是初级通路； v1e5v5e7v3e2v2e6v5e8v4是一条长度为5的简单通路，但不是初级通路； v1e1v2e6v5e7v3e3v4是一条长度为4的初级通路，也是简单通路。,8.3 路径与图的连通性,定理8.3.1 在一个具有n个结点的图中，如果从结点vi到结点vj（vivj）存在一条通路，则从vi到vj存在一条长度不大于n-1的通路。 分析 通路的长度为序列中的结点数减1，如果结点不重复，最多n个，因此通路长度最多n-1；如果结点有重复，则在重复的结点间构成一

23、条回路，删除这条回路，剩下的仍然是从结点vi到结点vj的通路。一直删下去，直到无重复结点为止，这样定理就得证了。,8.3 路径与图的连通性,推论8.3.1 在一个具有n个结点的图中，如果从结点vi到结点vj（vivj）存在一条通路，则从vi到vj存在一条长度不大于n-1的初级通路。 定理8.3.2 在一个具有n个结点的图中，如果存在经过结点vi的回路，则存在一条经过vi的长度不大于n的回路。 推论8.3.2 在一个具有n个结点的图中，如果存在经过结点vi的回路，则存在一条经过vi的长度不大于n的初级回路。 通路、回路是讨论图的连通性的基础，下面分别讨论无向图和有向图的连通性问题。,8.3 路径

24、与图的连通性,二、 无向图的连通性 无向图中，如果图中两个点之间存在通路，则称v0和vn是连通的。并规定一个点与其本身是连通的。 图中两点间的连通关系是等价关系。因此顶点集上的等价连通关系必然对应一个顶点集的一个划分，一个划分块中的任何点之间都是连通的，而不同的划分块之间是不连通的。如果划分块只有一个，则称无向图是连通的。 1、图的连通性定义 如果G=中任何结点都是连通的，则称图是连通的；否则，称为G为不连通的。,8.3 路径与图的连通性,连通分支：图G中的任何一个划分块，记为：W(G) 2、点割集和边割集 （1）点割集和割点 设无向图G=为连通图，若有点集V V，使图G删除了V的所有结点后（

25、将V中结点与其关联的边都删除）得到的子图是不连通的，而删除了V的任何一个真子集后得到的子图仍是连通图，则称V为G的一个点割集； 如果点割集中只有一个元素，此点称为割点。 示例：如图8.15所示，举例说明图中的点割集及割点。,8.3 路径与图的连通性,图 8.15,8.3 路径与图的连通性,（2）边割集和桥 设无向图G=为连通图，如果有边集E E，在图G中删除了E 后，得到的子图是不连通的，而删除了E的任何一个真子集后得到的子图仍是连通图，则称E为G的一个边割集； 如果边割集中只有一个元素，此边称为割边或桥。 示例： 同样如图8.15所示，举例说明图中的边割集和桥。,8.3 路径与图的连通性,三

26、、有向图的连通性 无向图的连通性不能直接推广到有向图。 在有向图中，如果存在从一个点u到另一个点v的路径，则称 从u到v可达。并规定任何顶点到自身是可达的。 注：顶点间的可达关系是有向图中基本的顶点间的关系，是自反的、可传递的，但不一定是对称的，所以不是等价关系。 根据顶点间的可达关系，可定义有向图的连通性。,8.3 路径与图的连通性,1、弱连通：在简单有向图D中，略去边的方向得到的无向图G，如果G是连通的，则有向图D是弱连通的； 2、单向连通：若D中任何两个顶点间，至少有一个顶点可达另一个顶点，则称D是单向连通的； 3、强连通：若D中任何两个顶点间都可以相互可达，则称D是强连通的； 示例：如

27、下图8.16所示。,8.3 路径与图的连通性,图 8.16,由上图可知，a为强连通的，b为单向连通的，c为弱连通的。,8.3 路径与图的连通性,思考题 例8.3.2 试寻找3个4阶有向简单图D1，D2，D3，使得D1为强连通图；D2为单向连通图，但不是强连通的；D3为弱连通的，但不是单向连通或强连通。,8.3 路径与图的连通性,四、路径与图的应用问题 1、渡河问题 例8.3.3 一个摆渡人要把一只狼、一只羊和一捆菜运过河去。由于船很小，每次摆渡人至多只能带一样东西。另外，如果人不在旁时，狼就要吃羊，羊就要吃菜。问这人怎样才能将它们运过河去？ 解 用F表示摆渡人，W表示狼，S表示羊，C表示菜。

28、若用FWSC表示人和其它三样东西在河的原岸的状态，这样原岸全部可能出现的状态为以下16种：,8.3 路径与图的连通性,FWSC FWS FWC FSC WSC FW FS FC WS WC SC F W S C 这里表示原岸什么也没有，即人、狼、羊、菜都已运到对岸去了。 根据题意我们知道，这16种情况中有6种是不允许的，它们是：WSC、FW、FC、WS、SC、F。如FC表示人和菜在原岸，而狼和羊在对岸，这当然是不行的。因此，允许出现的情况只有10种。,8.3 路径与图的连通性,以这10种状态为结点，以摆渡前原岸的一种状态与摆渡一次后仍在原岸的状态所对应的结点之间的联线为边做有向图G，如图,图中给出了两种方案，方案为图中的从FWSC到的不同的基本通路，它们的长度均为7，按图中所指的方案，摆渡人只要摆渡7次就能将它们全部运到对岸，并且羊和菜完