复旦大学：《离散数学》课程教学讲义（图论）第八章 图的基本概念

第八章图的基本概念 >图论 >图是由一些顶点和连接这些顶点的一些边 所组成的离散结构

第八章 图的基本概念  图论  图是由一些顶点和连接这些顶点的一些边 所组成的离散结构

图论教学目的 >采用图论的成果和方法,培养思考问题与 解决问题的能力

图论教学目的  采用图论的成果和方法，培养思考问题与 解决问题的能力

>8.1引言 >8.2路与回路 >8.3欧拉图 84哈密顿图 >8.5最短路 >86图论模型和证明

 8.1 引言  8.2 路与回路  8.3 欧拉图  8.4 哈密顿图  8.5 最短路  8.6 图论模型和证明

>有关图论的提高参考书: > Bela bollobas. Modern graph Theory(现代 图论)科学出版社& Springer.2001

 有关图论的提高参考书：  Bela Bollobas. Modern Graph Theory (现代 图论). 科学出版社 & Springer. 2001

8.1引言 图论的起源与发展 二有向图 无向图 >四顶点度数 >五同构概念 六子图

8.1 引言  一 图论的起源与发展  二 有向图  三 无向图  四 顶点度数  五 同构概念  六 子图

5.1引言 >一图论的起源与发展 1起源:哥尼斯堡七桥问题 能否从河岸或小岛出发,通过每一座桥,而且仅仅通 过一次回到原地

5.1 引言  一 图论的起源与发展 1 起源：哥尼斯堡七桥问题 能否从河岸或小岛出发，通过每一座桥，而且仅仅通 过一次回到原地。 A C B D

1736年:图论历史元年 >在1736年,年仅29岁的瑞士数学家欧拉 ( Euler)发表了图论的首篇论文—《哥 尼斯堡七桥问题无解》,所以人们普遍认 为欧拉是图论的创始人。 Euler指出,如果在B点出发,B点处有3座 桥,经过其中之一离开,有经过另一桥回 来,因为要求每桥恰过一次,所以不得不 经过第3座桥离开,则无法回来。处在其他 出发点的情形是相似的

1736年：图论历史元年  在1736年，年仅29岁的瑞士数学家欧拉 （Euler）发表了图论的首篇论文——《哥 尼斯堡七桥问题无解》，所以人们普遍认 为欧拉是图论的创始人。  Euler指出，如果在B点出发，B点处有3座 桥，经过其中之一离开，有经过另一桥回 来，因为要求每桥恰过一次，所以不得不 经过第3座桥离开，则无法回来。处在其他 出发点的情形是相似的

2图论的三个发展阶段 1736年到19世纪中叶,萌芽阶段;多数问 题围饶游戏展开 >19世纪中叶到1936年,作为一个数学分支的 形成;图论问题(如四色问题、哈密顿图)大量 出现,也出现了以图为工具解决问题的成果。 1936年,KOng总结了图论200年来的研究成果, 出版了图论的第一部专著《有限图与无限图理论》 1936年以后,计算机科学的发展为图论的发 展提供了计算工具;现代科学技术的发展需要借 助图论来描述和解决各类课题中的各种关系

2 图论的三个发展阶段  1736年到19世纪中叶，萌芽阶段；多数问 题围饶游戏展开  19世纪中叶到1936年，作为一个数学分支的 形成；图论问题（如四色问题、哈密顿图）大量 出现，也出现了以图为工具解决问题的成果。 1936年，Konig总结了图论200年来的研究成果， 出版了图论的第一部专著《有限图与无限图理论》  1936年以后，计算机科学的发展为图论的发 展提供了计算工具；现代科学技术的发展需要借 助图论来描述和解决各类课题中的各种关系

3图论发展的原因 >1图论提供了一个自然的结构,由此产生 的数学模型几乎适合于所有科学(自然科 学和社会科学)领域,只要这个领域研究 的主题是“对象”与“对象”之间的关系。 >2图论已形成自己的丰富词汇语言,能简 洁地表示出各个领域中“对象-关系”结构 复杂而又难懂的概念 3图论提供了大量智力挑战问题

3 图论发展的原因  1 图论提供了一个自然的结构，由此产生 的数学模型几乎适合于所有科学（自然科 学和社会科学）领域，只要这个领域研究 的主题是“对象”与“对象”之间的关系。  2 图论已形成自己的丰富词汇语言，能简 洁地表示出各个领域中“对象-关系”结构 复杂而又难懂的概念。  3 图论提供了大量智力挑战问题

5.1引言 >二有向图 >1)定义8.1(有向图) 设V是一个非空集,E是V上的二元关系, 称有序对(v,E为有向图,记为G=(VE或 G(v,E。V中元素称为顶点(或点),V称 顶点集。E是VxV的子集,E中的元素是有序 对,称为弧,E称为弧集。 二元组表示图:例分>图82

5.1 引言  二 有向图  1） 定义8.1(有向图) 设V是一个非空集，E是V上的二元关系， 称有序对(V, E)为有向图，记为G=(V, E)或 G(V, E)。V中元素称为顶点（或点），V称 顶点集。E是VV的子集，E中的元素是有序 对，称为弧，E称为弧集。 二元组表示图：例图8.2