离散数学─图论初步 南京大学计算机科学与技术系

Presentation on theme: "离散数学─图论初步 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─图论初步 南京大学计算机科学与技术系
基本概念 离散数学─图论初步 南京大学计算机科学与技术系

2 内容提要 图的定义 图模型 图的术语 几种特殊的图 二部图 （偶图） 图的运算 图结构上的经典问题

3 柯尼斯堡(Königsberg)七桥问题
C D A B A C B D 可否：从四块陆地中任一块出发，恰好通过每座桥一次，再回到起点。 “一笔画”问题 问题的抽象（欧拉于1736年） 用顶点表示对象-“地块” 用边表示对象之间的关系-“有桥相连” 没有一个顶点所关联的边数为偶数

4 图的定义 图G是一个三元组：G =(V, E, ) 举例（数据中心、通信链接） V是非空顶点集，E是边集，且V⋂E=；
: E  (V), 且e E. 1|(e)|2. (e)称为边e的端点集. 举例（数据中心、通信链接） 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律

5 图的定义（续） 图G = (V, E, )是简单图，如果 图G = (V, E, )是伪图，如果
每条边有2个端点，即： e E. |(e)| = 2，并且 不同边有不同端点集，即：如果e1 e2 ，则(e1)  (e2) 图G = (V, E, )是伪图，如果 存在一条只有1个端点的边，即: e0E.|(e0)| = 1，或者 有两条边具有相同的端点集，即: e1 e2.(e1)=(e2)

6 图的定义（续） 伪图（包含环或者多重边）示例 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律

7 图的定义（有向图） 有向图G是一个三元组：G= (V, E, ) 简单有向图:  是单射，边的起点和终点不相同。
V是非空顶点集，E是有向边（弧）集，且V⋂E=； :EVV, 若(e)=(u, v), 则u和v分别称为e的起点和终点. 简单有向图:  是单射，边的起点和终点不相同。 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律

8 图模型 交通网络 信息网络 社会网络 体育（循环赛的图模型） 航空、公路、铁路 万维网图（Web Graph）
引用图（Citation Graph） 社会网络 熟人关系图 合作图，好莱坞图 呼叫图 体育（循环赛的图模型）

9 图的术语 无向图G = (V, E, ), (e)={u, v} , uv 图G中顶点v的度, deg(v)， dG(v)
与该顶点关联的边数，自环为顶点的度做出双倍贡献。 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律

10 握手定理 无向图G有m条边，n个顶点v1, …vn. 推论：无向图中奇数度顶点必是偶数个。

11 图的术语（续） 有向图G =(V, E, ), (e)=(u, v) 有向图中顶点的出度和入度 有向图中各顶点的出度之和等于入度之和。
u是e的起点，v是e的终点 假设 uv，u邻接到v，v从u邻接 有向图中顶点的出度和入度 dG+(v) = 以v为始点的边的条数， deg+(v) dG-(v) = 以v为终点的边的条数， deg- (v) 有向图中各顶点的出度之和等于入度之和。 vV deg+(v) = vV deg-(v) =|E| 有向图的底图

12 特殊的简单图（完全图） 若简单图G中任意两点均相邻，则称为完全图。记为Kn, 其中n是图中顶点数。
Kn中每个顶点皆为n-1度，总边数为n(n-1)/2。 边数达到上限的简单图。 K5 K3 K4 K1 K2

13 特殊的简单图（圈图与轮图） Cycle C5 C4 C3 Wheel W4 W3 W5

14 特殊的简单图（立方体图） 正则图：顶点度相同的简单图 n-cube Q3 Q2 Q1 100 101 000 001 110 111 010
011 Q2 10 11 00 01 Q1 1 正则图：顶点度相同的简单图

15 二部图（bipartite graph） 二部图：顶点集划分为2个类别(不相交)，边的端点在不同类别中。
完全二部图：来自不同类别的两个顶点均有边。 K2,3 K3,3 G

16 二部图的判定 C6是否是二部图？ 二种颜色对顶点着色，相邻顶点赋以不同颜色 二部图？

17 子图 设G=<V,E>, G’=<V’,E’>, 如果V’V, E’E, 则称G’是G的子图。
诱导(导出)子图：可以由顶点集的子集，或者由边集的子集导出一个子图。

18 图的运算 加新边:G+e 减边或边集：G-e 减点或点集: G-v （同时删除与v关联的边） 边的收缩: G/e

19 图的运算 G∪G’：以V(G)∪V(G’)中的顶点组成的集合为顶点集,以E(G)∪E(G’)为边集。 //简单图的并
假设G和G’是不交的无向图, 定义GG’如下： 以V(G)∪V(G’)为顶点集 以E(G)∪E(G’)∪{{x, y}| xV(G), yV(G’)}为边集 举例, K2  K3 = K5. 简单图G的补图（complement graph），记为 G G=(V, E) 的补图定义为 (V, [V]2 \E)

20 图结构上的经典问题孤岛上的婚姻 孤岛上有m个男子和n个女子，每个人均有一个可选配偶列表，如何成就尽可能多的幸福婚姻？ 最大匹配问题。
A 1 B 2 C 3 D 4 E 5 F 6 G {A, C, F} {A, C} {A, F} {C, F}

21 中国邮递员问题（管梅谷，1960） 邮递员从邮局出发，走过辖区内每条街道至少一次，再回邮局，如何选择最短路线？
Euler回路？添加重复边（权和最小）。

22 旅行商(TSP)问题 n个城市间均有道路，但距离不等，旅行商从某地出发，走过其它n-1个城市，且只经过一次，最后回到原地，如何选择最短路线？
最短Hamilton回路。

23 地图与平面图着色（四色猜想）

24 作业 教材[9.1, 9.2] p. 459： 5-8, 16, 20 p. 468： 5, 8, 31, 36(a, c, e, g), 53