刘汝佳书上图论这章也看的差不多了，做题时发现自己在图论的知识与思维上还差很多，所以去图书馆借了两本图论的书翻了看看，一些笔记整理于此。
一.重要思想：
1.补图：
- -
G是以V（G）为点集的一个图，但是两个点在G中连接当且仅当他们在G中不连接。
eg
命题：在任何一个有6个人的组里，存在3个人相互认识，或存在3个人相互不认识。
证明：设A是其中的某一人，则另外5人中一定存在3个人都认识他，否则这个现象在补图中成立而在这三个人中，如果互相都不认识，则命题成立，否则存在某两人互相认识，则这两人和A一起，构成了互相认识的三人。如此，命题成立。
画图问题：画出全部具有5个顶点，3条或7条边的简单图。
因为一个5个点的完全图共有5*4/2=10条边，所以一个3条边的图的补图就是7条边的图，如此只需画出一种即可生成另一种
命题：对一个任意的简单图，此图或其补图是连通的。
证明：假设给定的图是不连通的，对这个图中的任意两点a、b，如果这两点在原图中不属于同一个块，则在补图中他们就是连通的如果这两点在原图中属于同一个块，则在原图中存在另一个块中点c，这个ac，bc在补图中是连通的，所以a、b在补图中连通，问题得证
2.最长路方法
设L是图G的最长路之一，它的长是m，它的端点之一是a，我们考察G中关联于a的那些边，其中任意边的另一端点必属于L，否则，把这另外的边添加到L上去，就会得到一条更长路。
eg
命题：一个连通图，每个顶点度数是2，则该图是个环。
证明：假设这个图有一条最长路L，一个端点为a，因为a的度数是2，所以a还有一条C边不在L中，由最长路原则可知，这条边的另一端点也必须属于L，而L中只剩一个点的度数是1，即另一端点b，其余点度数都是2，所以C只能连到b，这样最长路L首尾端点必然相连，即构成了一个环
命题：一个无圈有向图至少有一个顶点的出度为0。
证明：假设该图有一条最长路L，一个端点为a，若与a相连的边至少有两条，假设不在L中的那条边为C，根据最长路原则，C的另一端点只能在L中，而题目中说明了该图是无圈图，所以这条与a相连的边C不存在，这样可以看出与a相连的边只能有一条，所以a的出度为0。
3.方向对偶原则
逆有向图概念：简单来说，就是把一个有向图所有边反向得到的图。
eg
命题：一个无圈有向图至少有一个顶点的入度为0.
证明：通过上一个命题中证明的那张图的逆有向图，可以轻松看出这个命题也是成立的，（其实是等价的）。
4.矩阵的引入
一个图由它的邻接性或关联性完全决定。这种信息可以用矩阵很方便的表达。
eg
邻接矩阵
定理：令A为G的邻接矩阵，则An（A的n次方）的元素a[i][j]的值是由Vi到Vj的长度等于n的道路的数目。
推论1：A2中a[i][i]是Vi的度。A3的a[i][i]是含Vi的三角形数目的2倍。
推论2：若G是连通的，对于i!=j,Vi与Vj之间的距离是使An的a[i][j]不等于0的最小整数n。
5.图的度数是边数的两倍
因为图就是由点和边组成的，而度作为描述这两个量的数量关系上的概念，（因为通常知道点的度）这个相等关系就实在太重要了，虽然很简单。
eg
命题：若一个图是连通的，且每个点的度至少是2，则图G中一定含有一个圈。
证明：假设图中顶点个数是n，则图总的度数>=2*n，所以边数>=n，因为一个图的生成树只有n-1条边，所以这个多出来的一条边一定会形成一个环，命题得证
二.概念重述:
1.割点：v是图G的一个割点。则存在一个将点集V-{v}分成子集U和W的划分，使得对任何两点u<-U,和w<-W，点v在每一条u-w的道路上。
2.桥：x是G的一座桥。x不在G的任何一个圈中。
3.块：g是图的一个块。g的任何两个点在一个公共的圈上。对g的每三个不同的点，存在一条道路联结这两个点，并含（不含）有第三个点。（LA 3523）
4.欧拉图：
1). G是欧拉的 <=> G的每一个块是欧拉的。
2). 无向图G的每个点的度数是偶数。
3). 有向图G的入度等于出度。
4). 图的边集能划分为圈。
5.独立集与覆盖：
点覆盖：覆盖一个图所有“边”的一个“点”集。
边覆盖：覆盖一个图所有“点”的一个“边”集。
最小点覆盖集：所有点覆盖中元素数目最少的那个集合，记其元素数目为Df。
最小边覆盖集：所有边覆盖中元素数目最少的那个集合，记其元素数目为Bf。
点独立集：是一个图的点集，其中没有任何两个点在原图中是邻接的。
边独立集：是一个图的边集，其中没有任何两条边在原图中是邻接的。
最大点独立集：所有点独立集中元素数目最多的那个集合，记其元素数目为Dd。
最大边独立集：所有边独立集中元素数目最多的那个集合，记其元素数目为Bd。
重要定理 对任何一个连通图G
Df + Dd = P = Bf + Bd （P是G的顶点数）
重要拓展
如果G是二分图，Bd = Df 。
而最大边独立集Bd 就是 最大匹配数。
三.一些定理
1.明格尔定理：分离两个不相邻的点s、t的点最少数目等于点不相交的s-t路径的最多数目。
明格尔定理变形：对于一个图中的任何两个点，联结它们的边不相交的路径的最多数目等于分离它们的边的最少数目。
（点不相交，即指一般我们熟所悉的不相交；边不相交，即路径没有边重合。）
最大流最小割定理：在任何一个网络中，若有一条从s到t的路径，则从s到t的最大流等于最小截量。
要证明这个定理，可以把由u到v的容量为n的有向边换为n条不指名容量的有向边。这样利用明格尔定理的变形即可证明这个定理了。
2.一个图是可双色的当且仅当它没有奇圈。（作为二分图判定算法的依据）
3.可以给一个任意的无桥的无向连通图的边定向，使它成为一个强连通图。（uva 10972）
一个有向图D是强连通的，当且仅当D中存在一条回路，它至少经过每个顶点一次。（la 4287）
一个无向图G是边双连通的，当且仅当G中存在一条回路，它至少经过每个顶点一次。（uva 10972）
4.一个无向图，每个顶点的度数是偶数，则一定能找到图的一些回路，使每条边恰好属于这些回路之一。
一个有向图，每个点的入度与出度相等，则一定能找到图的一些回路，使每条边恰好属于这些回路之一。