发布时间 : 星期二 文章图论重要结论更新完毕开始阅读d436f1262cc58bd63086bd46
v??d(v)?2mV(G)定理1： 图G= (V, E)中所有顶点的度的和等于边数m的2倍，即： 推论1 在任何图中，奇点个数为偶数。 推论2 正则图的阶数和度数不同时为奇数 。
定理2 若n阶简单图G不包含Kl+1，则G度弱于某个完全 l 部图 H，且若G具有与 H 相同的度序列，则: G ?H定理3 设T是(n, m)树，则： m?n?1偶图判定定理: 定理4 图G是偶图当且仅当G中没有奇回路。 敏格尔定理: 定理5 (1) 设x与y是图G中的两个不相邻点，则G中分离点x与y的最小点数等于独立的(x, y)路的最大数目； (2)设x与y是图G中的两个不相邻点，则G中分离点x与y的最小边数等于G中边不重的(x, y)路的最大数目。
欧拉图、欧拉迹的判定: 定理6 下列陈述对于非平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数； (3) G的边集合能划分为圈。
推论： 连通非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。
H图的判定: 定理7 (必要条件) 若G为H图，则对V(G)的任一非空顶点子集S，有： ?(G?S)?S定理8 (充分条件) 对于n≧3的单图G，如果G中有：? (G)?n定理9 (充分条件) 对于n≧3的单图G，如果G中的任意两个不相2邻顶点u与v，有：d (u)?d(v)?n定理10 (帮迪——闭包定理) 图G是H图当且仅当它的闭包是H图。
定理11(Chvátal——度序列判定法) 设简单图G的度序列是(d1,d2,…,dn), 这里，d1≦d2≦…≦dn,并且n≧3.若对任意的m
??2??1?定理13 (Hall定理）设G=(X, Y)是偶图，则G存在饱和X每个顶点的匹配的充要条件是：对 ?S?X,有N(S)?S(*)推论：若G是k (k>0)正则偶图，则G存在完美匹配。定理14 (哥尼，1931) 在偶图中，最大匹配的边数等于最小覆盖的顶点数。 定理15 K2n可一因子分解。 定理16 具有H圈的三正则图可一因子分解。 定理17 K2n+1可2因子分解。
定理18 K2n可分解为一个1因子和n-1个2因子之和。
定理19 每个没有割边的3正则图是一个1因子和1个2因子问题可模型为一个偶图。
之和。若n为偶数，且δ(G)≥n/2+1, 则n阶图G有3因子 一节课对应边正常着色的一个色组。由于G是偶图，所以边色数定理20 设G=(n, m)是平面图，则： ?deg(f)?2m为G的最大度35。这样，最少总课时为35节课。平均每天要安排
f??n?m???27节课。 如果每天安排8节课，因为G的总边数为240，所定理21(欧拉公式) 设G=(n, m)是连通平面图，ф是G的面数，则： 以需要的教室数为240/40=6。
推论1 设G是具有n个点m条边ф个面的连通平面图，如果对G定理5 一个n阶图G相和它的补图有相同的频序列。
的每个面f ,有：deg (f) ≥ l ≥3,则： m?ll?2(n?2)边不重复的途径称为迹 ； 点不重复的途径称为路。显然路
推论2 设G是具有n个点m条边ф个面的简单平面图，则：m ?3n?必为迹。6 推论3 设G是具有n个点m条边的简单平面图，则：? ?5图G的直径定义为d(G) = max{ d(u, v) | u, v∈V}
定理22 平面图G的对偶图必然连通.
证明：若δ≥2，则G中必然含有圈。证明：只就连通图证明定理23 设G是至少有3个顶点的平面图，则G是极大平面图，即可！设W=v1v2…..vk-1vk是G中的一条最长路。由于δ≥2，所当且仅当G的每个面的次数是3且为单图。 以vk必然有相异于vk-1的邻接顶点。又W是G中最长路。
??(Km,n)??所以，这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为定理25 (哥尼，1916)若G是偶图，则 ??(G)??vm，则vmvm+1….v kvm为G中圈。
定理26 (维津定理，1964) 若G是单图，则：? ?(G)??或??(G)??+1设G是具有m条边的n阶单图，证明：若G的直径为2且Δ定理27 设G是单图且Δ(G)>0。若G中只有一个最大度点或恰有(G)=n-2,则m ≥2n-4. 证明：设d (v)=Δ=n-2,且设v的邻接点为两个相邻的最大度点，则： ??(G)??(G)v1,v2,…,vn-2. u是剩下的一个顶点。由于d (G)=2且u不能和v邻
定理28 设G是单图。若点数n=2k+1且边数m>kΔ,则： ??(G)??(G接，所以)?1u必须和v1,v2…,vn-2中每个顶点邻接。
定理29 设G是奇数阶Δ正则单图,若Δ>0,则：? ?(G)??(G)?1否则有d (G)>2.于是得： m ≥2n-4.
定理31(布鲁克斯，1941) 若G是连通的单图，并且它既不是奇圈，定理8 一个图是偶图当且当它不包含奇圈。
又不是完全图，则： ?(G)??(G)证明 设G是具有二分类（X, Y）的偶图，并且C = v0 v1… vk v0定理32 在完全m元树T中，若树叶数为t , 分支点数为(i , m则：?1)
i?t?是1G的一个圈。不失一般性，可假定v0 ∈ X 。这样， v2i ∈ X ，) 根树:一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而且v2i +1∈Y 。又因为v0 ∈ X ，所以vk ∈ Y 。由此即得C是其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为偶圈。显然仅对连通图证明其逆命题就够了。设G是不包含奇圈0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的连通图。任选一个顶点u且定义V的一个分类（X, Y）如下：
的点称为内点。又将内点和树根统称为分支点。
X = {x | d (u, x) 是偶数，x∈V(G)}
敏格尔定理: 定理5 (1) 设x与y是图G中的两个不相邻点，则Y = {y | d (u, y) 是奇数，y∈V(G)} 现在证明（X, Y）是G的一G中分离点x与y的最小点数等于独立的(x, y)路的最大数目；2)设个二分类。 假设v和w是X的两个顶点，P是最短的（u, v）x与y是图G中的两个不相邻点，则G中分离点x与y的最小边数路，Q是最短的（u, w）路，以u1记P和Q的最后一个公共顶点。等于G中边不重的(x, y)路的最大数目。
因P和Q是最短路，P和Q二者的（u1, u）节也是最短的路，故 例2 (排课表问题) 在一个学校中，有7个教师12个班级。在长相同。现因P和Q的长都是偶数，所以P的（u1, v）节P1和Q每周5天教学日条件下，教课的要求由如下矩阵给出：
的（u1, w）节Q1必有相同的奇偶性。由此推出路（v, w）长为偶??323333333333?数。若v和w相连，则 就是一个奇圈，与假设矛?136042513304???05500505055?P??5盾，故X中任意两个顶点均不相邻。
?242424242423????352203144325??550055050550?设A 为4圈C4 的邻接矩阵，求A的谱。所以A 的特征值为 - 2 ,
???034343434330??基本回路是点不重复，简单回来，边不重
0, 2 ; 其重数依次记为1,2,1。故Spec A = ???202??121??1 设G是具有n个点m条边的图，则以下关于树的命题等价。（1）G 是树。（2）G 中任意两个不同点之间存在唯一的路。（3）G 连通，删去任一边便不连通（4）G 连通，且 m = n-1。5）G 无圈，且 m = n-1 。（6）G 无圈，添加任一条边可得唯一的圈。
?(G)??(G?e)??(G?e)
定义2 设T 是图G = (V, E) 的一棵生成树，m 和 n 分别是 G 的边数与顶点数，e1, e2 ,…, em-n+1 为 T 的弦，设 Cr 是T 加 er 产生的圈，r = 1, 2 ,…, m-n+1, 称 Cr 为对应于弦 er 的基本回路， 称｛C1,C2 ,…,Cm-n+1｝为对应于生成树T 的基本回路系统。
定理8 连通图G的任一回路均可表示成若干个基本回路的对称差。
(1) 若ω(G-v)＞ω(G), 则 v 必为G 的割点；(2) 若G无环且非平凡
，
则
v
是
G
的
割
点
当
且
仅
当 ω(G-v)＞ω(G) 定理3 设v是无环连通图G的一个顶点，则v是G的割点当且仅当V(G-v)可划分为两个非空顶点子集V1与V2，使x∈V1，y∈V2，点v都在每一条 (x, y) 路上。 若e是图G的割边或e是一个环，则G[{e}]是G的块； G的仅含一个点的块或是孤立点,或是环导出的子图； 至少两个点的块无环，至少三个点的块无割边。
定理4 设图G的阶至少为3，则G是块当且仅当G无环并且任意两点都位于同一个圈上。
推论 设G的阶至少为3，则G是块当且仅当G无孤立点且任意两
条边都在同一个圈上。定理5 点v是图G的割点当且仅当v至少属于G的两个不同的块。
图G是2边连通的当且仅当G连通、无割边且至少含有两个点。 引理1 设G是n阶简单图，若δ(G)≥ n/2则G必连通。 定理8 设G是n 阶简单图，对正整数 k k 连通的。 定理5(Chvátal——度序列判定法) 设简单图G的度序列是(d1,d2,…,dn), 这里，d1≦d2≦…≦dn,并且n≧3.若对任意的m 证明：若n为偶数，且δ(G)≥n/2+1 ,则n阶图G有3因子。证明：因δ(G)≥n/2+1 ,由狄拉克定理：n阶图G有H圈C .又因n为偶数，所以C为偶圈。于是由C可得到G的两个1因子。设其中一个为F1。考虑G1=G-F1。则δ(G1)≥n/2。于是G1中有H圈C1. 作H=C1∪F1。显然H是G的一个3因子证明 K5 和 K 3,3 是不可平面图。 引理 设G是极大平面图，则G必连通；若G的点数n≥3，则G无割边。（1）若G不连通，则G至少存在两个连通分支G1与G2。显然G1与G2也是平面图。将G2画在G1的外部面内，并分别在G1与G2的外部面上各取一个点u和v。很明显， u与v不相邻。连接u和v，记所得的图为G* 。易知G*也是平面图，这与G是极大平面图矛盾，所以G连通。推论 设G是一个有n个点m条边ф个面的极大平面图，n≥3，则 （1）m = 3n-6； （2）ф= 2n-4。 定理12 设G*是平面图G的对偶图，则G*必连通。) 同构的平 面图可以有不同构的对偶图. 对于3阶以上的具有m条边的单图G来说，如果G满足如下条件之一： (1) m>3n-6 OR m>(n-2)l/(l-2);(2) K5是G的一个子图；(3) K3,3是G的一个子图， 那么，G是非可平面图。 定理15 (Wangner瓦格纳定理) 简单图G是可平面图当且仅当它不含可收缩到K5或K3, 3的子图。G是一个简单图，若顶点数n≥ 11,则G与G的补图中，至少有一个是不可平面图 (要求用推理方法). 一个简单图有多少个定向图？因为每条边有2种定向方式，所以共有2 m(G)种定向。