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 theory
1959: 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)
< 单连通的0-regular是单个点，单连通的1-regular是⼀条边的图，单连通的2-regular是⼀个圈，单连通的3-regular称为⽴⽅图Theorem: n阶r正则图存在，只要r, n不都是奇数，且r<=n-1
常⽤正则图：
Kn: n阶完全图，r = n-1
Cn: n(n>=3)阶圈， r = 2
Qr: n=2^r阶的超⽴⽅体(r-cube)高一化学教学反思
Kr,r: n=2r阶的⼆分图
2.3 ⼆分图（bipartite graph）
Definition：顶点被分为两个集合，所有边只在两个集合之间连接的图叫⼆分图
Theorem：图G是⼆分图\Leftrightarrow G中⽆奇圈
2.4 ⼦图
图G，⼦图（subgraph）H
subgraph ---> spanning subgraph
---> induced subgraph ---> vertex-delete subgraph
spanning 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的路径经过w
Definition：
点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 Tree
Definition：不包含圈的连通图为树（Tree）
Theorem：图G是树\Leftrightarrow G中任意两个顶点都有且只有⼀条连通路径
n阶树有n-1条边
在G内添加任意⼀条边，就会形成⼀个回路。
去掉任意⼀条边，就不再连通。
G内的任意两个顶点能被唯⼀路径所连通。
⼀颗树的每⼀个节点都可以作为根
Definition：叶⼦（leaf）：树中度为1的节点
Theorem：树⾄少有两个节点
Definition：⽣成树（spanning graph）：图G的⽣成⼦图T是树，则T称为G的⽣成树
最⼩⽣成树：加权边之和最⼩的⽣成树
克鲁克斯算法：依次选择最⼩权的边，但保证不形成圈，可以⽣成最⼩⽣成树
3 图的遍历
Definition：
对于某个顶点序列（v1，v2，..., vk）
通路 (walk) ---> 路径 (path) ---> 圈 (circle)
---> 迹 (trail) ---> 回路 (circuit)
闭合的含义：v1=vk
walk: 所有 vi-vi+1 都是图的边
path: 所有的顶点不重复，闭合path为circle
trail: 所有边不重复. 闭合trail为circuit
注：path -> trail, circle -> circuit
3.1 欧拉图问题（遍历所有边不能重复，⼀笔画问题）
欧拉回路 (Eulerian circuit): 包含G中所有边的回路
欧拉迹 (Eulerian trail or Eulerian tour): 包含G中所有边的迹
包含⼀个欧拉回路的连通图为欧拉图
Theorem：
连通图G是欧拉的\Leftrightarrow每个顶点的度是偶数，（注：G可以是多重图）
连通图G含有欧拉迹\Leftrightarrow图G中恰好有两个顶点是奇数度（注：G可以是多重图，欧拉迹从这两个奇数度的顶点开始和结束）3.2 中国邮递员问题（遍历所有边可以重复）
Definition：欧拉通路：经过G的所有边的最短闭通路
到欧拉通路的⽅法：对奇数度的顶点添加多重边，使每个顶点的度都是偶数
Theorem：欧拉通路⼀定经过G中的桥两次（注：也即是是说讲桥复制为欧拉多重图）
注：加权图也可以⽤类似思路解决
3.3 哈密尔顿问题 (遍历所有点不能重复)
Definition：经过图中所有顶点的圈为哈密尔顿圈，包含哈密尔顿的圈为哈密尔顿图。
还没有任何理论可以精确判定⼀个图是否是哈密尔顿图，但已有如下结论
Theorem:
设G是⼀个n阶图，每个顶点的度>=n/2, 则G为哈密尔顿图；
（奥尔定理）如果n阶图G中任意⼀对不相邻的顶点的度数和⼤于等于n，则G是哈密尔顿图；
如果G是哈密尔顿图，那么任意去掉G的k个顶点，剩余的图最多含有k个连通分⽀；
3.4 旅⾏商问题（遍历所有点可以重复）(TSP)
TSP（Traveling Salesman Problem），通过优化算法求解
4 图的匹配和分解
4.1 匹配（Matching）
（研究⼆分图中两个集合中元素的配对问题）
Definition: ⼀组互不相邻的边组成的集合叫做匹配（matching）（匹配的概念可以⽤于所有的图）
相异代表系：n个⾮空集合，每个集合挑出⼀个元素，这n个元素互不相同。因此，集合系有相异代表系，等价于对应的⼆分图（集合系和元素组成⼆分图的顶点集合）含有⼤⼩为n的匹配。
（霍尔定理 Philip-Hall's Theorem）n个⾮空集合存在相异代表系\Leftrightarrow任意k个集合的并，含有不少于k个元素（k=1,…,n）。
Definition: G中包含边最多的匹配为最⼤匹配
Definition: 匹配覆盖了图中所有的顶点的匹配为完美匹配 (n阶图的完美匹配的⼤⼩为n/2)
(塔特定理) 图G有完美匹配\Leftrightarrow对于任意⼀个顶点的真⼦集S，都有 k0(G-S) <= |S|, 其中k0(
G)表⽰G中奇数阶连通分⽀的数量
1-regular graph有完美匹配
2-regular graph有完美匹配\Leftrightarrow G中每个连通分⽀都是⼀个偶阶圈
3-regular graph（⽴⽅图）（彼得森定理）每个⽆桥⽴⽅图含有⼀个完美匹配
4.2 正则图的1-因⼦分解
Definition：
图G的1-正则⽣成⼦图称为1-因⼦图（1-因⼦图的边为图G的完美匹配）
图G的边集合可以表⽰为多个1-因⼦图的划分，则G称为1-因⼦分解图
由定义可知，每个1-因⼦分解图必定是⼀个偶数阶的r-正则图
注：反之不成⽴，例如彼得森图（10阶3-正则图）不是1-因⼦分解图
Theorem：偶数阶完全图是1-因⼦分解图；
猜想：若G是n阶r-正则图，且r>=n/2，则G是1-因⼦分解图。可分解为r个1-因⼦图
4.3 正则图的2-因⼦分解（圈分解）
Theorem：
（彼得森给出证明）图G是2-因⼦分解图\Leftrightarrow G是r-正则，r为偶数；圆锥曲线
完全图的分解定理（2012年证明，之前为阿尔斯波猜想）
（布莱恩特-霍斯利-彼得森定理）
1，n为奇数 (n>=3)，m1+m2+…+mt = n(n-1)/2, Kn可以分解为Cm1, Cm2, … , Cmt；
2，n为偶数 (n>=4)，m1+m2+…+mt = n(n-2)/2, Kn-M可以分解为Cm1, Cm2, … , Cmt ，其中M是Kn中的⼀个完美匹配；
推论：n为奇数，且m可以整除n(n-1)/2，那么Kn为Cm-可分解图；
再推论：n为奇数，Kn是哈密尔顿因⼦分解图（每个圈是哈密尔顿圈）
应⽤：
斯坦纳三元系（Steiner triple systems）问题
n个元素，每3个元素为⼀组（称为三元组），每⼀对元素恰好落在⼀个三元组中，这个分组称为斯坦纳三元系
等价于将Kn分解为多个C3
5 图的画法（可平⾯图，交叉点数）
Definition：如果图G能在平⾯上画出来，且任何两条边不相交，则称G为可平⾯图（planar graph），将可平⾯图在平⾯上画出得到的图为平⾯嵌⼊图（planar embedding）或平⾯图；
Three Houses and Three Utilities Problem等价为K3,3 是不是可平⾯图
最⼤平⾯图的区域都是三⾓形
欧拉多⾯体公式：V-E+F=2
多⾯体可以投影到平⾯上形成多⾯体的平⾯图
欧拉恒等式：G是连通的平⾯嵌⼊图，有n个顶点、m条边、r个区域，则n-m+r=2
网页登陆密码破解
Theorem：平⾯图G，则m<=3n-6，其中n为阶数，m为边数
推论：每个平⾯图都包含⼀个不超过5度的顶点；
（以下两个定理等价）
库拉托夫斯基定理：图G是可平⾯图\Leftrightarrow G不包含K5和K3,3的剖分⼦图作为其⼦图
注：在图G的边上插⼊任意个（可以是0个）2度的顶点得到的图称为G的剖分⼦图
⽡格纳定理：图G是可平⾯图\Leftrightarrow K5和K3,3都不是G的缩图
注：将图G中的某条边收缩为⼀个顶点，并删除重叠的顶点和边，形成的图为缩图（剖分图，则H是G的缩图）
缩图定理：对于任意⼀个含有⽆限个图的图集合，必定有⼀个图是另⼀个图的缩图
Definition：把图G画在平⾯上，产⽣的最少交叉点数⽬称为图G的交叉数cr(G) （crossing number）
Definition：把图G⽤直线画在平⾯上，产⽣的最少交叉点数⽬称为图G的直线段交叉数cr_(G) （rectilinear crossing number）Theorem：cr(G) >= m-3n+6
cr(Kn) <= ¼ floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2), 其中，当n<=12，上式中的等号成⽴
（法⾥定理）可平⾯图可以⽤直线画法⽆交叉点，即cr_(G) = 0
6 图的着⾊（顶点着⾊，边着⾊）
四⾊定理：每个可平⾯图的顶点能够以四种或更少的颜⾊被着⾊，且每两个相邻顶点的颜⾊不同
Processing math: 0%
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议