向上吧贺凯

一 特殊平面图1 极大平面图及其性质极大平面图的两种情况，一种是K1到K4四种特殊情况，即1阶到4阶的完全图是极大可平面图另一种就是一般的情况，任意非邻接顶点间添加一条边后，得到的图均是非可平面图。二、平面图的对偶图...

一 平面图概念可以看成可平面图和平面图是同构的。二 平面图性质平面图的所有面的次数之和等于边数的两倍。

（一）、平面图的概念可平面图定义：平面嵌入可以有很多种（二）、平面图的性质平面图的面外部面有且只有一个树一定是平面图，平面图不一定是树割边一定在某个区域中，而非割边一定是两个区域的交界平面图的总次数是边数的两倍平面图的欧拉公式这种证法关键在于分成各个连通分支来算的时候，外部面算了k次，而实际原图中只有一个外部面这个推论给出了边数的一个上界...

目录（一）匈牙利算法M交错树匈牙利算法-偶图完美匹配算法偶图中找最大匹配（二）、最优匹配算法-库恩算法可行顶点标号相等子图定理及其证明要求掌握例题：（一）匈牙利算法扎根于M非饱和点u,即以u为树根来构造M交错树，u是偶图中X点集中的点M交错树以非饱和点为根节点的树S是M交错树上的属于点集X的点的集合，T是M交错树上的属于点集Y上的...

目录（一）图的一因子分解因子因子分解n因子可n因子分解偶数阶完全图可一因子分解例题定理2 具有H圈三正则图可一因子分解定理3 若三正则图有割边，则它不能一因子分解（二）、图的二因子分解定理4 奇数阶完全图可2因子分解定理5 2n阶完全图可分解为1个一因子和n-1个二因子之并定理6 每个没有割边的3正则图是1个一因子和1个二因子之和定理7 一个...

点覆盖与哥尼定理点覆盖与最小点覆盖现在还没有好的方法来求最小点覆盖，所以还是得靠观察点覆盖的本质就是一个顶点子集，匹配时边子集，只不过匹配要求不能里边的边不能有公共交点最大匹配最小点覆盖定理上边G打错了，最后一句话，而K是最小覆盖，这个定理说明，当匹配中的边数等于点覆盖中的点数，那么此匹配是最大匹配，点覆盖是最小点覆盖。哥尼定理例题：托特定理...

目录基础回顾偶图k-正则偶图图的对称差运算一、图的匹配与贝尔热定理匹配概念最大匹配与完美匹配M交错路与M可扩路贝尔热定理二、偶图的匹配与覆盖偶图匹配存在性判定--Hall定理Hall定理推论（证明要求掌握）例题基础回顾偶图k-正则偶图图的对称差运算一、图的匹配与贝尔热定理匹配概念图的匹配本质上就是一个集...

目录一、超H图与超H迹超H图超可迹图关于H图的一些猜想二、E图与H图的关系线图概念线图性质从线图的角度考虑欧拉图与哈密尔顿图关系（考试不作要求）一、超H图与超H迹超H图彼得森图是3正则图，每个顶点关联的有3条边，假设彼得森图是H图的话，则存在H圈，且每个顶点都有两条边在H圈中，因为H圈要包括每一个顶点，但只能有2条边在H圈中，还有1条边不在圈中，因为...

一、非哈密尔顿图特征度极大非H图Cm,n图定义Cm,n图可以分为三部分，如上图所示，左边部分是m个顶点的单点集与m阶完全图联运算，右边部分是n-2m阶完全图与m阶完全图联运算，中间是m阶完全图分别与两边作联运算，所以左边部分的度都是m，右边部分的度都是n-2m-1+m=n-m-1,中间部分度为m-1+m+n-2m=n-1如果去掉中间部分，即去掉了m个点，则左边产生了m个连通...

一、欧拉图欧拉图与欧拉回路对于只存在欧拉迹，不存在欧拉闭迹的图成为半欧拉图，欧拉图与半欧拉图都是连通图欧拉图性质对于半欧拉图，恰好有两个奇点这种是常规操作，奇度点在图中一定有偶数个，只要我们将奇度点两两配对，一定可以将一个图变成欧拉图，比如这个例题，有8个奇度点，所以需要用4笔画完因为n阶完全图每个顶点度数为n-1，n方体的度数就是n，完全二...

