文章目录

图论学习资料

图论五百题

看到了有大神刷了五百题的图论, 感慨万千, 路漫漫其修远兮, 吾将上下而求索
图论五百题
以此为志

超级好的博客ACdreamer

图论基础知识

2017/8/14
图论

1.  什么是图, 一种高级数据结构, 三元组组成 <V,E,ψ>,V,点的集合, E ,边的集合, ψ是从边集合E到结点无序偶(有序偶)集合上的函数
2. 也可简记为G = <V,E> 其中V是非空点集合,E是连接结点的边集,
3. 无向图,  每一条边都是无向边的图.
4. 有向图 , 每一条边都是有向边的图. 还有混合图, 就是既有有向边又有无向边的图
5. 邻接点 在一个图中, 若两个结点由一条或者多条边相连
6. 在一个图中不与其它边相连的点叫做孤立结点,仅由孤立节点组成的图称为零图, 仅由一个孤立节点组成的图称为平凡图
7. 关联与同一结点的边称为邻接边, 关联与同一结点的一条边称为自回路或环,环的方向没有意义    
8. 与一个点相连的边数称为度数,每一个环在其对应结点上的度数增加2
9. 度数为奇数的的结点必为偶数个
10. 有向图, 出度与入度 定理, 在任何有向图中出度与入度之和必相等
11. 含有平行边的任何一个图称为多重图
12. 把不含有环和平行边的图称为简单图,若任何一对结点之间都有边相连, 则称为完全图, 有n个结点的无向完全图记为Kn
13. 生成子图 : 包含G中所有结点,且该字图为G的生成子图
14. 路和通路 给定图 G = <V,E>,设v0,v1,...vn€V,e1,e2,...en, €E,其中ei是关联于vi-1,vi的边,交替序列v0e1v1e2v2 e3 e3v3..envn称为联结v0到vn的路
15. v0到vn分别称作路的起点和终点,边的数目n称作路的长度,v0 = vn时,这条路称为回路
16. 若一条路中e1,e2,e3,...en都不相同,称作迹.
17. 若一条路中所有的结点v0,v1,v2...vn均不相同,称为通路
18. 闭的通路即除v0 = vn外,其余结点均不相同的路称为圈
19. 欧拉图 - 给定无孤立节点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路,若存在一条回路, 经过图中每边一次且仅一次,成回路为欧拉回路,具有欧拉回路的图称为欧拉图
20. 定理 无向图具有一条欧拉路, 当且仅当G是连通的,且有零个或奇数度结点
21. 推论 无向图G具有一条欧拉回路, 当且仅当G是连通的,并且所有结点度数全为偶数
22. 定义给定有向图G,通过图中每边一次且仅一次的一条单向路(回路),称作单向欧拉路(回路)
23. 定理 有向图G具有一条单向欧拉回路,当且仅当是连通的, 且每个结点的出度等于入度.一个有向图G具有一条单向欧拉路,当且仅当它是连通的,而且除了两个节点为出度等于入度,但这两个结点中,一个的入度比出度大1,另一个出度比入度大1
24. 汉密尔顿路,周游世界问题
25. 定义 给定图G,若存在一条路经过图中每一个结点恰好一次,这条路称作汉密尔顿路. 若存在一条回路,经过图中每一个结点恰好一次, 称为汉密尔顿回路
26. 定理 若图G = <V,E> 具有汉密尔顿回路,则对于结点集V的每个非空子集S均有W(G-S) <= |S|成立,.其中W(G-S)是G-S中的连通分支数目,常用来证明某些图是非汉密尔顿图
27. 充分条件 设G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路
28. 例 考虑在七天之内安排气门课程的考试,使得同一位教师所任的两门课考试不排在接连的两天中,证明如果没有教不同的老师担任,则在这两个结点之间有一条边,因为每一个老师所任课程不超过4,则每个节点的度数至少是3,任意两个结点度数之和至少是6,故G总是存在一条汉密尔顿路,它对应于一个七门考试科目的一个适当的安排
29. 定理 设G是具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路
30. 平面图, 设 G = <V,E> 是一个无向图,如果能够把G的所有结点和边画在平面上,且使得任何两条边除了断点之外没有其它的交点,则成G是一个平面图    
31. 一个有限平面图,面的次数之和是边数的两倍,
32. 欧拉定理 凸多面体, v个顶点,e条边,r块面,则v-e+r = 2,
33. 同样对于一个联通的平面图G,共有v个结点,e条边,r个面,则欧拉公式 v-e+r = 2成立
34. 定理 设G是一个由V个结点,e条边的连通简***面图,若v>=3,则e<=3v-6 用该定理可判断某些图是否为非平面图  
35. 对偶图    
36. 树和生成树
37. 定义 : 一个连通且无回路的的无向图称为树.书中度数为一的结点成为树叶,度数大于一的点称为分枝点或者内点. 一个无回路的无向图称为森林,他的每个连通分录称为森林
38. 定理 任何一棵树中至少有两片树叶
39. 若图G的生成子图是一个树,则成该树是G的一个生成树
40. 设图G中有一棵生成树T,则T中的边叫做树枝,图G中不在树T中的称为弦, 弦的集合称为T的补
41. 定理 连通图至少有一棵生成树
42. 一条回路和任何一棵生成树的补至少有一条公共边
43. 一个割边集和任何一棵生成树至少有一条公共边    
44. 在图G的所有生成树中,树权最小的那颗生成树称为最小生成树
45. 最小生成树算法Kruskal  
46. 如果一个有向图在不考虑边的方向的情况下是一棵树, 那么,称这个有向图为有向树
47. 根树及其应用
48. 一棵有向树, 如果恰有一个结点的入度为0,其余所有结点的入度都为一,入度为0的结点称为根,出度为0的结点称为叶,出度不为零的结点称为分支点或者内点
49. 层次,任意结点的层次就是从根到结点的单向通路长度
50. 定义 在根树中, 若每一个结点的出度正好小于或等于m,称这棵树为m叉树. 如果每一个结点的出度恰好等于m或零, 则称这棵树为完全m叉树, 若所有树叶层次相同,则称为正则m叉树
51. 设有完全m叉树, 其树叶数为t,分枝点数为i,(m-1)i = t-1
52. 应用 : 假设有一台计算机, 它有一条加法指令,可计算三个数的和,如果要计算9个数的和,至少要执行几次加法指令 (3-1) i = 9-1
53. 定义: 在根树中, 一个结点的通路长度,就是从树根到此节点的通路中的边数. 我们把分枝点的通路长度称为内部通路长度, 树叶的通路长度称为外部通路长度
54. 定理 : 若完全二叉树有n个分枝点,且内部通路长度的总和为I, 外部通路长度的总和为E,则 E = I+2n
55. 最优二叉树问题, 霍夫曼树, 前缀码问题,