东南大学：《离散数学》课程教学资源（PPT课件讲稿）第七章 图论（主讲：仲新宇）

第四篇图论 图论是近年来发展迅速而又应用广泛的一门新兴 学科。它最早起源于一些数学游戏的难题研究, 如1736年欧拉( L Euler所解决的哥尼斯堡七桥 问题。以及在民间广为流传的一些游戏问题: 例如迷宫问题、棋盘上马的行走路线问题等 等。这些古老的问题当时吸引了许多学者的注 意,从而在这些问题研究的基础上,又提出了 著名的四色猜想和环游世界各国的问题

第四篇 图论 图论是近年来发展迅速而又应用广泛的一门新兴 学科。它最早起源于一些数学游戏的难题研究， 如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥 问题。以及在民间广为流传的一些游戏问题： 例如 迷宫问题、棋盘上马的行走路线问题等 等。这些古老的问题当时吸引了许多学者的注 意，从而在这些问题研究的基础上，又提出了 著名的四色猜想和环游世界各国的问题

第四篇图论 图论不断发展,它在解决运筹学,网络理 论,信息论,控制论,博奕论以及计算 机科学等各个领域的问题时,显示出越 来越大的效果 对于这样一门应用广泛的学科,其包含的 内容是丰富的,本篇我们只准备介绍基 本的概念和定理,为今后有关学科及课 程的学习和研究提供方便

第四篇 图论 图论不断发展，它在解决运筹学，网络理 论，信息论，控制论，博奕论以及计算 机科学等各个领域的问题时，显示出越 来越大的效果。 对于这样一门应用广泛的学科，其包含的 内容是丰富的，本篇我们只准备介绍基 本的概念和定理，为今后有关学科及课 程的学习和研究提供方便

第四篇图论 第七章图论 §1图的基本概念 §2路与回路 §3图的矩阵表示 §4欧拉图和汉密尔顿图 §5平面图 §6树与生成树

第四篇 图论 第七章 图论 §1图的基本概念 §2路与回路 §3图的矩阵表示 §4欧拉图和汉密尔顿图 §5平面图 §6树与生成树

§1图的基本概念 1.基本名词和定义 《定义》一个图G是一个三元组2其中 V(G为有限非空结点(或叫顶点)集合(G是边的集 合,中G是从边集E到结点偶对集合上的函数 讨论定义 (1)VG)={V1,V2,…,Vn}为有限非空集合, V称为结点,简称V是点集 (2).E(G)={e1,…,em}为有限的边集合称为边 每个e都有V中的结点对与之相对应,称E为边集。 即每条边是连结中的某两个点的

§1图的基本概念 1.基本名词和定义 《定义》一个图G是一个三元组, 其中 V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集 合， ΦG是从边集E到结点偶对集合上的函数。 讨论定义： (1). V(G) ={V1，V2，…，Vn }为有限非空集合, Vi称为结点,简称V是点集。 (2). E(G)={e1，…，em }为有限的边集合,ei称为边， 每个ei都有V中的结点对与之相对应,称E为边集。 即每条边是连结V中的某两个点的

§1图的基本概念 (3)若G中每一条边e与有序偶对或无序偶 对(vv)相关系,则可说边e连接结点v;和v (4)可用e=vY>或e=(v,y),以结点来表示图 的边,这样可把图简化成:G= 例:有图如下,试写成定义表达式 V1 G=〈V,E 其中V={v 1V2,V3,v4,V5 E={X12x2X32X42X52x6}

§1图的基本概念 (3).若Ｇ中每一条边e与有序偶对或无序偶 对(vi ,vj )相关系，则可说边e连接结点vi和vj (4).可用e＝ 或e＝ (vi ,vj )，以结点来表示图 的边，这样可把图简化成：Ｇ＝。 例：有图如下，试写成定义表达式 Ｇ＝〈Ｖ，Ｅ〉， 其中Ｖ＝{v1 ,v2 ,v3 ,v4 ,v5} Ｅ＝{x1 ,x2 ,x3 ,x4 ,x5 ,x6}

§1图的基本概念 例:对有向图可表示为: G=〈V、E〉 b 其中V={a、b、c、d} E {,,,,,<c,c③ 下面定义一些专门名词: (1)有向边:在图中对应有序偶对的边(或者:在图中 带有箭头方向的边或弧线)

§1图的基本概念 例：对有向图可表示为： Ｇ＝〈Ｖ、Ｅ〉， 其中Ｖ＝｛a、b、c、d｝ Ｅ＝ ｛,,,,,｝ 下面定义一些专门名词： (1)有向边：在图中对应有序偶对的边（或者：在图中 带有箭头方向的边或弧线）

s1图的基本概念 (2)无向边:在图中对应无序偶对的边(或:在图中 不带箭头的边) (3)邻接结点:由一条边(有向或无向)连接起来的 结点偶对 (4)(n,e)图:具有n个结点(顶点),e条边 的图 (5)有向图:在G中每一条边均为有向边 (5)有向完全图:在n个结点的有向图G中,如 果B例 E=V×V,则称G为有向完全图

§1图的基本概念 (2)无向边：在图中对应无序偶对的边（或：在图中 不带箭头的边） (3)邻接结点：由一条边（有向或无向） 连接起来的 结点偶对 (4)（ｎ，ｅ）图：具有ｎ个结点（顶点），ｅ条边 的图 (5)有向图：在Ｇ中每一条边均为有向边 (5)有向完全图：在n个结点的有向图G=中，如 果 E＝V×V，则称G为有向完全图。 例：

§1图的基本概 对有向简单完全图讲:e=2.C2=n(n-1) (没有自回路)

§1图的基本概念 对有向简单完全图讲：ｅ＝ ＝n(n-1) （没有自回路） 2 2 Cn 

§1图的基本概念 (6)无向图:每一条边均为无向边的图 (7)无向完全图:每两个结点之间均有连线的无向图。 n个结点的无向完全图的边数为: 2n(n-1) 例:

§1图的基本概念 (6)无向图：每一条边均为无向边的图 (7)无向完全图：每两个结点之间均有连线的无向图。 n个结点的无向完全图的边数为： 例： 2 ( 1) 2 − = = n n e Cn

§1图的基本概念 (8)混合图:既有有向边,又有无向边的图 (9)互相邻接的边:连接于同一结点的二条(或若干条) a d C

§1图的基本概念 (8)混合图：既有有向边，又有无向边的图 (9)互相邻接的边： 连接于同一结点的二条（或若干条） 边 例：