目录一、割边、割点和块割边及其性质割点及其性质块一、割边、割点和块割边及其性质割边定义：w（G-e）> w(G)是说删去边e后连通分支数增加，w代表一个图的连通分支数，注意删边不删点，所以对于树来说，每一条边都是割边定理1给出了割边的充要条件，即不在圈中割点及其性质割点定义G[E]为边导出子图这里之所以（2）（3）都指出...

预备知识： 最小连接问题： （一）、克鲁斯克尔算法 例题：克鲁斯克尔求最小生成树 定理：由克鲁斯克尔算法得到的生成树一定是最小生成树。（二）、管梅谷的破圈法 ...

（一）、生成树的概念与性质1.生成树的概念定义1：图G的一个生成子图T如果是树，称它为G的一棵生成树。若T为森林，称它为G的一个生成森林。 首先回忆一下生成子图的概念，如果一个子图包含原图的所有顶点，则称该子图为原图的生成子图。G中生成树的边称为树枝，G中非生成树的边称为弦。2.生成树的性质定理1：每个连通图至少包含一棵生成树。 利用破...

（一）、树的概念与应用1.树的概念不含圈的图称为无圈图，树是连通的无圈图。树的度为1的顶点称为树叶。 定义：称无圈图G为森林。 即无圈图G就是森林，森林可以是不连通的，若森林连通，则该森林为树。即森林可以包含很多树，每个树都是该森林的连通分量。注意：树与森林都是简单图； 两个顶点及以上的树与森林都是偶图； ...

一、邻接谱、邻接代数与图空间（一）图的邻接谱1、图的邻接谱定义 图的邻接矩阵A（G）的特征值及其重数，称为G的邻接谱。 为什么长这样？哪个是特征值哪个是重数？ 邻接谱的第一行是特征值，第二行是特征值对应的重数。 同谱图定义：若两个非同构的n阶图具有相同的谱，则称它们是同谱图。 2、邻接谱的两个性质 s是特征值个数...

（一）相关概念1.边赋权图 2.边赋权图中的最短路 3.算法 解决某类问题的一组有穷规则，称为算法。4.好算法 5.算法分析 主要是对时间复杂度进行分析，分析运算量和问题规模之间的关系。（二）最短路算法1.最短路算法描述 顶点标号法 ...

一、图的代数表示一个图可以用定义描述，图形表示和代数表示，代数表示即用邻接矩阵或关联矩阵表示。（一）图的邻接矩阵1.邻接矩阵定义 2.邻接矩阵性质（1）非负性与对称性 邻接矩阵中的元素都是非负的，且关于主对角线对称。（2）同一图的不同形式的邻接矩阵是相似矩阵 同一图的不同形式或许是指同一...

目录一、子图相关概念1.子图概念2.点导出子图与边导出子图点导出子图边导出子图3.图的生成子图二、图运算1.图的删点、删边运算删点运算删边运算2.图的并运算3.图的交运算4.图的差运算5.图的对称差运算或环和运算6.图的联运算7.图的积图8.图的合成图三、路与连通性1.路与圈的相关概念图中的途径图中的迹图中的路...

一、完全图、偶图与补图二、顶点的度与图的度序列一、完全图 （1）完全图首先是一个简单图，即没有环也没有重边的图。且任意一个顶点都与其它每个顶点有且只有一条边相连接 （2）n个顶点的完全图用Kn表示，称为n阶完全图。 小知识：所以完全图的边数应该是C(2,n)=1/2*n*(n-1)...

一、什么是图？ 定义：一个图是一个序偶<V,E>，记为G=（V,E），其中 （1）V是一个有限的非空集合，称为顶点集合，其元素称为顶点或点，用|V|表示顶点的数目。 （2）E是由V中的点组成的无序对构成的集合称为边集，其中元素称为边，且同一点对在E中可以重复出现多次（如果标上边的重数的话，每一点对只要出现一次就行了）。用|E|表示边数。 图可以用...