Microsoft PowerPoint - Slide08-GraphTheory.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Slide08-GraphTheory.pptx"

柬尚
5 years ago
Views:

1 哥尼斯堡七桥问题普雷格尔河 (Pregel) 从哥尼斯堡镇 (Konigsberg, Prussia-now Kaliningrad Russia) 中穿过, 而河中有两个小岛, 小岛与河岸间由 7 座桥彼此连接连接于是有游客提出问题 : 能否从河岸或小岛或小岛出发, 通过每一座桥, 而且仅仅通过一次, 最后回到原地图论 Graph Theory 高晓沨 (XiaofengGao) Department of Computer Science Shanghai Jiao Tong Univ. 2 欧拉解瑞士数学家欧拉 (Leonhard Euler) 在 1736 年发表论文哥尼斯堡的七座桥, 对这个问题给出了否定的回答他将河岸和小岛作为图的顶点, 七座桥为边, 构成一个无向图, 则问题化为图论中的问题这是用图论方法建立的第一个模型 ( 图论的元年 ) More Examples Train Maps 3 4

2 More Examples (2) More Examples (3) Chemical Models 5 6 More Examples (4) More Examples (5) Family/Genealogy Tree Airline Traffic 7 8

哈密顿图 1859 年, 爱尔兰科学家哈密顿 (Sir William Rowan

个正五边形的面,20 个顶点,30 条棱 ),20 个顶点标上世界著名大城市的名字,

(Icosian) 问题, 即找一条经过所有顶点 ( 城市 ) 的圈周游世界游戏

Gao 9 2016/11/29 DiscreteMaths--Xiaofeng

3 哈密顿图 1859 年, 爱尔兰科学家哈密顿 (Sir William Rowan Hamilton) 发明了一个游戏 : 有一个实心的正十二面体 (12 个正五边形的面,20 个顶点,30 条棱 ),20 个顶点标上世界著名大城市的名字, 要求游戏者从某一城市出发, 遍历各城市一次, 最后回到原地这就是绕行世界 (Icosian) 问题, 即找一条经过所有顶点 ( 城市 ) 的圈周游世界游戏图例三维示例 /11/29 DiscreteMaths--Xiaofeng Gao /11/29 DiscreteMaths--Xiaofeng Gao 10 四色定理地图四色定理在 1853 年由古德里 (Francis Guthrie) 提出四色定理任意划分一个图形并给各部分着上颜色, 使任何具有公共边界的部分颜色不同, 仅需要四种颜色 1976 年美国数学家阿佩尔 (K.Appel) 与哈肯 (W.Haken) 借助电子计算机获得了四色定理的证明, 为用计算机证明数学定理开拓了前景 11 12

4 形象美丽而性质奇特的图 Petersen Family 妖怪图 (Snark Graph) 每个点关联三条边边染色需用四种颜色, 使公共顶点的边异色任意切断三条边不会断裂成两个有边的子图 ( 除单点 ) Y-Δ 变换 ( 星角变换 ) Single Star Snark (Petersen Graph) Double Star Snark Snark Family 图论的发展世纪的数学家仅将图论视为一般的数学游戏, 并未及时获得足够的发展 1936 年, 匈牙利数学家柯尼希 (Konig) 出版图论第一本专著有限图与无限图理论有限图与无限图理论, 总结了图论 200 年的成果 20 世纪中后期, 随着计算机领域的开拓, 图论得到长足发展, 现已成长为数学科学一个重要的独立学科分支 : 算法图论极值图论网络图论代数图论随机图论模糊图论超图论等

5 图论的研究对象世界由事物组成, 事物之间有联系图可以直观地描述事物及其间联系用结点表示事物用边表示它们之间的联系可见, 图模型几乎可用于任何领域图论 (graph theory) 就是以这种结点和边构成的图为研究对象目录 1 图的基本概念 2 图的基本性质 3 图的代数表示图论是简朴而机敏的学科王树禾无向图的基本概念 Basics Concepts for Undirected Graph 图的定义定义定义称二元组 G=(V, E) 是一个无向图 (undirected graph), 如果 V 是一个非空有限集合, E 是 V 中元素的无序对所组成的集合把 V 的元素叫做图的顶点 (vertex),e 的元素叫做图的边 (edge) V(G) 表示图 G 的顶点集,E(G) 表示图 G 的边集若 V(G) =n,, 则称 G 为 n 阶图 19 20

