《离散数学图论》ppt课件

《《离散数学图论》ppt课件》由会员分享，可在线阅读，更多相关《《离散数学图论》ppt课件（121页珍藏版）》请在金锄头文库上搜索。

1、第八章 图论(Graph Theory),8.1 图的基本概念(Graph) 8.2 路与图的连通性(Walks & Connectivity of Graphs) 8.3 图的矩阵表示(Matrix Notation of Graph) 8.4 最短链与关键路（Minimal path ） 8.5 欧拉图与哈密尔顿图(Eulerian Graph & Hamilton-ian Graph ) 8.6 平面图(Planar Graph) 8.7树与生成树(Trees and Spanning Trees) 8.8 二部图（bipartite graph）,图 8.1.1哥尼斯堡七桥问题,8.1

2、 图的基本概念,8.1.1 图,现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。 【例8.1.1】a， b， c， d 4个篮球队进行友谊比赛。 为了表示个队之间比赛的情况，我们作出图.8.1.1的图形。 在图中个小圆圈分别表示这个篮球队， 称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。,1.图的定义,8.1 图的基本概念,图 8.1.1,如果图 8.1.1中的个结点a， b， c， d分别表示个人，当某两个人互相认识时， 则将其对应点之间用边连接起来。 这时的图又反映了这

3、个人之间的认识关系。,8.1 图的基本概念,定义8.1.1一个图G是一个序偶V(G), E(G)， 记为GV(G), E(G)。 其中V(G)是非空结点集合， E(G)是边集合， 对E(G)中的每条边， 有V(G)中的结点的有序偶或无序偶与之对应。 若边e所对应的结点对是有序偶a,b,则称e是有向边。a叫边e的始点,b叫边e的终点,统称为e的端点。若边e所对应的结点对是无序偶(a,b) ,则称e是无向边。这时统称e与两个结点a和b互相关联。,8.1 图的基本概念,【例8.1.2】 设G=V(G),E(G),其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1

4、=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。 则图G可用图8.1.2(a)或(b)表示。,我们将结点a、b的无序结点对记为(a，b）， 有序结点对记为a，b。 一个图G可用一个图形来表示且表示是不唯一的。,8.1 图的基本概念,图 8.1.2,8.1 图的基本概念,2. 图G的结点与边之间的关系 邻接点: 同一条边的两个端点。 孤立点: 没有边与之关联的结点。 邻接边: 关联同一个结点的两条边。 孤立边: 不与任何边相邻接的边。 自回路（环）：关联同一个结点的一条边（v，v）或v，v）。 平行边(多重边):关联同一

5、对结点的多条边。,8.1 图的基本概念,如例8.1.1中的图，结点集Va，b，c，d， 边集 Ee1， e2， e3， e4， e5， 其中 e1（a，b），e2（a, c），e3（a，d）， e4（b, c）， e5（c, d）。 d与a、 d与c是邻接的， 但d与b不邻接， 边e3与e5是邻接的。,8.1 图的基本概念,【例8.1.3】设图GV ,E 如图10.1.3所示。 这里Vv1，v2，v3， Ee1，e2，e3，e4，e5， 其中e1 =(v1, v2) ，e2=(v1，v3) ， e3 =(v3, v3), e4 =(v2, v3), e5=(v2，v3)。 在这个图中，e3是关

6、联同一个结点的一条边,即自回路；边e4和e5都与结点v2、 v3关联，即它们是平行边。,8.1 图的基本概念,图 8 .1. 3,3. 图G的分类 按G的结点个数和边数分为(n,m)图,即n个结点, m条边的图; 特别地, (n,0)称为零图, (1,0) 图称为平凡图 。在零图中边集为空集。 (2) 按G中关联于同一对结点的边数分为多重图和简单图; 多重图:含有平行边的图（如图 8 .1. 3） ； 线 图: 非多重图称为线图； 简单图:不含平行边和自环的图。,8.1 图的基本概念,G1、G2是多重图,G3是线图,G4是简单图,(3)按G的边有序、无序分为有向图、无向图和混合图; 有向图：每

7、条边都是有向边的图称为有向图 （图 8 .1.4 (b)； 无向图：每条边都是无向边的图称为无向图； 混合图：既有无向边, 又有有向边的图称为混合图。 如果将有向图中的每条边都变成无向边，称为底图 (4)按G的边旁有无数量特征分为加权图、无权图(如图 8.1.4);,8.1 图的基本概念,图 8 .1. 4,(5)按G的任意两个结点间是否有边分为完全图Kn (如图 8.1.5)和不完全图(如图 8.1.6)。,8.1 图的基本概念,完全图：任意两个不同的结点都邻接的简单图称为完全图。n 个结点的无向完全图记为Kn。 图8.1.5给出了K3和K4。从图中可以看出K3有条边，K4有条边。 容易证明

8、Kn有 条边。,8.1 图的基本概念,图 8.1. 6,图 8.1.5 K3与K4示意图,例,有向完全图,无向完全图,8.1.2 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点 关联，这就引出了图的一个重要概念结点的度数。,8.1 图的基本概念,定义: 在有向图中, 以v为终点的边数称为结点v 的入度， 记为 ;以v为始点的边数称为结点v 的出度， 记为 。结点v的入度与出度之和称为结点v的度数，记为 d(v)或deg(v)。,定义: 在无向图中，图中结点v所关联的边数(有环时计算两次)称为结点v 的度数，记为d(v)或deg(v) 。,顶点2入度：1 出度：3 顶点4入度：

9、1 出度：0,顶点5的度：3 顶点2的度：4,定理 8.1.1 无向图GV ,E中结点度数的总和等于边数的两倍， 即 证明: 因为每条边都与两个结点关联， 所以加上一条边就使得各结点度数的和增加 2， 由此结论成立。 定义：无向图中，如果每个结点的度都是k,则称为k-度正则图。,8.1 图的基本概念,推论: 无向图G中度数为奇数的结点必为偶数个。 证明: 设V1和V2分别是G中奇数度数和偶数度数的结点集。 由定理8.1.1知 由于 是偶数之和， 必为偶数， 而2|E|也为偶数， 故 是偶数。 由此|V1|必为偶数。,8.1 图的基本概念,定理 8.1.2 在任何有向图GV ,E中， 有,图8.

10、1.4,8.1.3 子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。 定义8.1.5 设有图G=V , E和图 G= V, E 。 1) 若V V， E E， 则称G是G的子图。 2) 若G是G的子图，且EE，则称G是G 的真子图。,图与子图,3) 若V=V， E E，则称G是G的生成子图。 图8.1.7给出了图G以及它的真子图G1和生成子图G2。,图8.1.7 图G以及其真子图G 1和生成子图G2,8.1 图的基本概念,给定任意一个含有n个结点的图G,总可以把它补成一个 具有同样结点的完全图,方法是把那些缺少的边添上。 定义8.1.2 设GV, E是一个具有n个结点

