准备ACM比赛的时候，懵逼的发现自己竟然不知道怎么求解图论的最短路径问题，至此开始，收集一系列有关图论的知识体系以及大部分题目，力争这段时间完成，在说图论之前，我们首先要知道图论的定义包含哪些。
1 | 图由定点(vertex)的集V和边(edge)的集E组成。 |
紧接着就是图论有关算法涉及到的大多数定理了。稍微从各大网站还有大佬们的博客上爬虫下来的相关信息，了解到了主要有关图论的acm知识点，我以接下来的55点介绍，不一定能完全覆盖，但是大多数常考理论也都在里面涉及，相关算法方面，我也会在随后的一段时间里扩充。
- 什么是图, 一种高级数据结构, 三元组组成 <V,E,ψ>,V,点的集合, E ,边的集合, ψ是从边集合E到结点无序偶(有序偶)集合上的函数
- 也可简记为G = <V,E其中V是非空点集合,E是连接结点的边集,
- 无向图, 每一条边都是无向边的图.
- 有向图 , 每一条边都是有向边的图. 还有混合图, 就是既有有向边又有无向边的图
- 邻接点 在一个图中, 若两个结点由一条或者多条边相连
- 在一个图中不与其它边相连的点叫做孤立结点,仅由孤立节点组成的图称为零图, 仅由一个孤立节点组成的图称为平凡图
- 关联与同一结点的边称为邻接边, 关联与同一结点的一条边称为自回路或环,环的方向没有意义
- 与一个点相连的边数称为度数,每一个环在其对应结点上的度数增加2
- 度数为奇数的的结点必为偶数个
- 有向图, 出度与入度 定理, 在任何有向图中出度与入度之和必相等
- 含有平行边的任何一个图称为多重图
- 把不含有环和平行边的图称为简单图,若任何一对结点之间都有边相连, 则称为完全图, 有n个结点的无向完全图记为Kn
- 生成子图 : 包含G中所有结点,且该字图为G的生成子图
- 路和通路 给定图 G = <V,E>,设v0,v1,…vn€V,e1,e2,…en, €E,其中ei是关联于vi-1,vi的边,交替序列v0e1v1e2v2 e3 e3v3..envn称为联结v0到vn的路
- v0到vn分别称作路的起点和终点,边的数目n称作路的长度,v0 = vn时,这条路称为回路
- 若一条路中e1,e2,e3,…en都不相同,称作迹.
- 若一条路中所有的结点v0,v1,v2…vn均不相同,称为通路
- 闭的通路即除v0 = vn外,其余结点均不相同的路称为圈
- 欧拉图 - 给定无孤立节点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路,若存在一条回路, 经过图中每边一次且仅一次,成回路为欧拉回路,具有欧拉回路的图称为欧拉图
- 定理 无向图具有一条欧拉路, 当且仅当G是连通的,且有零个或奇数度结点
- 推论 无向图G具有一条欧拉回路, 当且仅当G是连通的,并且所有结点度数全为偶数
- 定义给定有向图G,通过图中每边一次且仅一次的一条单向路(回路),称作单向欧拉路(回路)
- 定理 有向图G具有一条单向欧拉回路,当且仅当是连通的, 且每个结点的出度等于入度.一个有向图G具有一条单向欧拉路,当且仅当它是连通的,而且除了两个节点为出度等于入度,但这两个结点中,一个的入度比出度大1,另一个出度比入度大1
- 汉密尔顿路,周游世界问题
- 定义 给定图G,若存在一条路经过图中每一个结点恰好一次,这条路称作汉密尔顿路. 若存在一条回路,经过图中每一个结点恰好一次, 称为汉密尔顿回路
- 定理 若图G = <V,E具有汉密尔顿回路,则对于结点集V的每个非空子集S均有W(G-S) <= |S|成立,.其中W(G-S)是G-S中的连通分支数目,常用来证明某些图是非汉密尔顿图
- 充分条件 设G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路
- 例 考虑在七天之内安排气门课程的考试,使得同一位教师所任的两门课考试不排在接连的两天中,证明如果没有教不同的老师担任,则在这两个结点之间有一条边,因为每一个老师所任课程不超过4,则每个节点的度数至少是3,任意两个结点度数之和至少是6,故G总是存在一条汉密尔顿路,它对应于一个七门考试科目的一个适当的安排
- 定理 设G是具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路
- 平面图, 设 G = <V,E是一个无向图,如果能够把G的所有结点和边画在平面上,且使得任何两条边除了断点之外没有其它的交点,则成G是一个平面图
- 一个有限平面图,面的次数之和是边数的两倍,
- 欧拉定理 凸多面体, v个顶点,e条边,r块面,则v-e+r = 2,
- 同样对于一个联通的平面图G,共有v个结点,e条边,r个面,则欧拉公式 v-e+r = 2成立
- 定理 设G是一个由V个结点,e条边的连通简单平面图,若v>=3,则e<=3v-6 用该定理可判断某些图是否为非平面图
- 对偶图
- 树和生成树
- 定义 : 一个连通且无回路的的无向图称为树.书中度数为一的结点成为树叶,度数大于一的点称为分枝点或者内点. 一个无回路的无向图称为森林,他的每个连通分录称为森林
- 定理 任何一棵树中至少有两片树叶
- 若图G的生成子图是一个树,则成该树是G的一个生成树
- 设图G中有一棵生成树T,则T中的边叫做树枝,图G中不在树T中的称为弦, 弦的集合称为T的补
- 定理 连通图至少有一棵生成树
- 一条回路和任何一棵生成树的补至少有一条公共边
- 一个割边集和任何一棵生成树至少有一条公共边
- 在图G的所有生成树中,树权最小的那颗生成树称为最小生成树
- 最小生成树算法Kruskal
- 如果一个有向图在不考虑边的方向的情况下是一棵树, 那么,称这个有向图为有向树
- 根树及其应用
- 一棵有向树, 如果恰有一个结点的入度为0,其余所有结点的入度都为一,入度为0的结点称为根,出度为0的结点称为叶,出度不为零的结点称为分支点或者内点
- 层次,任意结点的层次就是从根到结点的单向通路长度
- 定义 在根树中, 若每一个结点的出度正好小于或等于m,称这棵树为m叉树. 如果每一个结点的出度恰好等于m或零, 则称这棵树为完全m叉树, 若所有树叶层次相同,则称为正则m叉树
- 设有完全m叉树, 其树叶数为t,分枝点数为i,(m-1)i = t-1
- 应用 : 假设有一台计算机, 它有一条加法指令,可计算三个数的和,如果要计算9个数的和,至少要执行几次加法指令 (3-1) i = 9-1
- 定义: 在根树中, 一个结点的通路长度,就是从树根到此节点的通路中的边数. 我们把分枝点的通路长度称为内部通路长度, 树叶的通路长度称为外部通路长度
- 定理 : 若完全二叉树有n个分枝点,且内部通路长度的总和为I, 外部通路长度的总和为E,则 E = I+2n
- 最优二叉树问题, 霍夫曼树, 前缀码问题。
附赠：来自csdn某位大佬贡献的各大OJ上有关的图论500题，已经按类按OJ型号题目位置划分完毕，可以供大家学习使用。
1 | =============================以下是最小生成树+并查集====================================== |