图论GraphTheory-复旦大学数学科学学院

第一章 图形理论图形理论有明确的起始点，由瑞士数学家尤拉(Leonhard Euler, 1707-1783)于1736年发表的论文开始。

其研究的主要论点，乃在于解决当时的热门问题，即有名K önigsgerg 的七桥问题。

1.1 定义与例题定义1.1：令 V 为非空集合，且E V V ⊆⨯. 序对(),V E 称为(V 上)有向图(directedgraph or digraph)，其中 V 为顶点(vertex)或节点(node)的集合，E 为边(edge)的集合。

我们记(),G V E =表示此图形。

图1.1为{}, , , , V a b c d e =上有向图的例子，其中()()()(){}, , , , , , , E a a a b a d b c =。

边的方向由边上的有向箭头表示，如图所示对任意边，如(), b c ，我们说此边接合(incident)顶点, b c ；称b 邻接至(adjacent to) c ；或c 邻接自(adjacent from) b 。

此外， b 称为边的原点(origin)或源点(source)， c 称为终点(terminus or terminating vertex)。

边(), a a 为一个循环(loop)， 且顶点e 不与任何边接合，称为孤立点(isolated)。

若不考虑边的方向，此图称为无向图(undirected)。

定义1.2：令, x y 为无向图(), G V E =的顶点(不一定相异)。

G 中的X Y -路(x y -walk)是指选自G 的顶点及边的有限交错序列。

01122311,,,,,,...,,,,n n n n x x e x e x e e x e x y --==其中由顶点 1x 开始，终止于顶点y ，n 个边{}1,,1i i i e x x i n -=≤≤路的长度(length)是指该条路的边数n 。

图论学习笔记（2）基本概念设图G，u∈V(G)，v∈V(G)，u-v通道（u-v path）是指从结点u出发，经过一个交互的结点和边的序列，最后回到结点v的路径，其中连续的结点和边是关联的。

通道的长度（length）是指通道经过边的数量。

若一个通道中没有重复的边，则称该通道为迹（trace）。

（注：迹中的结点是可以重复的）若迹开始和结束于相同的结点，则称该迹是闭的（closed），称该迹为回路（loop）。

若一个通道中没有重复的节点，则称该通道为路（pathway）。

若u∈V(G)，v∈V(G)，则一个将u和v连接起来的路称为u-v路（u-v pathway）。

注：显然，如果结点不重复，则边必然不重复，所以，一个路也是迹，一个闭路称为圈（circle）。

若图中的任意两个结点间都存在路，则称此图为连通图（connected graph），否则，称之为非连通图（disconnected graph）。

在连通图中，各个分支称为连通分量，严格来说，图的连通分量指的是极大连通子图（[unknown]）。

若u∈V(G)，v∈V(G)，则节点u和v之间的测地线路是指长度最短的u-v路，简称测地线（geodesic）。

注：当你要在最短时间内从u到达v，测地线路是你的最佳选择。

途中可能存在多条测地线路。

测地线路也常被称为最短路。

图G的结点集V(G)，边集E(G)。

当图H满足结点集V(H)的子集，边集E(H)是E(G)的子集，边界对每一条边e=uv∈E(H)，其中u∈V(H)，v∈V(H)，则称图H是G的子图（subgraph），通常称图G为图H的超图（supergraph）。

定义结点都给以标号的图称为标记图（labeled graph），否则，称为非标记图（unlabeled graph）。

注：对标记图G，若S⊆V(G)，并且在标记图G中共有k条边连接了S中的所有结点，那么，G的以S为结点集的子图数为2k。

若V(H)=V(G)，则称子图H是图G的生成子图（spanning subgraph）。

图论学习笔记（3）基本概念图G中的结点u与v相邻接当且仅当它们在图H中的相应结点也邻接，则称图G与图H是同构的（isomorphic），记作G≈H，否则，称两者为非同构的（nonisomorphic）。

用函数描述同构：图G与图H同构，即存在一个一一映射函数 f : V(G) →V(H)，此时，图G中任何结点对u和v邻接当且仅当f(v)和f(u)在图H中邻接。

函数f 称作从G到H的同构函数（isomorphic function）。

相关推论：令函数 f : V(G) →V(H)为图G与图H的同构函数，那么，对任意结点u∈V(G),都有deg(u)=deg(v)，换句话说，如果两个图同构，则对应的结点有相同的度数。

设图G与H同构，同构函数为 f : V(G) →H(G)。

若在图G中，结点v1与v2间的测地线为v1,v2,v3,...,vk，则在图H中，f(v1),f(v2),f(v3),...,f(vk)是结点f(v1)与f(vk)间的测地线。

含n个结点的图G的度序列（degree sequence）是指按照节点度数排列的n-元非递增序列。

