2023年7月19日发(作者：)

电⼦科技⼤学《图论及其应⽤》复习（史上最全汇总）⼀、重要概念1. 图、简单图、图的同构、度序列与图序列、补图与⾃补图、两个图的联图、两个图的积图、偶图图：⼀个图是⼀个有序对，记为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

　　 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，则条件，不是充分条件)　　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同胚的⼦图(注意：G是平⾯图的必要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≌H3、树的性质定理3 设T是(n, m)树，则m=n-14、最⼩⽣成树算法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。若对任意的m0)正则偶图，则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 完全图不⼀定没有割边，⽐如K22连通图⼀定没有割边若图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 有相同点集的闭图 Ĝ，使G18、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路Ĝ，且对异于Ĝ的任何图H，若有GHĜ，则H不是闭图，则称Ĝ是G的闭包 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)=035、独⽴数:⼀个图的点独⽴集，简称独⽴集，是指图中⼀些互不相邻的点构成的点⼦集。图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)=139、⾼为h的完全⼆元树⾄少有h+1⽚树叶40、最优树：设T是⼀棵有t⽚树叶的⼆元树，若对T的所有t⽚树叶赋以权值(实数) w1, w2,…, wt，则称T为带权⼆元树；若带有权wi的树叶的层数为l(wi)，则称树称为最优树。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为T的权，给定实数w1, w2,…, wt，在所有树叶带有权w1, w2,…, wt 的⼆元树中，W(T)最⼩的⼆元　　(2) 若D⽆环，称矩阵M(D)=(mi j)n×m为D的关联矩阵，其中等于0。45、有向图相关结论

有向图D的任意⼀个顶点只能处于D的某⼀个强连通分⽀中有向图D中，顶点ｖ可能处于D的不同的单向连通分⽀中有向连通图中顶点间的关系是等价关系强连通图的所有顶点必然处于某⼀有向闭途径之中

。由定义可知，邻接矩阵A(D)的所有元素之和等于边数。关联矩阵中列和等于0；⼀⾏中1的和等于出度之和，-1的和等于⼊度之和；其全部元素之和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)。