运4

应用运筹学 应用运筹学 科学与研究类通识课程 浙江大学数学系 谈之奕 应用运筹学 第四章 图与网络优化 （Graph and Network Optimization） 应用运筹学 2 图 • 有序三元组 称为（无向） 图（graph） • 为顶点集， 中元素称为顶点（vertex） • 为边集， 中元素称为边（edge） • 为 到 的函数，称为关联函数 （incident function） • 图可以用以点示顶点，以曲线段表 示边的图形来表示，但图与上述表示 中点和曲线段在图形中的相对位置无 关 ( , , )G V E  1 2 3 4{ , , , }V v v v v 1 2 3 4 5 6 7{ , , , , , , }E e e e e e e e 1 1 3 2 1 2 3 1 4 4 5 2 3 6 7 2 4 ( ) ( , ), ( ) ( , ), ( ) ( , ), ( ) ( ) ( , ), ( ) ( ) ( , ) e v v e v v e v v e e v v e e v v               1e 2e 3e 4e 5e 6e 7e 1v 2v 3v 4v V V E E E V V 应用运筹学 3 顶点与边 • 若 ，则称 为 的端点 （endpoint），也称 与 关联（incident） • 与同一个顶点关联的两条边或与同一条边关联的 两个顶点称为相邻（adjacent） • 若 的像集 中的元素为有序对，则称 相应的图 为有向图（digraph） • 有向图中的边也称作弧（arc） • 若 ，则称 为 的起点， 为 的终 点 • 对图中每条边 赋予权重 ，可得赋权图 ( ) ( , )e u v  V V ,u v e ,u v e ( , , )D V A  ( ) ( , )a u v  u va a e )(ew 4v2v 3v1v 4v2v 3v1v 基础图 应用运筹学 4 子图与图的运算 • 图 称为图 的 子图（subgraph），若 ， 且 是 在 上的限制 • 生成子图： • 导出子图： ， ， ， • 图的补，两个图的并、积 ( , , )G V E ' ( ', ', ')G V E  'V V 'E E 'V V '( )G V '\G V '( )G E '\G E '  'E 2e 1v 2v 1 2({ , })G v v 3v 4e 5e 6e 7e 2v 4v 1e 2e 3e 4e 5e 6e 7e 1v 2v 3v 4v 1e 3e 1v 3v 4v1\{ }G v 1 3({ , })G e e 4e 5e 6e 7e 1v 2v 3v 4v 1 2 3\{ , , }G e e e 应用运筹学 5 简单图 • 两端点相同的边称为环（loop），两端点 分别相同的两条边称为平行边（parallel edges） • 既没有环，也没有平行边的图称为简单图 （simple graph） • 任何两个不同顶点之间都有边相连的简单 图称为完全图（complete graph） • 若图的顶点集可以划分为两个非空集合 和 ，使得 中任何两顶点之间无边相 连，则称该图为二部图（bipartite graph） 5K完全图 完全二部图 3,2K X Y ( )X Y 应用运筹学 6 路与连通 • 顶点和边交替出现的序列 称为连接顶 点 和 的长度为 的途径（walk） • 若图为简单图，则可省略途径中边的符号 • 若图为有向图，所有边的方向均为自 指向 ， 为从 到 的 有向途径 • 经过边互不相同的途径称为迹（trail），经过顶点互不相 同的迹称为路（path），起点和终点相同的路称为圈 （cycle） • 若图中任何两个端点之间都有路相连，则称图是连通的 （connected） 0 1 1 2 k ki i i i i i W v e v e e v  0i v ki v k ji v 1ji v  W 0iv kiv 应用运筹学 7 度 • 与顶点 关联的边的数目称为 的度（degree），记为 • 和 分别表示图的最大度和最小度 • 度为 的点称为孤立点（isolated vertex） • 所有顶点度相等的图称为正则图（regular graph） • 有向图中以 为起点的弧的数目称为 的出度（out degree），以 为终点的弧的数目称为 的入度（in-degree） • （Handshaking定理） • 无向图中度为奇数的顶点总有偶数个 v )(vdG Δ( )G v ( )G 0 ||2)( Evd Vv G   v v v v 应用运筹学 8 平面图 • 若存在 的一种图形表示，使得 除端点外，任何两条边均不相 交，则称 为平面图（planar graph） • 均为平面图，但 均不是平面图 • 非空平面图 将平面划分成的连 通区域 称为 的面。 的 对偶图（dual graph）以 为 顶点， 之间有边相连当且仅 当 的边界有公共边 G G 1v 2v 3v 4v 5v 1v 2v 3v 4v 5v 1v 2v 3v 1u 2u 3u 3u 2v 3v 1u 2u 1v 5 3,3\{ }, \{ }K e K e 5 3,3,K K G 1, ,f f G G 1, ,f f ,i jf f ,i jf f 应用运筹学 9 简单无向图的性质 • 若 连通，则 ；若 无圈，则 • 是二部图当且仅当 中不含奇 圈 • 连通 正则图必为圈 • 无圈图称为森林（forest），连通 无圈图称为树（tree） • 完全图 有 颗不同的生成 树 G | | | | 1E V  G | | | | 1E V  4K nK 2nn GG 2 应用运筹学 10 最小生成树 • 赋权图的所有生成树中总权和最 少的生成树称为最小生成树 （minimum spanning tree，MST） • Kruskal 算法 • 将边按权非降顺序排列 • 加入不会导致圈出现的边 Otakar Borůvka （1899－1995） 捷克数学家2 2 1 3 3 34 6 6 6 7 8 × ×× × 贪婪思想 拟阵（matroid） Joseph Bernard Kruskal (1928 –2010) 美国数学家、 计算机科学家 应用运筹学 11 最短路 • 连接赋权图中两个顶点 之间总权和最小的路称 为最短路（shortest path） • Dijkstra算法 • Bellman–Ford算法：负 权图 • Floyd–Warshall算法： 所有点对之间的最短路 Otakar Borůvka （1930 –2002） 荷兰计算机科学家 1972年Turing奖得主 Robert W Floyd （1936 –2001） 美国计算机科学家 1978年Turing奖得主 动态规划 应用运筹学 12 图的应用 • 一群人中任两人要么互相认识，要么互相不认 识，则总有两人认识的人数相同 • 以每一人为一个顶点，两个顶点之间有边相连当且仅 当相应的两人互相认识。每人认识的人数为顶点的度 • 若顶点数为 ，且不存在两人认识的人数相同，则 个顶点的度为 • 度为 的顶点必与所有其他顶点有边相连，故不存 在度为 的顶点 n n 1n  0,1, , 1n  0 矛盾 应用运筹学 13 1 2 3 黑白易位 • 一 方格棋盘，第一行左、 右两个方格各置一匹黑马，第 三行左、右两个方格各置一匹 黑马，按国际象棋中马的走子 规则，如何用最少的步数将黑 马白马的位置互换 • 将每个格子作为图的一个顶 点，对应两个格子的顶点之间 有边相连当且仅当马能从一个 跳到另一个 3 3 4 5 6 7 8 9 1 6 4 9 8 7 3 2 应用运筹学 14 匹配 • 的非空子集 称为 的一个匹配 （matching），若 中任何两条边在 中均不相邻 • 若 中所有顶点都与匹配 中某条边 关联，则称 为完美匹配（perfect matching） • 图中边数最多的匹配称为最大基数匹 配，赋权图中总权重最大的匹配称为 最大权匹配，赋权图中总权重最小的 完美匹配称为最小权完美匹配 完美匹配 最大基数匹配 GE M M G G M M 应用运筹学 15 匹配 任意图 二部图 最大权匹配最大基数匹配 Egervary，1931 Kuhn，1955 Edmonds，1965 Edmonds，1965 Jack Edmonds （1934－ ） 加拿大数学家 完全二部图的最小权完美匹配＝指派问题 Edmonds, J., Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449–467, 1965 Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices. Journal of Research National Bureau of Standards B, 69, 125–130, 1965 Blossom Algorithm 应用运筹学 16 Hall定理 • 设 为二部图，则 存 在匹配 ，使得 中的任一个顶点均 与 中某条边关联的充要条件是 这里 为 中所有与 相邻的顶 点集合 • 将52张扑克牌分成13叠，必可从每一 叠中抽出一张，使得抽出的13张牌包 含所有点数 Philip Hall （1904－1982） 英国数学家 ( , )G X Y E  G M XM | | | ( ) |, ,GS N S S X   ( )GN S G S 应用运筹学 17 Frobenius定理 • 设 为二部图，则 有完 美匹配 的充要条件是 且对任 意 或 ，均有 ( , )G X Y E  G | | | |X Y S X S Y | | | ( ) |GS N S Ferdinand Georg Frobenius （1849－1917） 德国数学家 M 应用运筹学 18 周游世界 • 1859年Hamilton发明了名为周游世界 的游戏 • 一个正十二面体的二十个顶点各代表一 个城市，是否有一条从某个城市出发， 沿正十二面体的棱行走，经过每个城市 恰好一次，最后回到出发城市的路线 William Rowan Hamilton 爱尔兰数学家 (1805-1865) Amsterdam, Ann Arbor, Berlin, Budapest, Dublin, Edinburgh, Jerusalem, London, Melbourne, Moscow, Novosibirsk, New York, Paris, Peking, Prague, Rio di Janeiro, Rome, San Francisco, Tokyo, Warsaw 应用运筹学 19 Hamiltonian图 • 称经过图的所有顶点恰好一次的圈为 Hamiltonian圈，存在Hamiltonian圈的 图为Hamiltonian图 • 判断图是否为Hamiltonian图是NP －完 全问题 • 为Hamiltonian图，Petersen图不是 Hamiltonian图 • 由Hamiltonian图问题的NP －完全性可 归约证明TSP问题是NP －完全的 nK 应用运筹学 20 Knight's tour • 在 国际象棋棋盘上，马能否按其 走子规则，从一个格子出发，经过其 它格子恰好一次，最后回到起点 • 构造“跳马图”，每一格子为图的一个顶 点，两个格子之间有边相连当且仅当马可 按走子规则从一个格子跳到另一个格子 • 方格棋盘对应的“跳马图” 为Hamiltonian图，除非 • 均为奇数 • 或 • 或 8 8 ( )m n m n  ,m n 1, 2, 4m  3, 4,6,8m n  Euler, L., Mémoires de l‘Academie Royale des Sciences et Belles Lettres, 15, 310–337, 1759 应用运筹学 21 1v 2v 3v 0v 4v 5v 独立集和顶点覆盖 • V 的子集 S 称为 G 的独立集 （independent set），若S中任 何两个顶点在 G 中均不相邻。 顶点数最多的独立集称为最大 独立集 • V 的子集 S 称为 G 的顶点覆盖 （vertex cover），若E中每条 边都与 S 中某点关联。顶点数 最少的顶点覆盖称为最小顶点 覆盖 1v 2v 3v 0v 4v 5v 与 都是独立 集，后者是最大独立集 与 都是顶点覆盖， 后者是最小顶点覆盖 }{ 0v },{ 52 vv },,,,{ 54321 vvvvv }, 43 vv ,,{ 10 vv 应用运筹学 22 独立集与顶点覆盖 • S 是 G 的独立集当且仅当V \ S是 G 的顶点覆盖 • 若V \ S 不是 G 的顶点覆盖，则存在 ，并 且 ，则 ，且 通过边 在 G 中相邻，S 不是 G 的独立集 • 若 S 不是 G 的独立集，则存在 ， ， 则 ，且 不与 V \ S 中的点关联，V \ S 不是 G 的顶点覆盖 • S 是 G 的最大独立集当且仅当 V \ S 是 G 的最 小顶点覆盖 Evu ),( SVvu \,  Svu , vu, ),( vu Svu , Evu ),( SVvu \,  ),( vu 应用运筹学 23 支配集 • V 的子集 S 称为 G 的支配 集（dominated set），若 对 G 中任意顶点 ，要么 有 ，要么 与 S 中某 个顶点在 G 中相邻。顶点 数最少的支配集称为最小 支配集 1v 2v 3v 0v 4v 5v 与 都是支配 集，后者是最小支配集 }{ 0v },{ 52 vv v Sv v v 应用运筹学 24 皇后问题 • 给定一张8´8的国际象棋 棋盘 • 最少几个皇后，放在哪些 方格中，才能吃掉对方任 何一个格子上的棋子 • 最多几个皇后，放在哪些 方格中，使得任一皇后吃 不掉任何其他皇后 应用运筹学 25 皇后问题 • 作一张含 64 个顶点的“皇 后图”，每个顶点代表棋 盘上一个方格，两个顶点 之间有边相连当且仅当能 吃子。上述两个问题分别 对应于最小支配集和最大 独立集问题 Karl Friedrich Gauss (1777-1855) 德国数学家 应用运筹学 26 皇后问题 最小支配集（五皇后问题） 最大独立集（八皇后问题） 应用运筹学 27 联络与监控 • 若干个城镇之间有一个通信网络，要在这些城镇 中选定几个建立中心台站，中心台站需与每个城 镇都有直通线路，且中心台站数目尽可能少。最 少台站数目即为最小支配集数目 • 现要在交通网中选择若干交叉路口处建立监控设 备，要求能控制所有的道路，且所用的设备尽可 能少。最少设备数目即为最小顶点覆盖数目 应用运筹学 28 顶点着色 • 图 G 的顶点 着色是指将图G 的 每一个顶点用 种颜色之一着 色，使得相邻的顶点不染同一种 颜色 • 将 G 的顶点按上述要求着色所 需的最少颜色数称为图 G 的色 数（chromatic number），记为 • 图的顶点着色问题等价于把图的 顶点集划分成若干个不相交的独 立集的并 Petersen 图， k k )(G 3)( G 应用运筹学 29 四色定理 • 设图 是任一平面图，则 • 地图着色可转化为其对偶图的顶点着 色问题 • 四色定理提出于1852年。1976年， 美国数学家Appel 和Haken利用计 算机证明了四色定理 4)( GG 可约构形组成的不 可免完备集（部分） Appel, K., Haken, W., Every Planar Map is Four Colorable, Illinois Journal of Mathematics Part I. Discharging, 21, 429–490, 1979 Part II. Reducibility, 21, 491–567,1979 应用运筹学 30 安全储藏问题 • 若要在仓库中储藏若干种化学制品，某些制 品若相互接触易发生爆炸。仓库应至少分为 多少个隔间，才能把不相容的化学制品贮藏 在不同的隔间里。 • 仓库应分的最少的隔间数即为图的色数，能 放在同一个隔间里的制品对应于图的一个独 立集 应用运筹学 31 边着色 • 图 G 的边 着色是指将图 G 的每一条边用 种颜色 之一着色，使得相邻的边 不染同一种颜色 • 将图 G 的边按上述要求着 色所需的最少颜色数称为 图 G 的边色数（edge chromatic number），记 为 Petersen 图， 4)(' G k k )(' G 应用运筹学 32 排课表问题 • 有 位教师和 个班级，教师 每天为班级 授 课 个学时，如何安排一张课表，可使每天课 时数最少 • 构造有平行边的二部图 ，顶点集 ， 为教师集， 为班级集， 中顶点 和 中顶点 有 条边相连 • 排课表问题等价于 的边着色问题，每天最少课 时数即为 nm i j ijp i j ijp YXV (G)' G X Y X Y G 应用运筹学 33 排课表问题           11000 01110 01010 01102 54321 yyyyy 4 3 2 1 x x x x 4321课时教师 4311 yyyy 42 yy 243 yyy 54 yy4 3 2 1 x x x x 4321 xxxx 54321 yyyyy 应用运筹学 34 排课表问题 • 若可以提供的教室数有限制，只能通过增加课时 来错开教室使用，若给定可用的教室数，则需安 排多少个课时 • 设 是二部图，对任意的 ， 中存在 个无公共边的匹配 ，使得iM pi p |E|M p |E|ME i p i i ,,1,||, 1        且 )(Gp  pG G 应用运筹学 35 排课表问题 4321 1314 yyyy 42 yy 243 yyy 45 yy 3 5 6421 1134 yyyy 42 yy 234 yyy 54 yy 三间教室 两间教室 4 3 2 1 x x x x 4 3 2 1 x x x x 应用运筹学 36 网络流 • 有向图 ，弧 的容量 （capacity）为 。 有两个特殊顶 点 ，源（source）入度为 ，流 （sink） 出度为 。 也称作网络 • 记 为通过弧 的流量，满足以下 条件的 称为可行流 • 经过每条弧的流量不超过每条弧的容量，即 • 除源和流外，流入每个顶点 的流量等于流 出 的流量，即 ( , , )N V A  ),( ji vv iju  ,s t s t ijf ),( ji vv N 0 0 { }ijf f 0 ij ijf u  iv iv :( , ) :( , ) 0, , i j j i ij ji i j v v A j v v A f f v s t       Ahuja, R.K., Magnanti, T.L., Orlin, J.B., Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993. N 应用运筹学 37 最大流 • 若 为可行流，则流 出源 的流量与流入 流 的流量相同，称 其为 的流量 • 求一网络流量最大的 可行流问题称为最大 流（maximum flow） s 可行流 图中弧上第一个数字表示 弧的容量，第二个数字表 示当前每条弧的流量 该可行流的流量为3 4v3v ts 3,1 2,2 3,2 1,0 1,1 2,2 2,1 2,11v 2v f t f 应用运筹学 38 2 割 • 设 ，且 ， 用 表示所有起点在 中，终点在 中的弧的全 体，称为网络的割（cut）， 割中弧的容量之和称为割量 • 网络中割量最小的割称为最 小割 VS  SVtSs \,  ),( SS S SV \ 4v3v ts 3 3 1 1 2 2 21v 2v S SV \ 割，割量为 4 应用运筹学 39 最大流与最小割 • （最大流最小割定理）任一网 络中，最大流量等于最小割量 • Ford和 Fulkerson 于1956 年证 明了最大流最小割定理，并提 出了最大流问题的一个算法， 但该算法不是多项式时间的。 Edmonds 和 Karp对该算法作 了改进，使之成为多项式时间 算法 最大流，流量为 4 1v 4v3v 2v ts 3,1 2,1 2,2 3,2 1,0 1,1 2,2 2,12,2 1,0 2,2 3,2 Ford., L. R., Fulkerson, D. R., Maximal flow through a network, Canadian Journal of Mathematics, 8, 399-404, 1956 应用运筹学 40 RAND 1954 Schematic diagram of the railway network of the Western Soviet Union and Eastern European countries, with a maximum flow of value 163,000 tons from Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as “The bottleneck” ——Harris, T.E., Ross, F.S., Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum-1573, The RAND Corporation,1955. 应用运筹学 41 js km 代表问题 • 学校从修读每门课程的同学中选择一名召开座谈 会，要求参加同学中来自专业 的学生数不超 过 。假设每位同学属于一个专业，修读若干门 课程 • 构造网络 ，顶点集为 • 对任意 ，弧 的容量为 • 若学生 修读课程 ，则弧 的容量为 • 若学生 属于专业 ，则弧 的容量为 • 对任意 ，弧 的容量为 • 代表问题有解当且仅当网络 的最大流流量为 { , }s t C S M  N ic ( , )i jc sjs km ( , )j ks m ( , )km t ku 课程集 学生集 专业集 1 1 1 ( , )is cic | |CN ku k 应用运筹学 谢 谢