东南大学：《离散数学》课程教学资源（PPT课件讲稿）第四部分 图论 第十四章 图的基本概念

七桥问题 豪 问题 A 令寻找走遍哥尼斯堡( KOnigsberg) 岛 城的7座桥,且只许走过每座桥 次,最后又回到原出发点 口求解 ◆1736年瑞士大数学家欧拉 ( Leonhard euler)发表了关于 “哥尼斯堡七桥问题”的论文 (图论的第一篇论文)。他指出 从一点出发不重复的走遍七桥, 最后又回到原来出发点是不可能 的

2 七桥问题 ❑问题 ❖寻找走遍哥尼斯堡（KÖnigsberg） 城的7座桥，且只许走过每座桥一 次，最后又回到原出发点 ❑求解 ❖1736年瑞士大数学家欧拉 （Leonhard•Euler）发表了关于 “哥尼斯堡七桥问题”的论文 （图论的第一篇论文）。他指出 从一点出发不重复的走遍七桥， 最后又回到原来出发点是不可能 的

图论 豪 图论是近年来发展迅速而又应用广泛的 门新兴学科。它最早起源于一些数学游戏的 难题研究,如1736年欧拉( LEuler)所解决 的哥尼斯堡七桥问题。以及在民间广为流传 的一些游戏问题:例如迷宫问题、棋盘上马 的行走路线问题

3 图论 图论是近年来发展迅速而又应用广泛的一 门新兴学科。它最早起源于一些数学游戏的 难题研究，如1736年欧拉（L.Euler)所解决 的哥尼斯堡七桥问题。以及在民间广为流传 的一些游戏问题：例如迷宫问题、棋盘上马 的行走路线问题

棋盘上马的行走路线问题 豪 口在中国象棋中,马走“日”字,即每步从1×2矩形的 个顶点跳到相对的顶点。如图,马从M(3,2)一次只 能跳到A、B、C、D、E、F、G、H中的任何一个位置。 口问题:马能否从棋盘上任意一点出发,不重复、不遗漏 地走遍整个棋盘(即每一点都走到并且只到一次)? 楚河汉界 H B G 马 D 12345 78 4

4 棋盘上马的行走路线问题 ❑ 在中国象棋中，马走“日”字，即每步从1×2 矩形的一 个顶点跳到相对的顶点。如图，马从M（3，2）一次只 能跳到A、B、C、D、E、F、G、H中的任何一个位置。 ❑ 问题：马能否从棋盘上任意一点出发，不重复、不遗漏 地走遍整个棋盘（即每一点都走到并且只到一次）？

棋盘上马的行走路线问题 豪 口将马目前所在位置涂成白色,用涂色的方法,将棋 盘上的点分为黑、白相间的两类 楚河汉界 3 1 7 8

5 棋盘上马的行走路线问题 ❑ 将马目前所在位置涂成白色，用涂色的方法，将棋 盘上的点分为黑、白相间的两类

环游世界各国的问题 豪 口英国数学家哈密顿于1859年以游戏的形式提出:把一个 正十二面体的二十个顶点看成二十个城市,要求找出 条经过每个城市恰好一次而回到出发点的路线。这条路 线就称“哈密顿圈”。一百多年来,对哈密顿问题的研 究,促进了图论的发展。 16 5 14

6 环游世界各国的问题 ❑ 英国数学家哈密顿于1859年以游戏的形式提出：把一个 正十二面体的二十个顶点看成二十个城市，要求找出一 条经过每个城市恰好一次而回到出发点的路线。这条路 线就称“哈密顿圈”。一百多年来，对哈密顿问题的研 究，促进了图论的发展

四色猜想 豪 口问题:任何一张地图只用 四种颜色就能使具有共同 边界的国家着上不同的颜 口用数学语言表示,即: 将平面任意地细分为不相 重叠的区域,每一个区域 总可以用1,2,3,4这四 个数字之一来标记,而不 会使相邻的两个区域得到 相同的数字

7 四色猜想 ❑问题：任何一张地图只用 四种颜色就能使具有共同 边界的国家着上不同的颜 色 ❑用数学语言表示，即：“ 将平面任意地细分为不相 重叠的区域，每一个区域 总可以用 1 ， 2 ， 3 ， 4这四 个数字之一来标记，而不 会使相邻的两个区域得到 相同的数字

图论 豪 口图论不断发展,它在解决运筹学,网络 理论,信息论,控制论,博奕论以及计 算机科学等各个领域的问题时,显示出 越来越大的作用

8 图论 ❑图论不断发展，它在解决运筹学，网络 理论，信息论，控制论，博奕论以及计 算机科学等各个领域的问题时，显示出 越来越大的作用

9)第十四章图的基本概念 豪 第一节:图 第二节:通略、回路、图的连通性 第三节:图的矩阵表示和运算

9 第十四章 图的基本概念 第一节：图 第二节：通路、回路、图的连通性 第三节：图的矩阵表示和运算

第一节:图 豪 口无序积:设A,B为任意的两个集合,称 {a,b}|a∈A且b∈B} 为A与B的无序积,记做A&B 口无向图:一个无向图G是一个二重组VG,E(G)>,其 中ⅤG为有限非空结点(或叫顶点)集合,E(G)是边 的集合,它是无序积v&V的多重子集,其元素为无 向边,简称边。 口有向图:一个有向图G是一个二重组,其 中VG为有限非空结点(或叫顶点)集合,E(G)是边 的集合,它是笛卡儿乘积V×V的多重子集,其元素 为有向边,简称边。 10

10 第一节：图 ❑ 无序积：设A，B为任意的两个集合，称 {{a,b} | a∈A且b∈B} 为A与B的无序积，记做A&B ❑ 无向图：一个无向图G是一个二重组, 其 中V(G)为有限非空结点（或叫顶点）集合, E(G)是边 的集合，它是无序积V&V的多重子集，其元素为无 向边，简称边。 ❑ 有向图：一个有向图G是一个二重组, 其 中V(G)为有限非空结点（或叫顶点）集合, E(G)是边 的集合，它是笛卡儿乘积V×V的多重子集，其元素 为有向边，简称边

第一节:图 豪 下面定义一些专门名词: (1)通常用G表示无向图,D表示有向图,但G也可以泛 指图。V(G),E(G)分别表示G的顶点集和边集。 V(G)|,|E(G)分别表示G的顶点数和边数, 若|V(G)|=n,则称G为n阶图 (2)若V(G)|,EG)|均为有限数,则称G为有限图 (3)若图G中,边集为空,则称之为零图, 若G为n阶图,则称之为m阶零图,记为N, N称为平凡图 (4)顶点集为空的图记为空图

11 下面定义一些专门名词： （１）通常用G表示无向图，D表示有向图，但G也可以泛 指 图 。 V(G) ， E(G) 分别表示 G 的顶点集和边集 。 |V(G)|,|E(G)|分别表示G的顶点数和边数， 若|V(G)|＝n，则称G为n阶图。 （２）若|V(G)|,|E(G)|均为有限数，则称G为有限图。 （３）若图G中，边集为空，则称之为零图， 若G为n阶图，则称之为n阶零图，记为Nn， N1称为平凡图。 （4）顶点集为空的图记为空图。 第一节：图