6 有限图 vs 无限图有限图 :V 和 E 是有限集合无限图 :V 或 E 是无限集合我们只讨论有限图 : V = {v 1, v 2,, v n }; E = {e 1, e 2,, e m } e k 可记为无序或有序的顶点对 (v i,v j ). 称 e k 与 v i,v j 关联 ; e k 连接 v i 和 v j ; v i,v j 是 e k 的端点 ; 称 v i 和 v j 相邻 (adjacent 或 neighbors) 以后不加说明时, 都假定图有 n 个顶点,m 条边. 简单图 vs 多重图孤立点 : 不与任何边关联的顶点环 (loop): : 两端点重合的边. 即 e k = (v i,v i ) 重边 (multiple edges): : 若两结点间有两条或两条两条或两条以上的边, 则这些边称为重边多重图 (multigraph): : 有重边的图简单图 (simple graph): : 无重边无自环的无向图空图 (null/empty graph): : 无边的简单图, 记作 N n 有的书定义空图是 (, ),, 也称为零图完全图 (complete graph): : 任意两结点间都有边的简单图 n 个顶点的完全图记作 K n 平凡图 : 只有一个顶点的图节点的度定义定义在无向图 G 中, 对于每个 G 中的顶点 v,, 与 v 相关联的边的数目称为 v 的度 (degree), 记为 d G (v),, 或 d(v) 并规定在计算关联边数目时, 环算作两条边注 : 度为 1 的顶点称为悬点, 与悬点关联的边称为悬边度为奇数的点称为度为奇数的点称为奇点奇点, 度为偶数的点称为偶点偶点每个顶点的度都相同的图称为每个顶点的度都相同的图称为正则图, 若其顶点的度均为 k,, 则称为 k- 正则图易知完全图 K n 是 (n-1)- 正则图握手定理 (Handshaking Theorem) 定理定理在无向图 G=(V, E) 中, 结点度数的总和等于边数的两倍, 即 d( v) = 2E 证当对图 G=(V, E) 的所有顶点的度求和时, 每条边都为顶点的度之和贡献 2,, 因为一条边恰好关联 2 个 ( 可能相同 ) 顶点这意味着顶点的度之和是边数的 2 倍定理得证上述定理有时也称为握手定理握手定理 v V 23 24

7 推论推论推论无向图中奇点数目是偶数推论推论非空简单图中一定存在度相同的点. 推论推论 1 Kn的边数是 nn ( 1) 2 例设图 G 有 10 个顶点, 每个顶点的度为 6, 那么图中共有多少条边? 解由握手定理得, 在 G 中所有顶点的度的总和为 6 10 = 60,, 因此图 G 中共有 30 条边有向图的基本概念 Basics Concepts for Directed Graph 无向图 vs 有向图无向边 (undirected edge): 边无方向. 对无向边 e k = (v i, v j ), v i 和 v j 称为 e k 的端点. 有向边 (directed edge): 边有方向. 对 e k = (v i, v j ): v i 称始点 (initial vertex), v j 称终点 (terminal vertex). v i 是 v j 的直接前趋, v j 是 v i 的直接后继. 无向图 (undirected graph): 都是无向边. 有向图 (directed graph): 都是有向边. 混合图 : 既有无向边也有有向边. 基本概念设 G 是有向图,e=(u,v) 是 E 中元素, 则称 u 为 e 的起点或尾,e 为 u 的出边 ; 并称 v 为 e 的终点或头,e 为 v 的入边对于环而言, 起点和点和终点是点是重合的若两条或两条以上的边有相同的头和尾, 则这些边称为边称为重边没有重边和环的有向图称为边和环的有向图称为简单有向图简单有向图 27 28

8 完全图与竞赛图若对任意的 u, v V, 均有 (u, v) E 和 (v, u) E,, 则称 D 为有向有向完全完全图设 D 为有向简单图, 若对任意的 u, v V, 有向边 (u, v) E 和 (v, u) E 有且仅且仅有一个成立, 则称 D 为竞赛竞赛图结点的度定义定义在有向图中, 顶点 v 的出边数称为 v 的出度, 记作 d + (v) 顶点 v 的入边数称为 v 的入度, 记作 d - (v) 顶点 v 的关联边数称作 v 的度, 记为 d(v),, 即 + d( v) = d ( v) + d ( v) 基本性质定理定理对有向图, 有 v V + d ( v) = d ( v) v V 证因为每条边都有一个因为每条边都有一个起点和一个点和一个终点点, 所以在带有有向边的图里, 所有顶点的入度之和等于出度之和显然显然也等于图的边数 = E 基础图与定向图定义定义设 D 是有向图, 若略去略去边的方向, 则得到一个无向图, 称其为图 D 的基础基础图如果 D 是无向图, 给所有的边任意定方向后, 则得到一个有向图, 称为图 D 的定向图定向图 31 32