若一个非负整数的非递增序列S可以表示某个图的度序列，则称序列S是可绘的。

注：非递增序列可绘⇒图的结点度数之和是非负偶数。

相关算法：可绘图度序列的判定算法从序列S中删除第一个数k。

如果S的第一个数后的k个数都大于等于1，则将这k个数分别都减去1得到新序列S'；否则，停止，得出元序列不可绘图的结论。

若S'全是0，停止，得原序列为可绘图。

将步骤2得到的序列S'重新排序，得到非递增序列S*。

令S=S*，转不骤1。

图常量是指根据图的某个性质定义的函数，即同构图将具有相同的函数值。

注：如果f 是图常量，而f(G) ≠f(H)，则图G于图H不同构。

用来说明图是否同构的一些量：结点个数连通分量个数边数度序列具有给定唯一度数结点对间的测地线长度图中的最长路具有唯一度数结点的邻接点的度基本定理定理3.1 设S是由以上算法得到的序列，那么当且仅当S'是可绘图序列时，S是可绘图序列。

图论介绍（GraphTheory）1 图论概述1.1 发展历史第⼀阶段：1736：欧拉发表⾸篇关于图论的⽂章，研究了哥尼斯堡七桥问题，被称为图论之⽗1750：提出了拓扑学的第⼀个定理，多⾯体欧拉公式：V-E+F=2第⼆阶段（19~20世纪）：1852: Francis Guthrie提出四⾊问题1856: Thomas P. Kirkman & William R.Hamilton研究了哈密尔顿图1878: Alfred Kempe给出给出四⾊定理证明1890: 希伍德（Heawood）推翻原有四⾊定理证明1891: 彼得森（Petersen 丹麦）给出关于图论的理论知识的第⼀篇论⽂1936: 哥尼格(Dénes Kőnig Hungarian), 写出第⼀本图论专著《有限图与⽆限图的理论》，图论成为了⼀门独⽴学科第三阶段（现代图论）：1941: F. P. Ramsey开创 Extremal graph theory1959: Erd˝os and Rényi 引⼊随机图理论（边的存在的概率为p）1976: Kenneth Appel & Wolfgang Haken使⽤计算机最终证明了四⾊问题1.2 参考教材Graph Theory with Application - J.A. Bondy and U.S.R. Murty, Elsevier, 1976《图论及其应⽤》经典教材，吴望名译，有电⼦版Graph theory - J.A. Bondy and U.S.R. Murty, Springer, 2008《图论》GTM244，可以认为是 “Graph Theory with Application” 的第⼆版，推荐教材Graph Theory, 5th - Reinhard Diestel, Springer, 2017《图论》GTM173，有电⼦版Introduction to Graph Theory, 2nd- Douglas B. West, 2017⼊门教材2 图的初步知识（注：⼀般考虑simple graph (no graph loops or multiple edges), 且阶⼤于等于2）2.1 不规则图Definition: 所有顶点的度都不同的图叫不规则图 (irregular graph)Definition: 只有⼀对顶点的度相同的图叫⼏乎不规则图 (almost irregular graph)Theorem:1）不规则图不存在2）恰好存在两个阶数相同的⼏乎不规则图，且互为补图（顶点相同，边合起来是完全图）3）对于任意最⼤值为n的正整数集合，存在n+1阶的图，使其顶点数正好等于这些整数（以上结论不适⽤于多重图和加权图）2.2 正则图Definition: 所有顶点的度为r的图叫 r-正则图 (r-regular graph)e.g. 单连通的0-regular是单个点，单连通的1-regular是⼀条边的图，单连通的2-regular是⼀个圈，单连通的3-regular称为⽴⽅图Theorem: n阶r正则图存在，只要r, n不都是奇数，且r<=n-1常⽤正则图：Kn: n阶完全图，r = n-1Cn: n(n>=3)阶圈， r = 2Qr: n=2^r阶的超⽴⽅体(r-cube)Kr,r: n=2r阶的⼆分图2.3 ⼆分图（bipartite graph）Definition：顶点被分为两个集合，所有边只在两个集合之间连接的图叫⼆分图Theorem：图G是⼆分图\Leftrightarrow G中⽆奇圈2.4 ⼦图图G，⼦图（subgraph）Hsubgraph ---> spanning subgraph---> induced subgraph ---> vertex-delete subgraphspanning subgraph: ⽣成⼦图，H和G的顶点相同induced subgraph: 诱导⼦图，H = G[S] (从图中去除1个或多个顶点)vertex-delete subgraph: 去顶点⼦图，从图中去除1个顶点Theorem：任意图都可以表⽰为某个正则图的导出⼦图未解问题：给定某⼀图G的所有去顶点⼦图，是否能够重构出唯⼀的图G（同构意义上是唯⼀的）？2.5 距离Definition：连通图（connected），由多个连通分⽀（component）构成的图为不连通图（disconnected）G-v ⽐ G有更多的连通分⽀，则点v称为G的割点（cut-vertex）G-e ⽐ G有更多的连通分⽀，则边e称为G的桥（bridge）Theorem:连通图G，e是桥\Leftrightarrow e不属于G的任何⼀个圈\Leftrightarrow存在顶点u，v，使得任意路径u-v的路径经过e连通图G，w是割点\Leftrightarrow存在顶点u，v，使得任意路径u-v的路径经过wDefinition：点u, v之间的距离（distance）：u,v之间最短路径的长度d(u,v)点u的离⼼率（eccentricity）：u 与其它点的最⼤距离\epsilon(u)=\max\limits_v d(u,v)最⼩离⼼率为图的半径（radius），达到最⼩离⼼率的点为中⼼点（central vertex）最⼤离⼼率为图的直径（diameter），达到最⼤离⼼率的点为边缘点（peripheral vertex）2.6 TreeDefinition：不包含圈的连通图为树（Tree）Theorem：图G是树\Leftrightarrow G中任意两个顶点都有且只有⼀条连通路径n阶树有n-1条边在G内添加任意⼀条边，就会形成⼀个回路。

