1、一个图是一个有序对
2、无环无重边的图称为简单图；
3、设有两个图G1=(V1,E1)和G2=(V2,E2)，若在其顶点集合间存在双射，使得边之间存在如下关系：设u1u2,v1v2，u1,v1∈V1，u2,v2∈V2；u1v1∈E1当且仅当u2v2∈E2，且u1v1与u2v2的重数相同。称G1与G2同构，记为G1≌G2；
4、图的度序列：一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列
注：(1)常用δ表示最小度，▲表示最大度；(2)握手定理：图G的度和为边数的2倍——sum(d)=2m；(3)判定条件：非负整数组(d1,d2,….,dn)是图的度序列的充分必要条件是：∑di为偶数。
5、图的图序列：一个非负数组如果是某简单图的度序列，则称其为可图序列；
6、自补图——性质：若n阶图G是自补图，则有n=(0,1)mod(4)
7、图的基本运算：联图G1VG2；积图G1XG2
注：对于积图，点数为n1+n2，边数为n1m2+n2m1对于联图，点数为n1n2，边数为m1+m2+n1n2
8、偶图——偶图的判定定理：一个图是偶图当且仅当它不包含奇圈
9、图的代数表示——其中Ak=(a)ijk表示顶点i到顶点j长度为k的途径数目
1、完全图n阶Kn：m(Kn)=n(n-1)/2
2、一个图的度数为奇数的顶点数为偶数
3、正则图的阶数和度数不同时为奇数
第二章-数
1、树是连通的无圈图;无圈图即是森林
注：若G是具有n点m边的树，则下列命题等价
(1)G是树
(2)G无环且任意两个不同点之间存在唯一的路
(3)G连通，删去任意一条边便不连通
(4)G连通或无圈，且m=n-1
(5)G无圈，添加任何一条边可得到唯一的圈
2、最小生成树——图G的一个生成子图T若是树，则其为G的一颗生成树
注：最小生成树求法：Kruskal算法、破圈法、Prim算法
3、根树——一颗非平凡有向树，恰有一个顶点入度为0，其余所有顶点入度为1，出度为0为树叶，树根和内殿统称为分支点
4、m元完全树——对于根树T每个分支点至多m个儿子，成为m元树，若每个分支点恰有m个儿子，则称为完全m元树
注：对于完全m元树T，由分支点i，树叶t则(m-1)i=t-1
1、树和森林都是简单图
2、树和森林都是偶图
3、每颗非平凡树至少含有两片树叶
证明：树中去最长路V1V2...Vk,则V1和Vk在最长路中只能有一个邻接点，否则要么存在圈，要么不是最长路，故得证
4、树是含有边数最少的连通图，是最小连通图——连通图的边数至少为n-1
证明：分情况讨论：(1)若G无一度顶点，则显然成立，根据握手定理(2)若G有一度顶点，采用归纳法，n=1成立一次类推
5、树是含有边数最多的无圈图
6、假定(n,m)是森林G，则m=n-k
7、若G是树，且最大度大于等于k，则G至少有k片叶子
证明:若G至多有k-1片叶子，则由握手定理k+k-1+2(n-k)=2n-1>2n-2，不是树了，故得证
8、每颗连通图至少包含一个生成树
第三章图的连通度
1、途径——若边不重复则为迹——若既边不重复又点不重复则为路
2、最短路：连接uv的长度最短的路的长度，也称为uv的距离
3、连通图：图G的任意两点是连通的
4、连通分支：图G的连通分支的个数称为分支数，记为ω(G)
5、点连通度：对n阶非平凡连通图G，若G存在顶点割，则称G的最小顶点割的点数为G的连通度，点连通度符号为k(G)
6、边连通度：对于连通图G，边割集的最小边割数称为最小边割，记为λ(G)
1、若图G中不同点uv存在途径，则uv存在路，若过点u存在闭迹，则过点u存在圈
2、若过点u存在闭途径，则过点u不一定存在圈（途径的边可重复）
3、在n(n≥2)阶连通图中，至少有n-1条边(数学归纳法)，若边大于n-1，则至少有个圈
4、若一个图G的最小度大于等于2则图G必然有圈
5、若G不连通，则图补图一定是连通图
6、k(Kn)=n-1,k(Cn)=2；λ(Kn)=n-1,λ(Cn)=2
7、非平凡连通图均是1连通的；图G是2连通的当且仅当G连通、无割点且至少有3割点(K2连通度为1)
8、非连通图和平凡图的边连通度为0
9、对任意的图G，有κ(G)≤λ(G)≤δ(G)
10、设G为n点m边的连通图则
(1)若δ(G)≥n/2，则G必连通(反证法)，且λ(G)=δ(G)(2)对正整数k 11、敏格尔定理 设x与y是图G中的两个不相邻点，则G中分离点x与y的最小点数等于独立的(x,y)路的最大数目设x与y是图G中的两个不相邻点，则G中分离点x与y的最小边数等于G中边不重的(x,y)路的最大数目。 第四章欧拉图和哈密尔顿图、 1、欧拉图：对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图 2、欧拉环游：欧拉闭迹又称为欧拉环游，或欧拉回路 3、欧拉迹：对于连通图G，如果G中存在经过每条边的迹，则称该迹为G的一条欧拉迹 4、哈密尔顿图：如果经过图G的每个顶点恰好一次后能够回到出发点，即存在H圈的图称为哈密尔顿图，简称H图 5、哈密尔顿圈：经过图中每个点仅一次的圈是哈密尔顿圈 6、哈密尔顿路：图G的经过每个顶点的路称为哈密尔顿路 7、中国邮递员问题：图论模型为在一个连通的具有非负权的赋权图G中找一条包含每条边(允许重复)且边权之和最小的闭途径，称之为最优环游。 1、欧拉图E图判定条件： (1)G是欧拉图(2)G的顶点度数为偶数(3)G的边集合能划分为圈(4)G存在欧拉迹当且仅当G中只有两个顶点度数为奇数 2、哈密尔顿图H图 性质定理（必要条件）：若G是H图，则对任意非空子集S，有w(G-S)≤|S| 判定条件(1)(充分条件)对于δ(G)≥n/2,则G是H图(2)(充分条件)对任意u，v有d(u)+d(v)≥n，则G是H图(3)(充分必要条件)图G是H图当且仅当他的闭包是H图(4)(充分条件、度序列判定法)设简单图G的度序列是(d1,d2,…,dn)，其中d1≤d2≤…≤dn，并且n≥3。若对任意的m 第5章匹配 1、如果M是图G的边子集(不含环)，且M中的任意两条边没有共同顶点，则称M是G的一个匹配或边独立集 注：匹配、饱和点与非饱和点：设M是图G的边子集，若任意的e∈M，e都不是环，且属于M的边互不相邻，则称M为G的一个匹配。设M为G的一个匹配，对v∈V(G)，若v是M中某边的一个端点，则称v为M饱和点，否则称为M非饱和点 2、最大匹配：如果M是图G的包含边数最多的匹配，称M是G的一个最大匹配 3、完美匹配：若最大匹配饱和了G的所有顶点，称它为G的一个完美匹配 注：完美匹配必是最大匹配，而最大匹配不一定是完美匹配;最大匹配必存在，完美匹配不一定存在;G存在完美匹配的一个必要条件是G的点数必然为偶数 4、最优匹配：设G=(X,Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G的最优匹配 5、因子分解：所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。k-因子分解：每个因子均为k-因子的因子分解，此时称G本身是k-可因子化的 1、设M是匹配，K是覆盖，若|M|=|K|，则M是最大匹配,且K是最小覆盖 2、设G=(X,Y)是偶图，则G存在饱和X的每个顶点的匹配的充要条件是：|N(S)|≥|S| 3、若G是k(k>0)正则偶图，则G存在完美匹配 4、在偶图中，最大匹配中的边数等于最小覆盖中的点数 5、K2n和kn,n完美匹配个数分别是(2n-1)!!、n！ (1)K2n可一因子分解(2)K2n+1可2因子分解，分解成n个2因子(3)K2n可分解为一个1因子和n-1个2因子之和->即2n-1个1因子(4)具有H圈的三正则图可一因子分解(充分条件)(5)每个没有割边的3正则图是一个1因子和1个2因子之和 第6章平面图 1、平面图：如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图 2、极大平面图：设G是简单可平面图，如果G是Ki(1≤i≤4)，或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图 3、极大外平面图：若一个可平面图G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图 4、平面图的对偶图：给定平面图G，G的对偶图G*如下构造：1)在G的每个面fi内取一个点vi*作为G*的一个顶点；2)对G的一条边e，若e是面fi与fj的公共边，则连接vi*与vj*，且连线穿过边e；若e是面fi中的割边，则以vi为顶点作环，且让它与e相交 注：对偶图性质：（1）平面图的对偶图必连通 （2）|V(G*)|=|φ(G)| （3）|E(G*)|=|E(G)| （4）|φ(G*)|=|V(G)| 1、次数公式：sum(deg(f))=2m 2、欧拉公式：n-m+Φ=2(对于连通平面图)；n-m+Φ=k+1(对于k个连通分支的平面图) 3、平面图的必要条件 (1)对于n≥3，则m≤3n-6=>可推出K5为非可平面图(2)若对每个面f，由deg(f)≥l≥3，则m>l/(l-2)*(n-2)=>可推出K3,3为非可平面图(3)简单可平面图G，δ(G)≤5 4、一个连通平面图G是2连通的当且仅当G的每个面的边界是圈 5、对于极大可平面图G (1)G必连通(2)若G阶数至少为3，则G无割边(3)充分必要条件：G中的各个面次数均为3且为简单图，即每个面的边界均为三角形(4)m=3n-6,φ=2n-4(5)若G是一个阶数至少为4的极大外可平面图，则G中存在两个度数为2且不相邻的点 6、设G是一个具有n(n≥4)个点，m条边的简单连通外平面图。若G不含三角形，则m≤(3n–4)/2 7、每个至少有7个顶点的外可平面图的补图不是外可平面图，且7是这个数目的最小者 8、图G是可平面的当且仅当它不含与K5或K3,3同胚的子图 第7章图的着色 1、边着色：相邻边着不同颜色，其最小边色数可表示为χ’(G) (1)完全二部图：χ’(G)=Δ(2)二部图：χ’(G)=Δ(3)G是简单图，χ’(G)=ΔorΔ+1(4)设G是简单图且Δ(G)>0。若G中只有一个最大度点或恰有两个相邻的最大度点，则χ’(G)=Δ(5)设G是简单图。若点数n=2k+1且边数m>kΔ，(6)则χ’(G)=Δ+1(7)设G是奇数阶Δ正则简单图，若Δ>0，(8)则则χ’(G)=Δ+1 2、点着色：相邻点着不同颜色，其最小边色数可表示为χ(G) (1)对任意图G，χ(G)≤Δ+1(2)若G是连通的单图，且既不是奇数圈也不是完全图，则χ(G)≤Δ(3)对任意图G，χ(G)≤Δ2+1 3、色多项式 (1)递推计数法：Pk(G)=Pk(G-e)-Pk(G·e)(2)理想子图计数法