9 示例例给出以下有向图的有向图的基础基础图图, 并给出其基础图的图的另一个定向图 a) b) 解上图的上图的基础基础图为左图, 再为其边为其边指定方向, 得到另外另外的定向图之一, 如右图顶点的邻点无向图 G 中, 顶点 v 的邻点集定义为 Γ(v) = {u (v,u) E(G)} 有向图 G 中, 顶点 v 的直接后继集或集或外邻外邻集定义为 Γ + (v) = {u (v,u) E(G)} v 的直接前趋接前趋集或集或内邻内邻集定义为 Γ (v) = {u (u,v) E(G)} 图的基本性质 Basic Properties of Graph 二部图 ( 二分图 ) 定义定义设 G 是简单图, 若其顶点集 V 可以划分为两个为两个不相交的非空集合 V 1 和 V 2, 而 G 中所有边都连接 V 1 中的一个顶点和 V 2 中的一个顶点 ( 也就是说 G 中没有边有边连接连接着 V 1 中的两个顶点或 V 2 中的两个顶点 ), 那么将 G 称作二部图或偶图偶图若图可以划分划分为两个为两个不相交的非空集合, 其元素个数分别分别为 m 和 n, 而在两个顶点之间有边相连当且仅且仅当这两个顶点当这两个顶点分属分属两个集合, 则将图称为完全完全二部图, 记作 K m,n 35 36

r 部图星 :K 1,n 称作星完全 r 部图 : 若顶点集合分成两两不交的 r 个子顶点集, 当且仅且仅当两个顶点不两个顶点不在同一个子顶点集时, 这两个顶点相连, 则称图 G 是完全 r 部图, 记做 K m1,m2,,mr 若每个子顶点集等势 ( 顶点个数为 m), 则记为 K r(m) 示例例判断判断下图 G 和 H 是否二部图 K 1,7 K 4(3)

的顶点集分成两个成两个不相交的集合, 则两个集合之一必然包含两个顶点两个顶点假如这个图是二如这个图是二部图图, 那么这两个顶点就不能用边能用边连接, 但是在 K 3 里每一个顶点都用边连接连接着其他每个顶点同理可知 K n 也不是二是二部图 39 子图定义定义若 V(H) V(G),E(H) E(G), 则称图 H 是图 G 的子图 (subgraph), 记作

10 r 部图星 :K 1,n 称作星完全 r 部图 : 若顶点集合分成两两不交的 r 个子顶点集, 当且仅且仅当两个顶点不两个顶点不在同一个子顶点集时, 这两个顶点相连, 则称图 G 是完全 r 部图, 记做 K m1,m2,,mr 若每个子顶点集等势 ( 顶点个数为 m), 则记为 K r(m) 示例例判断判断下图 G 和 H 是否二部图 K 1,7 K 4(3) 37 答 :G 的顶点集可以分为两个不相交的集合 {a, b, d} 和 {c, e, f, g} 而 H 不是二部图, 因为 H 中 a, e, f 三个顶点两两相邻, 根据鸽笼原理, 它们不可能分配到两个子集中使得边 (a, e) (e, f) (a, f) 均连接不同子集的两个顶点 38 示例例 K 3 不是二是二部图图注意若把 K 3 的顶点集分成两个成两个不相交的集合, 则两个集合之一必然包含两个顶点两个顶点假如这个图是二如这个图是二部图图, 那么这两个顶点就不能用边能用边连接, 但是在 K 3 里每一个顶点都用边连接连接着其他每个顶点同理可知 K n 也不是二是二部图 39 子图定义定义若 V(H) V(G),E(H) E(G), 则称图 H 是图 G 的子图 (subgraph), 记作 H G 若 H G, 且 H G, 则称 H 是 G 的真子真子图, 记为 H G 或 H G 若 H G, V(H)=V(G), 则称 H 是 G 的生成子图或支撑支撑子图 (spanning subgraph) 如果 V(H) V(G), 且中包含包含了 G 在节点集 V(H) 中的所有边, 则称 H 是 G 的导出子图 (induced subgraph) 平凡子图 : G 和 N n 40