第一章 图形理论图形理论有明确的起始点，由瑞士数学家尤拉(Leonhard Euler, 1707-1783)于1736年发表的论文开始。

其研究的主要论点，乃在于解决当时的热门问题，即有名K önigsgerg 的七桥问题。

1.1 定义与例题定义1.1：令 V 为非空集合，且E V V ⊆⨯. 序对(),V E 称为(V 上)有向图(directedgraph or digraph)，其中 V 为顶点(vertex)或节点(node)的集合，E 为边(edge)的集合。

我们记(),G V E =表示此图形。

图1.1为{}, , , , V a b c d e =上有向图的例子，其中()()()(){}, , , , , , , E a a a b a d b c =。

边的方向由边上的有向箭头表示，如图所示对任意边，如(), b c ，我们说此边接合(incident)顶点, b c ；称b 邻接至(adjacent to) c ；或c 邻接自(adjacent from) b 。

此外， b 称为边的原点(origin)或源点(source)， c 称为终点(terminus or terminating vertex)。

边(), a a 为一个循环(loop)， 且顶点e 不与任何边接合，称为孤立点(isolated)。

若不考虑边的方向，此图称为无向图(undirected)。

定义1.2：令, x y 为无向图(), G V E =的顶点(不一定相异)。

G 中的X Y -路(x y -walk)是指选自G 的顶点及边的有限交错序列。

01122311,,,,,,...,,,,n n n n x x e x e x e e x e x y --==其中由顶点 1x 开始，终止于顶点y ，n 个边{}1,,1i i i e x x i n -=≤≤路的长度(length)是指该条路的边数n 。

1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与网络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization1.2.图的表示Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表示Star1.3.图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1.概念1.3.1.2.求无向连通图中的桥Finding bridges in undirected graph1.3.2.广度优先搜索Breadth first search (BFS)1.4.拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.无向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.无权图Unweighted1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路径与回路1.5.2.1.无权图Unweighted1.5.2.2.有权图Weighed —旅行商问题The travelling salesman problem1.6.网络优化Network optimization1.6.1.最小生成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制生成树Minimum degree-bounded spanning trees1.6.1.2.2.k小生成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1. ..................................................................................................... D ijkstra1.6.2.1.1.2. .......................................................................................... B ellman-Ford1.6.2.1.1.2.1.....................................Shortest path faster algorithm(SPFA)1.6.2.1.2.应用Applications1.6.2.1.2.1. ........................... 差分约束系统System of difference constraints1.6.2.1.2.2. .......................... 有向无环图上的最短路Shortest paths in DAG1.6.2.2.所有顶点对间最短路All-pairs shortest paths1.6.2.2.1.基本算法Basic algorithms1.6.2.2.1.1. ....................................................................................... F loyd-Warshall1.6.2.2.1.2. .................................................................................................... Johnson 1.6.3.网络流Flow network1.6.3.1.最大流Maximum flow1.6.3.1.1.基本算法Basic algorithms1.6.3.1.1.1. ........................................................................ Ford-Fulkerson method1.6.3.1.1.1.1.......................................................... E dmonds-Karp algorithm1.6.3.1.1.1.1.1. ................................................... M inimum length path1.6.3.1.1.1.1.2. ........................................... Maximum capability path1.6.3.1.1.2. ............................................... 预流推进算法Preflow push method1.6.3.1.1.2.1.................................................................................. P ush-relabel1.6.3.1.1.2.2........................................................................... Relabel-to-front1.6.3.1.1.3. .......................................................................................... Dinic method1.6.3.1.2.扩展模型Extended models1.6.3.1.2.1. ............................................................................... 有上下界的流问题1.6.3.2.最小费用流Minimum cost flow1.6.3.2.1.找最小费用路Finding minimum cost path1.6.3.2.2.找负权圈Finding negative circle1.6.3.2.3.网络单纯形Network simplex algorithm1.6.4.匹配Matching1.6.4.1.二分图Bipartite Graph1.6.4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.一般图General Graph1.6.4.2.1.无权图-带花树算法Unweighted - Blossom (Edmonds)1.图论Graph Theory1.1. 定义与术语Definition and Glossary1.1.1.图与网络Graph and Network二元组(),V E称为图(graph)。

