电⼦科技⼤学《图论及其应⽤》复习（史上最全汇总）
沈阳航空学院王婷
⼀、重要概念
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，E1\E)称为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连通、⽆割边且⾄少含有两个点
244uu（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边可着⾊的
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议