11、的简单 图。以V为结点集，以从完全图Kn中删去G的所有边后 得到的图（或由G中所有结点和所有能使G成为完全图 的添加边组成的图）称为G的补图，记为 。 例如，零图和完全图互为补图。,8.1 图的基本概念,G相对于Kn的补图是下图中的,关于补图： 1、G与 互为补图,1. 图的同构,8.1 图的基本概念,试观察下面各图有何异同？,图 8.1.8 同构的图,图 8.1.9,8.1 图的基本概念,定义8.1.6 设有图 G=V , E和图G= V, E。 如果存在双射：VV，使得 e=(u, v) E e=(u),(v)E， 且 (u， v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。

12、 注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。,8.1 图的基本概念,【例8.1.5】考察图8.1.9中的两个图GV , E和 G= V, E 。 显然，定义：VV, (vi)v i , 可以验证是满足定义8.1.6的双射，所以GG。,8.1 图的基本概念,图 8.1.9,一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。请证明下图中两个图是同构的。,根据图的同构定义，可以给出图同构的必要条件如下： (1) 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。 (4)有相同

13、重数的边数相同，等等。 但这仅仅是必要条件而不是充分条件。,下图中的(a)和(b)满足上述三个条件，然而并不同构。 因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,高等学校21世纪教材,对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,8.2 路与图的连通性(Walks & The Connectivity o

14、f Graphs),8.2.1 路与回路(Walks and Circuits) 8.2.2 图的连通性(The Connectivity of Graphs),8.2.1 路与回路(Wlaks and Circuits),定义 8.2.1 给定图GV ,E, 设v0, v1, , vkV， e1，e2，ekE，其中ei是关联于结点vi-1和vi的边， 称交替序列v0e1v1e2ekvk为连接v0到vk的路， v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。 当v0=vk时,这条路称为回路。 在简单图中一条路v0e1v1e2ekvk由它的结点序列v0v1vk确定,所以简单图的路,

15、可表示为v0v1vk 。如图8.1.1表示的简单图中， 路ae1be4ce5d可写成abcd。,定义 8.2.2 设=v0e1v1e2ekvk是图G中连接v0到vk的路。 1)若e1， e2， ， ek都不相同， 则称路为简单路或迹； 2)若v0， v1， ， vk都不相同，则称路为基本路或通路； 3) 圈中若出现的每条边恰好一次，称简单圈。若出现的每个结点恰好一次，称基本圈。,8.2.1 路与回路(Wlaks and Circuits),8.2.1 路与回路(Wlaks and Circuits),例如在图 8.2.1中， 有连接v5到v3的路v5e8v4e5v2e6v5e7v3， 这也是一

16、条简单路；路 v1e1v2 e3v3是一条基本路； 路v1e1v2e3v3e4v2e1v1是一 条回路， 但不是基本圈； 路v1e1v2e3v3e2v1是一条 简单回路，也是基本圈。,图 8.2.1,8.2.1 路与回路(Wlaks and Circuits),定义 8.2.3 在图G中， 若结点vi到vj有路连接（这时称vi和vj是可达的）， 其中长度最短的路的长度称为vi到vj 的距离， 用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=。 例如在图8.2.1中， （v1， v4）。,8.2.1 路与回路(Wlaks and Circuits),注意:在有向图中,d