导图社区 图论
对研究生图论的简单知识点总结梳理,图论包括平面图,行遍性问题,树,图的连通性,匹配的基本定理,路径算法。
编辑于2021-12-10 14:45:10图论
路径算法
floyd
直接在图的带权邻接矩阵中插入顶点构造出图的距离矩阵,同时引入后继点矩阵记录两点最短路径
dj
标号作业法,每次迭代产生永久标号,生长一颗最短路树,在这颗树上每个顶点与根结点之间皆为最短路径。权为非负
关于路径算法的总结
匹配
匹配基本定理
贝尔定理
最大匹配当且仅当不含m可增长路径
二部图匹配存在性定理:hall定理
x中,对任意点集的领域数大于点集数,则存在渗透x的匹配
点覆盖与哥尼定理
最小点覆盖与最大匹配数相等
托特定理
0(g-s)<=|s|
彼德森定理:没有割边的3正则图存在理想匹配
匹配概念
m中的两条边没有共同顶点,则称m是g的一个匹配
理想匹配
最大匹配m是g包含边数最多的匹配。 理想匹配是最大匹配渗透了所有点
m交错路
m可增长路径:交错路起点与终点是非渗透点
渗透点
匹配m中的某条边的顶点
二部图最大匹配
最优匹配算法
匈牙利算法
图的连通性
连通度的概念
点断集,点连通度概念
边断集或边割集,边连通度
连通度性质
惠特尼定理,点连通度小于边连通度小于最小度数
敏格儿定理 最少点数是内不相交路的最大数目 最少边数等于边不重的路最大数目
敏格儿定理推论:
图的关键性部位
割边
割边不在任何圈中
割点
存在不同的两点路径都会经过割点
块图,没有割点的连通图
割点属于两个不同的块
块割点树
割集
图的秩,点的关联集
割集与生成树的关系
哈拉里图
子主题
树
路与连通
在n阶阶连通图中至少有n-1条边,用归纳假设法可得
连通性性质.:若图g不连通则其补图连通
一个图是二部图当且仅当它不含奇圈
树的概念
无圈图
每棵非平凡树至少有两片树叶
树的边数等于点数减一
树的顶点上增加一边会得到唯一圈
生成树
每个连通图至少包含一个连通树
凯莱生成树计数公式
关联矩阵计数法
矩阵树定理:写拉氏矩阵,一行一列对应的行列式即生成树棵树
n阶完备图的树有
最小生成树
prim算法
克鲁斯克尔算法
避圈式扩张
行遍性问题
欧拉图
求欧拉巡回:fleury算法
避割边行走
hierholzer算法
产生圈,插入旧圈
哈米尔顿图
定理1必要条件:w(g-s)<=|s|
充分条件
充分条件
邮递员问题
最小集对法
流动推销员问题
经过每顶点至少一次的权最小闭通路为最佳推销员回路
满足三角不等式最佳h图也是最佳推销员回路
tsp问题
在完备加权图求最佳h圈
平面图
平面图概念
图可画在一个平面上使得除顶点外边不交叉,称称g为可嵌入平面
面 面的次数deg(f)
欧拉公式
连通平面图点数减边数加面数等于2
面次数之和为边数的两倍