一、重要概念
1. 图、简单图、图的同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图
- 图：一个图是一个有序对<V, E>，记为G=(V, E)，其中： 1) V是一个有限的非空集合，称为顶点集合，其元素称为顶点或点。用|V|表示顶点数；2) E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数
注：图G 的顶点集记为V(G)，边集记为E(G)。图G 的顶点数(或阶数)和边数可分别用符号n(G)和m(G)表示
- 简单图：无环无重边的图称为简单图。（除此之外全部都是复合图）
注：点集与边集均为有限集合的图称为有限图。只有一个顶点而无边的图称为平凡图。边集为空的图称为空图
- 图的同构：设有两个图G1=(V1, E1)和G2=(V2, E2)，若在其顶点集合间存在双射，使得边之间存在如下关系：设u1↔u2, v1↔v2， u1, v1∈V1，u2, v2∈V2；u1v1∈E1当且仅当u2v2∈E2，且u1v1与u2v2 的重数相同。称G1与G2同构，记为G1≌G2
- 图的度序列：一个图G的各个点的度d1, d2,…, dn构成的非负整数组(d1, d2,…, dn)称为G的度序列
注：非负整数组(d1, d2,…., dn)是图的度序列的充分必要条件是：∑di 为偶数。度序列的判定问题为重点！
- 图的图序列：一个非负数组如果是某简单图的度序列，称它为可图序列，简称图序列
- 补图：对于一个简单图G=(V, E)，令集合E1={uv|u≠v, u, v∈V}，则图H=(V，E1E)称为G的补图
- 自补图：若简单图G与其补图同构，则称G为自补图
注：自补图的性质
（1）若n阶图G是自补的(即
)，则
- 联图：设G1，G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为G1∨G2
- 积图：设G1=(V1, E1)和G2=(V2, E2)是两个图，对点集V1×V2中的任意两个点u=(u1, u2)与v=(v1, v2)，当(u1=v1和u2 adj v2)或(u2=v2和u1 adj v1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为记为G1×G2
例如：
- 偶图：所谓具有二分类（X, Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个非空子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中
注：偶图的判定定理：一个图是偶图当且当它不包含奇圈
2. 树、森林、生成树、最小生成树、根树、完全m元树
- 树：不含圈的图称为无圈图，树是连通的无圈图
注：1、设G是具有n个点m条边的图，则下列命题等价：
（1）G 是树
（2）G 无环且任意两个不同点之间存在唯一的路
（3）G 连通，删去任一边便不连通
（4）G 连通，且 n = m + 1
（5）G 无圈，且 n = m + 1
（6）G 无圈，添加任何一条边可得唯一的圈
2、几个结论
（1）树和森林都是简单图
（2）树和森林都是偶图
（3）每棵非平凡树至少含有两片树叶
（4）树是含有边数最少的连通图，成为最小连通图
（5）树是含有边数最多的无圈图
（6）假定（n,m）图G是由k棵树组成的森林，则m=n-k
（7）若G是树，且最大度大于等于k，则G至少有k片叶子
- 森林：无圈图G为森林
- 最小生成树：图G的一个生成子图T如果是树，称它为G的一棵生成树；若T为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦
注：最小生成树的求法：Kruskal算法、破圈法、Prim算法
- 根树：一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点
- m元完全树：对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树
注：
3. 途径(闭途径)、迹(闭迹)、路(圈)、最短路、连通图、连通分支、点连通度与边连通度
- 途径（闭途径）:给定图G = (V, E)，w =v0e1v1e2…ekvk是G中点边交替组成的序列，其中vi∈V，ei∈E，若w满足ei的端点为vi-1与vi，则称w为一条从顶点v0到顶点vk的途径（或通道或通路)，简称(v0, vk)途径。顶点v0和vk分别称为w的起点和终点，其他点称为内部点，途径中的边数称为它的长度。起点和终点相同的途径就称为闭途径（环游）
- 迹（闭迹）:边不重复的途径称为迹,起点终点相同的迹为闭迹（回路）
- 路（圈）：点不重复的迹称为路，起点终点相同的路成为圈
- 最短路：连接u、v的长度最短的路的长度，也称u与v的距离，记作d（u，v）
- 连通图：如果图G中任意两个点都是连通的，则G为连通图
- 连通分支：在非连通图G中，每一个极大的连通部分为G的连通分支，G的连通分支的个数，称为G 的分支数，记为ω(G)。
- 点连通度：对n阶非平凡连通图G，若G存在顶点割，则称G的最小顶点割中的点数为G的连通度；否则称n-1为其连通度。G的连通度符号表示为κ(G)，简记为κ；非连通图或平凡图的连通度定义为0。
- 边连通度：设G为连通图，称使G-E ′不连通的G的边子集E ′为G的边割，含有k条边的边割称为k边割。边数最少的边割称为最小边割
注：1、几个结论
（1）若图中两个不同点u与v间存在途径，则u与v间必存在路；若过点u存在闭迹，则过点u必存在圈。
（2）若过点u存在闭途径，则过点u不一定存在圈。
（3）在n(n≥2)阶连通图中，至少有n-1条边；如果边数大于n-1，至少有个圈
（4）若一个图G中的最小度大于等于2，则G中必然有圈
（5）若图G是不连通的，则其补图一定是连通图
（6）设图G为n阶图，若G中任意两个不相邻顶点u与v满足d(u)+d(v)≥n-1，则G是连通图且d(G)≤2
（7）若G是非平凡连通图，则v是G的割点当且仅当{v}是G的1顶点割
（8）完全图没有顶点割，实际上也只有以完全图为生成子图的图没有顶点割
（9）κ(Kn)=n-1；κ(Cn)=2，其中Cn为n圈，n≥3
（10）非平凡连通图均是1连通的；图G是2连通的当且仅当G连通、无割点且至少含有3个点；K2连通、无割点、但连通度为1
（11）非连通图或平凡图的边连通度定义为0
（12）λ(Kn)=n-1；λ(Cn)=2，其中Cn为n圈，n≥2
（13）非平凡连通图均是1边连通的；图G是2边连通的当且仅当G连通、无割边且至少含有两个点
（14）对任意的图G，有κ(G)≤λ(G)≤δ(G)
（15）设G是具有m条边的n阶连通图，则
（16）设G是n阶简单图，若δ(G)大于等于(n/2)向下取整，则G必连通
（17）设G是n阶简单图，对正整数k<n，若
，G是k连通的
（18）设G是n阶简单图，若δ(G)≥（n/2）向下取整，则λ(G)=δ(G)
4. 欧拉图、欧拉环游、欧拉迹、哈密尔顿圈、哈密尔顿图、哈密尔顿路、中国邮递员问题、最优H圈
- 欧拉图：对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图
- 欧拉环游：欧拉闭迹又称为欧拉环游，或欧拉回路
- 欧拉迹：对于连通图G，如果G中存在经过每条边的迹，则称该迹为G的一条欧拉迹
- 哈密尔顿图：如果经过图G的每个顶点恰好一次后能够回到出发点，即存在H圈的图称为哈密尔顿图，简称H图
- 哈密尔顿圈：经过图中每个点仅一次的圈是哈密尔顿圈
- 哈密尔顿路：图G的经过每个顶点的路称为哈密尔顿路
- 中国邮递员问题：图论模型为在一个连通的具有非负权的赋权图G中找一条包含每条边 (允许重复) 且边权之和最小的闭途径，称之为最优环游。
注：
（1） 若图G是一个欧拉图，则找出G的欧拉回路即可。
（2）对一般图，其解法为：添加重复边以使G成为欧拉图G*，并使添加的重复边的边权之和为最小，再求G*的欧拉回路。
（3）
- 最优H圈（旅行售货员问题）：图论模型：在赋权完全图G中求具有最小权的哈密尔顿圈，这个圈称为最优圈。采用边交换技术求解最优H圈，详情见PPT
5. 匹配、最大匹配、完美匹配、最优匹配、因子分解
- 匹配：如果M是图G的边子集(不含环)，且M中的任意两条边没有共同顶点，则称M是G的一个匹配或边独立集
- 最大匹配：如果M是图G的包含边数最多的匹配，称M是G的一个最大匹配
- 完美匹配：若最大匹配饱和了G的所有顶点，称它为G的一个完美匹配
- 最优匹配：设G=(X, Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G的最优匹配
- 因子分解：所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。k-因子分解：每个因子均为k-因子的因子分解，此时称G本身是k-可因子化的
注：1、匹配、饱和点与非饱和点：设M是图G的边子集，若任意的e∈M，e 都不是环，且属于M的边互不相邻，则称M为G的一个匹配。设M为 G的一个匹配，对v∈V(G)，若v是M中某边的一个端点，则称v为M饱和点，否则称为M非饱和点
2、
3、完美匹配必是最大匹配，而最大匹配不一定是完美匹配；最大匹配必存在，但完美匹配不一定存在；G存在完美匹配的一个必要条件是G的点数必然为偶数
4、交错路与可扩路：设M为图G的一个匹配，G的M交错路是指G中由M中的边与非M中的边交替组成的路。 M可扩路是指其起点与终点均为M非饱和点的M交错路
5、
的完美匹配的个数分别为：（2n-1）!!、n！
6、覆盖：图G的一个覆盖是指V(G)的一个子集K，使得G的每条边都至少有一个端点在K中。G中点数最少的覆盖称为G的最小覆盖
7、设K是G的覆盖，M是G的匹配，由于M中的边互不相邻，若要覆盖中M中的边，至少需要|M|个顶点，所以|M| ≤ |K|。特别地，若M*是最大匹配，且
是最小覆盖，则
8、设M是匹配，K是覆盖，若|M| = |K|，则M是最大匹配,且K是最小覆盖
9、在偶图中，最大匹配中的边数等于最小覆盖中的点数
10、因子：图G的一个因子是指至少包含G的一条边的生成子图，即非空的生成子图就是一个因子(G的生成子图是指满足V(H) =V(G)的子图H)
11、k-因子指k正则的因子
6.平面图、极大平面图、极大外平面图、平面图的对偶图
- 平面图：如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图
- 极大平面图：设G是简单可平面图，如果G是Ki (1≤i≤4)，或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图
- 极大外平面图：若一个可平面图G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图
- 平面图的对偶图：给定平面图G，G的对偶图G*如下构造：1) 在G的每个面fi内取一个点vi*作为G*的一个顶点；2) 对G的一条边e，若e 是面 fi 与 fj 的公共边，则连接vi*与vj*，且连线穿过边e；若e是面fi中的割边，则以vi为顶点作环，且让它与e相交
注：1、设 f 是G的一个面，构成 f 的边界的边数(割边计算2次)称为面 f 的次数，记为deg( f )
2、
3、设G是具有m条边的平面图，则
4、设G是具有n个点，m 条边，φ个面的连通平面图，则有n–m+φ=2
5、设G是具有n个点，m条边，φ个面，k个连通分支的平面图，则
6、设G是具有n个点，m条边，φ个面的连通平面图，如果对G的每个面f，有deg(f )≥ l ≥3，则
(注意：G是平面图的必要条件，不是充分条件)
7、设G是具有n个点，m条边的简单平面图且n≥3，则
8、若G是简单平面图，则δ≤5
9、一个连通平面图G是2连通的当且仅当G的每个面的边界是圈
10、一个图可嵌入平面当且仅当它可嵌入球面
11、设G是极大平面图，则G必连通；若G的阶数至少等于3，则G无割边
12、设G是至少有3个顶点的平面图，则G是极大平面图的充分必要条件为G中各面的次数均为3且为简单图(极大平面图的三角形特征，即每个面的边界为三角形)
13、设G是一个有n个点，m条边，φ个面的极大平面图，且n≥3，则(1) m=3n–6(2) φ=2n–4
14、如果在不可平面图G中任意删去一条边所得的图为可平面图，则称G为极小不可平面图。例如K5和K3,3
15、设 G 是一个有 n (n≥3)个点，且所有点均在外部面上的外平面图，则G是极大外平面图当且仅当其外部面的边界是圈，内部面是三角形
16、设G是一个阶数为n (n≥4)且所有点均在外部面上的极大外平面图，则G中存在两个度数均为2且不相邻的点
17、设G是一个有n (n≥3)个点，且所有点均在外部面上的极大外平面图，则G有n–2个内部面
18、设G是一个具有n (n≥4)个点，m条边的简单连通外平面图。若G不含三角形，则m≤(3n–4)/2
19、每个至少有7个顶点的外可平面图的补图不是外可平面图，且7是这个数目的最小者
20、图G是可平面的当且仅当它不含与K5或K3,3同胚的子图
7.边色数、点色数、色多项式
- 边色数：设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为χ'(G)
- 点色数：对图G正常顶点着色需要的最少颜色数，称为图G的点色数，用χ(G)表示
- 色多项式：对图进行正常顶点着色，其方式数Pk(G)是k的多项式，称为图G的色多项式
注：
1、边着色/k边可着色：设G是图，对G的边进行着色，若相邻边着不同颜色，则称对G进行正常边着色； 如果能用k种颜色对图G 进行正常边着色，称G是k边可着色的
2、在任何正常边着色中，与任一顶点关联的各边必须着不同色，由此推知：对无环图
3、Km,n的一个正常边着色为 χ′(Km, n)=Δ
4、设G是非空的简单图。若G中恰有一个度为Δ(G)的点，或G中恰有两个度为Δ(G)的点并且这两个点相邻，则χ′(G)=Δ(G)
5、设图G=(V, E)是n阶简单图，若n=2k+1且边数m>kΔ，则χ′=Δ+1
6、设G是奇阶Δ正则简单图。若Δ>0，则 χ′=Δ+1
7、对任意的无环图G，均有χ ≤Δ+1
8、设G是简单连通图。假定G既不是完全图又不是奇圈，则χ ≤ Δ
9、设G是非空简单图，若G中度数最大的点互不相邻，则
10、对任意的简单平面图，均有χ≤5
11、若k<χ(G)，则Pk(G)=0； χ(G)=min{k | Pk(G)≥1}
12、若G为n阶空图，则Pk(G)=k^n
13、
14、若图G含有n个孤立点，则Pk(G)=k^n*Pk(G′)，其中G′是 G去掉n个孤立点后所得的图
15、若图G有环或有重边，则去掉环并将重边用单边代替之 后所得图的k着色数目与原图一样
16、设e=uv是图G的一条边，并且d(u)=1，则 Pk(G)=(k-1)Pk(G-u)
17、对n阶简单图G，Pk (G)是k的整系数n次多项式，首项为k^n，常数项为零，并且各项系数的符号正负相间
8.强连通图、单向连通图、弱连通图
- 强连通图：若D的中任意两点是双向连通的，称D是强连通图
- 单向连通图：若D中任意两点是单向连通的，称D是单向连通图
- 弱连通图：若D的基础图是连通的，称D是弱连通图
注：1、有向图D=(V, E)是强连通的当且仅当D中存在含有所有顶点的有向闭途径
2、设D'是有向图D=(V, E)的一个子图。如果D'是强连通的(单向连通的、弱连通的)，且D中不存在真包含D'的子图是强连通的(单向连通的、弱连通的)，则称D'是D的一个强连通分支(单向连通分支、弱连通分支)
3、有向图D=(V, E)的每个点位于且仅位于D的一个强(弱)连通分支中
4、若G是2边连通的，则G存在强连通定向图
5、若有向图D的基础图是树，则称D为有向树
6、恰有一个顶点的入度为0，其余顶点的入度均为1的非平凡有向树称为根树。根树中入度为0的顶点称为树根，出度为0的顶点称为树叶，其余点称为内点，内点和根统称为分支点。
7、根树T中，若每个分支点至多有m个儿子，则称T为m元树；若每个分支点恰有m个儿子，则称T为m元完全树
8、设m元完全树T的树叶数为t，分支点数为i，则(m-1)i=t-1
二、重要结论
1、握手定理及其推论
定理1 图G中所有顶点的度数和等于边数的2倍。
推论1 在任何图中，奇点个数为偶数。
推论2 正则图的阶数和度数不同时为奇数。
2、Turan定理
定理2 若n阶简单图G不包含
，则G度弱于某个完全l 部图 H，且若G具有与H相同的度序列，则G≌H
3、树的性质
定理3 设T是(n, m)树，则m=n-1
4、最小生成树算法
Kruskal算法，Prim算法，破圈法。
5、偶图判定定理
定理4 图G是偶图当且仅当G中没有奇圈
6、Menger定理
定理5 (1) 设x与y是图G中的两个不相邻点，则G中分离点x与y的最小点数等于独立的(x, y)路的最大数目；(2) 设x与y是图G中的两个不相邻点，则G中分离点x与y的最小边数等于G中边不重的(x, y)路的最大数目。
7、欧拉图、欧拉迹的判定
定理6 下列命题对于非平凡连通图G是等价的：
(1) G是欧拉图；
(2) G的顶点度数为偶数；
(3) G的边集合能划分为圈。
推论 连通非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。
8、H图的判定
定理7 (必要条件) 若G为H图，则对V(G)的任一非空顶点子集S，成立：ω(G－S) ≤|S|。
定理8 (充分条件) 对于n≥3的简单图G，如果δ(G) ≥n/2，则G是H图。
定理9 (充分条件) 对于n≥3的简单图G，如果G中的任意两个不相邻顶点u与v，有d(u)+d(v) ≥n，则G是H图。
定理10 (闭包定理) 图G是H图当且仅当它的闭包是H图。
定理11 (度序列判定法) 设简单图G的度序列是(d1, d2,…,dn)，其中d1≤d2≤…≤dn，并且n≥3。若对任意的m<n/2，或者
，或者
，则G是H图。
定理12 设G是n阶简单图。若n≥3且
则G是H图；并且具有n个顶点
条边的非H图只有C1,n以及C2,5
9、偶图匹配与因子分解
定理13 设G=(X, Y)是偶图，则G存在饱和X的每个顶点的匹配的充要条件是：
推论 若G是k (k>0)正则偶图，则G存在完美匹配。
定理14 在偶图中，最大匹配的边数等于最小覆盖的顶点数。
定理15 K2n可一因子分解。
定理16 具有H圈的三正则图可一因子分解。
定理17 K2n+1可2因子分解。
定理18 K2n可分解为一个1因子和n-1个2因子之和。
定理19 每个没有割边的3正则图是一个1因子和1个2因子之和。
10、平面图及其对偶图
1)平面图的次数公式
定理20 设G是平面图，则次数之和等于2倍的边数。
2)平面图的欧拉公式
定理21 (欧拉公式) 设G=(n, m)是连通平面图， φ是G的面数，则n-m+φ=2。
3)几个重要推论
推论1 设G是具有n个点m条边φ个面的连通平面图，如果对G的每个面f，有deg (f )≥l ≥3，则：
推论2 设G=(n,m)是简单平面图，则m≤3n-6。
推论3 设G是简单平面图，则δ(G)≤5。
注：推论2的证明
4)对偶图的性质
定理22 平面图G的对偶图必然连通。
5)极大平面图的性质
定理23 设G是至少有3个顶点的平面图，则G是极大平面图，当且仅当G的每个面的次数是3且为简单图。
11、着色问题
1)边着色
定理24 完全二部图的边色数等于顶点度数的最大值。
定理25 二部图的边色数等于顶点度数的最大值。
定理26 若G是简单图，则边色数要么为最大度，要么等于最大度+1。
定理27 设G是简单图且Δ(G)>0。若G中只有一个最大度点或恰有两个相邻的最大度点，则边色数等于最大度。
定理28 设G是简单图。若点数n=2k+1且边数m>kΔ，则边色数等于最大度+1。
定理29 设G是奇数阶Δ正则简单图，若Δ>0，则边色数等于最大度+1。
2)点着色
定理30 对任意的图G，
定理31 若G是连通的简单图，并且它既不是奇圈，又不是完全图，则
。
3)色多项式
a)递推计数法
定理32 设G为简单图，则对任意e∈E(G)，有
b)、理想子图计数方法
12根树问题
定理32 在完全m元树T中，若树叶数为t，分支点数为i，则(m-1)i = t-1。
Note：以上为暂时的全部总结，在近些天复习的过程中发现漏洞会及时填补。
补充内容
1、关于正则与完全图的一些理解：k正则图，指的是每个点都有k度，n阶k正则图就是n个顶点的度数都为k，而完全图是最大的正则，因此完全图中每个顶点的度数为n-1，为n-1正则图。
2、邻接矩阵的概念
定义 设n阶标定图G = (V, E)，V = {v1, v2,…, vn}，则G的邻接矩阵是一个n×n 矩阵A(G) = [ aij ] (简记为A)，其中若 vi邻接vj，则aij =1；否则aij =0
若aij 取为连接vi与vj 的边的数目，则称A为推广的邻接矩阵。
性质：邻接矩阵是一个对称方阵；简单标定图的邻接矩阵的各行 (列) 元素之和是该行 (列) 对应的点的度
定理 令G是一个有推广邻接矩阵A的 p阶标定图，则An的i 行 j 列元素aij(n)等于由vi到vj的长度为n的通道的数目
推论 设A为简单图G的邻接矩阵，则(1) 
的元素 
是 vi 的度数。A3 的元素 
是含 vi 的三角形的数目的两倍 (2) 若G是连通的，对于i≠j，vi 与vj 之间的距离是使An 的aij(n) ≠0 的最小整数n
3、l部图概念及特征
定义 若简单图G的点集V有一个划分：
且所有的Vi 非空，Vi 内的点均不邻接，称G是一个 l 部图。
定义 如果在一个l 部图G中, |Vi|=ni, 任何两点u∈Vi , v∈Vj , i ≠ j , i, j =1, 2,…, l 均邻接，则称G为完全l 部图。记作
4、生成树：若图G的生成子图T是树，则称T为G的生成树；若T为森林，称它是G的生成森林。生成树的边称为树枝，G中非生成树的边称为弦。
定理 每个连通图至少包含一棵生成树
计数：用τ(G) 表示G的生成树的个数，
一个定理：
5、单调不增正整数序列(d1, d2,…, dn)是一棵非平凡树的度序列当且仅当∑ di=2(n-1)
6、
7、简单图一定存在度数相同的顶点
8、k正则二部图（k正则偶图）G的相关结论：
（1）若k≥2，则G无割边
（2）存在完美匹配
（3）可1-因子化
9、彼得森图：
，其相关结论有：
- 点连通度为3，边连通度为3
- 是一个3正则图
- 点色数为3，边色数为4
- 半径与直径均为2
- 不是H图（删去任意顶点后为H图）
- 是不可平面图
- 存在完美匹配
- 虽然该图无割边，但也不可1-因子分解（3正则图有割边，不能1-因子分解）
- 是一个1-因子和一个2-因子的并
10、欧拉图相关等价命题：
- 每个点的度为偶数
- 是连通图
- 边集可以划分为边不重的圈的并
11、欧拉迹相关结论：
- 连通图存在欧拉迹当且仅当G最多有两个奇度顶点
- 有向图中存在欧拉迹，当且仅当D连通且除了两个点外，每个点出度与入度相等。而这两个点中，一个点入度比出度大1，另一个点出度比入度大1
12、完全偶图：是指具有二分类(X, Y )的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若 |X|=m，|Y|=n，则这样的偶图记为
13、相关结论（从平时作业中的选择题提炼出来）：
- 有割边的图不一定有割点，比如K2
- 有割点的图不一定有割边，比如8字形的图
- 割点至少属于图的两个块
- 割边不在图的任意一个圈之中
- 阶数至少是3的连通图中，图的割点也是子图的割点
- G为n阶简单图，若δ(G) ≥n/2，则G连通且λ(G)=δ(G)
- 非平凡树不一定存在割点，但一定存在割边，比如K2
- 完全图不一定没有割边，比如K2
- 2连通图一定没有割边
- 若图G是块，则块中不一定有圈，比如K2；块中不一定无环，比如自环
- 非平凡树T，最多包含一个完美匹配
- 非平凡树T是只有一个面（外平面）的平面图
- 非平凡树T的对偶图不一定是简单图，比如K2的对偶图为自环，自环不是简单图
- 无割边的三正则图一定存在完美匹配，有割边的三正则图不一定有完美匹配
- 有完美匹配的三正则图不一定没有割边
- 三正则哈密尔顿图存在完美匹配，可1-因子分解
- 任意非平凡正则偶图包含完美匹配且能够1-因子分解
- 只有一个面的连通平面图一定是树
- 存在一种方法，总可以把平面图中任意一个内部面转为外部面
- 无环图是2连通的平面图，一定不包含割点，同时不包含割边，一定不包含只属于一个面的边，边界均为圈
- 若（n,m）图是极大外平面图且n大于等于3，则m=2n-3
- 阶数至少为3的极大外平面图一定是H图
14、块的定义：没有割点的连通图称为块图，简称块。若图G的子图B是块，且G中没有真包含B的子图也是块，则称B是G的块
相关性质：
- 仅有一条边的块，要么是割边，要么是环
- 仅有一个点的块，不是孤立点就是自环
- 至少两个点的块无环
- 阶数至少为3的块无割边
- 阶数至少为3的块中的任意两点都位于同一个圈上
- 阶数至少为3的块中的任意两条边都在同一个圈上
15、欧拉图的相关结论：
- 一定是连通图
- 欧拉图不一定没有割点，比如8字形的图
- 欧拉图一定没有割边
- 非平凡的欧拉图中一定有圈
- 至少具有两个点的无环欧拉图一定是2边连通的
16、闭图：在n阶简单图G中，若对d(u)+d(v)≥n的任何一对点u和v都是相邻的，则称G是闭图
17、闭包：若一个与G 有相同点集的闭图 Ĝ，使G
Ĝ，且对异于Ĝ的任何图H，若有GHĜ，则H不是闭图，则称Ĝ是G的闭包
18、H图相关结论：（举反例想到长度为５的圈）
- 一定没有割边
- 不一定没有割点，比如H图+自环（也是H图，而自环让该点成为了割点）
- 一个简单图是H图当且仅当它的闭包是H图
G是n≥3的简单图，若G的闭包是完全图，则G是H图
若G是阶数至少为3的简单图，其中任何两个不邻接的点u和v均有d(u)+d(v)≥n，则 G是H图
- 若G是阶数至少为3的简单图，若G中每个点的度d(v)≥n/2，则G是H图
- 图G的闭包是Kn，则G是H图
- G为阶数至少为3的非H的简单图，G度弱于某个Cm,n图（度极大的H图）
- H图不一定是完全图，比如长度为5的圈
- G为阶数至少为3的H简单图，若n为奇数，则G一定不是偶图
19、G为n阶简单图，若任意两个顶点存在d(u)+d(v)大于等于n-1，则该图G存在H路
20、n方体：超立方体Qn简称为n方体，
。其构造方式为：n方体有2^n个顶点，每个顶点可以用长度为n的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同
其相关结论有：
-
- 每个n方体都有完美匹配（n大于等于1）
21、因子分解相关结论
- 若G有一个1-因子(其边集为完美匹配)，则显然G的阶数是偶数。所以，奇数阶图不能有1-因子。
- 完全图
是可以1-因子化 - k正则偶图(k>0)是1-可因子化
- 具有Hamilton圈的3正则图是1-可因子化的（注意：1-可因子分解的3正则图不一定有Hamilton圈）
- 若3正则图有割边，则不可1-因子分解（注意：无割边的3正则图可能也没有1-因子分解，比如彼得森图）
- K4有唯一的1-因子分解
- 一个图2-可因子化，则每个2-因子是边不重圈的并
2-可因子化的图的所有点的度一定是偶数，所以完全图
不是2-可因子化的- 若一个2-因子是连通的，则它是一个H圈
- 图
是n个H圈的并 - 完全图是一个1-因子和n-1个H圈的并
- 每一个没有割边的3正则图是一个1-因子和一个2-因子的并
- 若没有割边的3正则图中的2-因子是一些偶圈，则该图也是1-可因子化的
- 一个连通图是2-可因子化的当且仅当它是偶数度正则图
- 的不同1-因子数目为(2n-1)!!
22、存在且只存在5种正多面体：正四面体、正六面体、正八面体、正十二面体和正二十面体
23、一个有n个顶点，m条棱和φ个面的凸多面体的棱数与面数满足：n–m+φ=2。设每个面的次数为l，每个点的度数为r，则
24、对偶图相关结论：
- 平面图G的对偶图G*也是平面图，且G*的点数 = G的面数；G*的边数 = G的边数；G*的面数 = G的点数 (G连通)；d(vi*) = deg ( fi )
- 设G*是平面图G的对偶图，则G*必连通
- 假定G是平面图，则(G*)* = G当且仅当G是连通图
- 若G1≌G2，在一般条件下，只存在非同构的对偶图G1*与G2*
25、2度顶点的扩充与收缩：在图G的边上插入一个新的2度顶点，使一条边分成两条边，则称将图G在2度顶点内扩充；去掉图G的一个2度顶点，使这个2度顶点关联的两条边合成一条边，则称将G在2度顶点内收缩
同胚：两个图G1和G2，如果G1≌G2，或者通过反复在2度顶点内扩充和收缩它们能变成同构的，则称G1和G2是同胚的或G1和G2在2度顶点内是同构的
26、初等收缩/收缩边uv运算：设uv是简单图G的一条边。去掉该边，重合其端点，再删去由此产生的环和重边。这一过程称为图G的初等收缩或收缩边uv运算，并记所得之图为G/uv。一个图G可收缩到H，是指H可从G通过一系列初等收缩而得到
27、基础简单图：给定图G，去掉G中的环(若有的话)，将G中的重边(若有的话)用单边代替，称这样所得的图为G的基础简单图
与可平面性的关系：（1）图G是可平面图当且仅当其基础简单图是可平面图（2）图G是可平面图当且仅当它的每个块是可平面图
28、瓦格纳定理（平面图的判定定理）：简单图G是可平面图当且仅当它不含可收缩到K5或K3,3的子图（还是必要条件，不是充要条件）
29、临界图：若对图G的任意真子图H都有χ(H)< χ(G)，则称G是临界图；色数为k的临界图称为k临界图
相关性质：k色图均有k临界子图；每个临界图均为简单连通图；若G是k临界图，则δ≥k-1；临界图没有割点
30、每个k色图至少有k个度不小于k-1的顶点
31、唯一可着色图：设简单标号图G的色数是k，如果在任意的k正常点着色方案下，导出的顶点集合划分唯一，称G是唯一k可着色图，简称唯一可着色图
相关结论：
- δ≥k-1；
- 在G的任意一种k着色中，G的任意两个色组的并导出的子图是连通的；
- 每个唯一k (k≥2)可着色图是(k-1)连通的；
- 设G是唯一n(n≥2)可着色图，π是任意一种n着色方案，则由π的任意k个色组导出的子图是(k-1)连通的
- 唯一1可着色图是空图
- 唯一2可着色图是连通的偶图
- 每个唯一4可着色可平面图都是极大可平面图
32、团：图G的一个团是指G的顶点子集S，使得导出子图G[S]是完全图。G的k团是指G的含k个点的团；G的最大团的点数称为G的团数记为cl(G)，即cl(G)=max{|S| | S是G的团}。图G的色数与团数的关系为
33、完美图：设G是一个图，若对G的每个点导出子图H，均有 χ(H)=cl(H)，则称G为完美图。图G是完美图当且仅当G的补图是完美图
相关结论：
- 完全图、偶图均为完美图，而不含三角形但含奇圈的图不是完美图
- 偶图的补图是完美图
- 长度至少为5的奇圈及其补图均不是完美图
34、理想子图：设H是图G的生成子图。若H的每个分支均为完全图，则称H是G的一个理想子图。用Nr (G)表示G的具有r个分支的理想子图的个数。设G是具有n个点m条边的图，则有(1) Nn(G)=1;
(2) Nn-1(G)=m;(3) 若k<ω(G)，则Nk(G)=0
35、独立数:一个图的点独立集，简称独立集，是指图中一些互不相邻的点构成的点子集。图G中含点数最多的独立集称为G的最大独立集；最大独立集所含的顶点数称为G的点独立数，简称独立数，记为α(G)，简记为α
36、图G的最大独立集中包含的顶点个数与G的最小覆盖中包含的顶点个数之和等于G的阶数
37、覆盖数：G的一个包含顶点数最少的覆盖称为G的最小覆盖。G的最小覆盖包含的顶点数，称为G的点覆盖数，简称覆盖数，记为β(G)
38、拉姆齐数：设m和n是两个正整数，令R(m, n)是最小的正整数l使得任意的l阶图要么包含m个顶点的团，要么包含n个顶点的独立集。R(m, n)称为(m, n)Ramsey数。R(2, n)=n，R(3, 3)=6，
R(m, n)=R(n, m)，R(1, n)=R(n, 1)=1
39、高为h的完全二元树至少有h+1片树叶
40、最优树：设T是一棵有t片树叶的二元树，若对T的所有t片树叶赋以权值(实数) w1, w2,…, wt，则称T为带权二元树；若带有权wi的树叶的层数为l(wi)，则称
为T的权，给定实数w1, w2,…, wt，在所有树叶带有权w1, w2,…, wt 的二元树中，W(T)最小的二元树称为最优树。
41、频序列：设n阶图G 的各点的度取s个不同的非负整数d1, d2,…, ds。又设度为di的点有bi个(∑bi=n)，则称 (b1, b2,…, bs) 为G的频序列
相关结论：
- 一个n阶图G 和它的补图有相同的频序列
- 一个简单图G 的n个点的度不能互不相同
42、完全图Kn相关结论
- 点色数为n
- 边色数为：n（n为奇数时）；n-1（n为偶数时）
- 点连通度为n-1
- 边连通度为n-1
- 是临界图
- 是唯一可着色图
43、关联矩阵：无环图G的关联矩阵B(G) = [bij] (简记为B)是一个n×m 矩阵，当点vi 与边ej 关联时 bij =1，否则 bij =0。其性质为：关联矩阵的每列和为2；其行和为对应顶点的度数。
44、有向图的邻接矩阵、关联矩阵：设D=(V, E)是一个标定有向图，其中设V={v1, v2,…, vn}，E={e1, e2,…, em}：
(1) 称矩阵A(D)=(ai j)n×n为D的邻接矩阵，其中ai j是以vi作为始点，vj作为终点的边的数目，1≤ i ≤n, 1≤ j ≤n
(2) 若D无环，称矩阵M(D)=(mi j)n×m为D的关联矩阵，其中
。由定义可知，邻接矩阵A(D)的所有元素之和等于边数。关联矩阵中列和等于0；一行中1的和等于出度之和，-1的和等于入度之和；其全部元素之和等于0。
45、有向图相关结论
- 有向图D的任意一个顶点只能处于D的某一个强连通分支中
- 有向图D中，顶点ｖ可能处于D的不同的单向连通分支中
- 有向连通图中顶点间的关系是等价关系
- 强连通图的所有顶点必然处于某一有向闭途径之中
46、假定G*是在图G中添加一些重复边得到的欧拉图，则G*具有最小权值的充要条件是（1）G的每一条边最多被添加一次（2）对于G*的每个圈来说，新添加的边的总权值不超过该圈总权值的一半
47、5阶度极大非哈密尔顿图族有
48、设树T 中度数为i 的顶点的个数为ni (1≤ i ≤k) ，则
49、图兰定理： 若G是n阶简单图，并且不包含Kl+1，则边数 m(G) ≤ m(Tl, n)。 此外，仅当G ≌ Tl, n时，m(G) = m(Tl, n)。
如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。您的鼓励是博主的最大动力！
支持一下博主，给博主买瓶饮料，那就太谢谢啦~