11 例 : 子图下图中 G 和 G 都是 G 的子图 G 是 G 的导出子图, 而 G 不是 G 是 G 的支撑子图, 而 G 不是 41 图的运算定义设 G 1 =(V 1, E 1 ) 和 G 2 =(V 2, E 2 ) 是两个简单图, 则它们的并定义为 G =(V, E), 其中 V=V 1 V 2, E=E 1 E 2, 记作 G=G 1 G 2 G=G 1 G 2 =(V 1 V 2, E 1 E 2 ) 它们的交定义为 G=(V, E),, 其中 V=V 1 V 2, E=E 1 E 2, 记作 G=G 1 G 2 G=G 1 G 2 =(V 1 V 2, E 1 E 2 ) 它们的对称对称差定义为 G=(V, E), 其中 V=V 1 V 2, E=E 1 E 2, 记作 G=G 1 G 2 G=G 1 G 2 =(V 1 V 2, E 1 E 2 ) =(V 1 V 2, (E 1 E 2 ) (E 2 E 1 )) 42 图的运算 ( 续 ) 若 G 2 是 G 1 的子图, 则定义差 : G 1 G 2 =(V 1, E 1 E 2 ) n 个结点的简单简单图 G 的补图 G: K n G 显然 :G = G 从 G 中删去删去结点 v 及其关联的边 : G v 显然 :G v 是 G 的导出子图从 G 中删去删去边 e: G e 显然 :G e 是 G 的支撑子图向 G 中增加增加边 e ij =(v i, v j ): G +e ij 示例例下图中 G 1 和 G 2 并交交和对称和对称差分别是 (a),(b) 和 (c) (d) 是 G 1 的补图 43 44

12 图的同构定义定义对于简单对于简单图 G 1 =(V 1, E 1 ),G 2 =(V 2, E 2 ),, 如果能建立 V 1 到 V 2 的双射 f,, 其中 G 1 中的顶点 a 和 b 相邻, 当且仅且仅当 G 2 中的顶点 f(a) 和 f(b) 也相邻, 则称 G 1 与 G 2 同构 (isomorphic), 记作 G G 1 2 若 G 1 G 2, 则有 a) V(G 1 ) = V(G 2 ), E(G 1 ) = E(G 2 ) ; b) G 1 和 G 2 结点度的非增序列相同 ; c) G 1 的任一导出子图出子图在 G 2 中都有与之同构的导出子图 ; 反之亦然. 例 : 同构下图显示了图 G 与它的补图同构 Ulam 猜想 (1929) G 与 H 是两个顶点个数相等的图令 V(G)={v 1,v 2,,v n }; V(H)={u 1,u 2,,u n } 如果 G-v i H-u i (i=1,,n),, 则 G H 47 赋权图定义定义如果给图 G=(V,E) 的每条边 e k 都赋以一个实数 w k 作为该边的边的权 (weight), 则称 G 是赋权赋权图. 特别地, 如果权都是正数, 称为正权图. 应用中用中往往往往是赋权赋权图. 权可以表示可以表示长度时间费费用等. 例右图中 w AB =3 w BC =20 w AC =4 48

13 例题例证明任意 6 个人中必有三人三人相互认识互认识或者有三人互不相不相识. 证作 K 6 并给边涂色 : 红 = 认识, 蓝 = 不认识. 只要证图中必有同色有同色三角三角形. v 1 有 5 条边, 由抽屉抽屉原则原则必有三边同色 ( 设为红 ), 这三边的边的另一顶点一顶点设为 v 2, v 3, v 4. v 2 v 3 v 4 有一边为红色, 则与 v 1 构成红色 ; v 2 v 3 v 4 的三边无边无红色, 则构成蓝色. Xiaofeng Gao 49

<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074>

<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074> 图论王智慧复旦大学计算机学院图的基本概念图的概念通路与回路图的连通性图的矩阵表示图的运算 2 无序积, 多重集定义 : 设 A 和 B 为任意的两个集合, 称 { {a, b} a A, b B } 为 A 与 B 的无序积, 记做 A&B. 定义 : 元素可以重复出现的集合称为多重集, 其中某元素重复出现的次数称为该元素的重复度. 例如 : {a, a, b} 为一个多重集, 其中元素