图论学习笔记（一）
一、基本概念
1、简单图：无环且无多重边 伪图：有环或有多重边
2、特殊的简单图：Kn，Qn，Wn，Cn（完全图，n立方图，轮图，圈图）
3、（?）
生成子图：生成子图的顶点与原图完全一样，但是边可以取原图中边的任意子集
诱导子图（导出子图）：诱导子图中顶点可以取原图的任意非空子集，但是这些顶点之间对应的连线在G和G‘中必须相同
4、握手定理：（主要是度的奇偶性讨论，在欧拉图部分会详细探讨用法，此处略过）
二、二分图（二部图）
1、定义：二部图：顶点集划分为2个不相交类别，边的端点在不同类别中 完全二部图：来自不同类别的两个顶点均有边
2、判定：二种颜色对顶点着色，相邻顶点赋以不同颜色（等价性）
3、（?）二部图的匹配
完全匹配的充分必要条件 —>（霍尔婚姻定理，该定理提供了一组存在完全匹配的充分必要条件）
带有二部划分(V1,V2)的二分图G(V,E)中有一个从V1到V2的完全匹配当且仅当对于V1的所有子集A，有|N(A)|>=A
证明：数学归纳法，设<=k均成立，对k+1进行证明
(笔记较抽象，不具有太高的参考意义)
霍尔定理的推论：设二部图G是一个k-正则的(k >=1), 则G有完美匹配
证明略
三、图的表示
1、关联矩阵：只适用于无向图，无向图中的简单图和伪图均适用，横向为边，纵向为顶点
2、邻接矩阵：无向图，有向图均可以（无向图中的简单图和伪图均适用，无向图为对称矩阵）
注：图G的邻接矩阵中的元素的次序是无关紧要的，只要进行和行、列和列的交换，则可得到相同的矩阵。
若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（同构的一个判定方法√）
3、（?）邻接矩阵的计算
（a）逆图：把图沿着左上到右下的对角线对称过去
（b）
bij表示结点i和结点j均有边指向的那些结点的个数，若i＝j，则bii表示结点i的出度。
(c)Cij表示同时有边指向结点i和结点j的那些结点的个数；若i＝j，则Cii表示结点i的入度
(d)
若aik×akj＝1，则表示有i→k→j长度为2的有向边；dij表示i和j之间具有长度为2的通路个数。
4 、沃舍尔算法回顾
纸上算法：
（从1到n一共n行n列）
第k行为1的元素所在列画纵向直线
第k行为1元素所在行画横向直线
直线相交位置如果为0，则改为1
5、（?）图的同构
图形不变量：顶点数，边数，度序列，可以查看特定度的子图是否同构
法一：如果以上的图形不变量都相同，可以考虑找两个图之间的对应函数。如果能够找到，则两个图同构。
法二：写出两个图的对应邻接矩阵，两个矩阵如果可以通过行和行，列和列交换重合，则两个图同构。