图论学习笔记（9）距离与连通性基本概念设u和v为图G中给定的两个结点，则两者间的距离是指G中任意u-v测地线中边的数目，记作d(u,v)。

图论中的距离函数满足如下公理（这三个公理称为三角不等式）：d(u,v) ≥0，当且仅当u = v 时，d(u,v) = 0。

对任意结点u、v都有d(u,v) = d(v,u)。

对任意结点u、v和w都有d(u,v) ≤d(u,v) + d(w,v)。

设v为图G的给定结点，v的偏心距是指v与和它相距最远的结点间的距离e(v)，用数学公式表示为：e(v) = d(u,v)。

相关结论：对图G的某个结点v若有e(v) = t，则：图G的任意其他结点与v间的距离都不大于t。

图G中至少存在一个结点与v间的距离为t。

若结点w满足d(v,w) = e(v)，则称w为偏心结点。

若两个结点中的任意一个都是另一个的偏心结点，则称它们是互为偏心的。

图G的所有结点中最小偏心距称为G的半径，记作rad(G)。

具有最小偏心距的结点组成的集合称为G的中心，记作C(G)。

图G的边界是指具有最大偏心距的结点组成的集合，记作P(G)。

图G中最大偏心距称为G的直径，记作diam(G)。

非平凡图的边界至少包含一对结点u、v，满足d(u,v) = diam(G)，此对结点称为相对结点对或者径向结点对，其中的一个结点为另一个结点的相对结点。

相对结点总是互为偏心的。

注：其逆命题不成立。

中心结点集中的某个结点与其偏心结点间的测地线称为半径路，其长度必然是rad(G)。

相对结点对间的测地线称为直径路，其长度必然是diam(G)。

图论学习笔记（8）基本概念图的匹配M是有一些边组成的集合，其中的任何两个边都不关联。

注：设X，Y是二分图G中的两个部分，则图G一个匹配中的每一条边关联的两个结点满足：一个在X中，另一个在Y中。

事实上，图G的每条边也都满足。

若X中的每个结点都关联于匹配M中的一条边，则称M为从X到Y的一个完全匹配。

注：此时M未必是从Y到X的一个完全匹配。

若M是从X到Y的一个完全匹配也是从Y到X的一个完全匹配，则称M为一个完美匹配。

这要求|X| = |Y|，即图G是平衡的，从X到Y的一个完全匹配仅要求|X|≤|Y|。

若匹配M在图G的所有匹配中最大，则称M为最大匹配。

也就是说，若M'是图G的任意一个匹配，则|M'|≤|M|。

若不存在更大的匹配M'包含匹配M，则称M为一个极大匹配。

因此，极大匹配是指不能通过增加边而扩大的匹配。

设M是图G的一个匹配。

图G的M-交错路是由在M中的边和不再M中的边交替出现构成的。

若结点v与M中的某条边相关联，则称v为M-匹配的，否则，称v为M-不匹配的。

M-增广路是指连接两个M-不匹配结点的交错路。

注：M-增广路不必包含M的所有边。

M-增广路开始并终止于不在M中的边。

基本定理定理8.1 Berge匹配定理图G的匹配M是最大匹配当且仅当G中没有M-增广路。

预备：对于结点v，用n(v)表示所有与v邻接的结点集。

对于图G结点集的任意子集S，N(S)表示所有与S中的结点相邻接的结点集的并集，即N(S)=n(v)。

定理8.2 Hall匹配定理二分图G的两个部分为X、Y，若存在从X到Y的完全匹配当且仅当对任意S⊆X，都有|N(S)|≥|S|。

定理8.3 Hall婚配定理二分图G的两个部分X、Y满足|X| = |Y|时，图G存在完美匹配当且仅当对任意子集S⊆X，都有|N(S)| ≥|S|。

引理8.3.1 正则二分图G一定平衡，即G的两个部分X、Y一定有相同的结点数。

定理8.4 若二分图是正则图，则它一定存在完美匹配。