文档库

最新最全的文档下载
当前位置:文档库 > 图论重要结论

图论重要结论

定理1: 图G= (V, E)中所有顶点的度的和等于边数m 的2倍,即: 推论1 在任何图中,奇点个数为偶数。 推论2 正则图的阶数和度数不同时为奇数 。

定理2 若n 阶简单图G 不包含Kl+1,则G

图论重要结论

度弱于某个完全 l 部图 H ,且若G 具有与

图论重要结论

H 相同的度序列,则: 定理3 设T 是(n, m)树,则: 偶图判定定理: 定理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 ,有:定理8 (充分条件) 对于n ≧3的单图G ,如果G 定理9 (充分条件) 对于n ≧3的单图G ,如果G 邻顶点u 与v ,有: 定理10 (帮迪——闭包定理) 图G 是H 图当且仅当它的闭包是H 图。

定理11(Chv átal ——度序列判定法) 设简单图G 的度序列是(d1,d2,…,dn), 这里,d1≦d2≦…≦dn,并且n ≧3.若对任意的mm,或者dn-m ≧ n-m,则G 是定理12 设G 是n 阶单图。若n ≧3且 则G 是H 图;并且,具有n 个顶点 H 图只有C1,n 以及C2,5.

定理13 (Hall X 每个顶点推论:若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因子 定理20 设G=(n, m)是平面图,则:

定理21(欧拉公式) 设G=(n, m)是连通平面图,ф是G 的面数,则: 推论1 设G 是具有n 个点m 条边ф个面的连通平面图,如果对G 的每个面f ,有:deg (f) ≥ l ≥3,推论2 设G 是具有n 个点m 条边ф个面的简单平面图,则: 推论3 设G 是具有n 个点m 条边的简单平面图,则: 定理22 平面图G 的对偶图必然连通.

定理23 设G 是至少有3个顶点的平面图,则G 是极大平面图,当且仅当G 的每个面的次数是3且为单图。 定理25 (哥尼,1916)若G 是偶图,则 定理26 (维津定理,1964) 若G 是单图,则: 定理27 设G 是单图且Δ(G)>0。若G 中只有一个最大度点或恰有两个相邻的最大度点,则: 定理28 设G 是单图。若点数n=2k+1且边数m>k Δ,则: 定理29 设G 是奇数阶Δ正则单图,若Δ>0,则: 定理31(布鲁克斯,1941) 若G 是连通的单图,并且它既不是奇圈,又不是完全图,则: 定理32 在完全m 元树T 中,若树叶数为t , 分支点数为i , 则:

) 根树:一棵非平凡的有向树T ,如果恰有一个顶点的入度为0,而其余所有顶点的入度为1,这样的的有向树称为根树。其中入度为0的点称为树根,出度为0的点称为树叶,入度为1,出度大于1的点称为内点。又将内点和树根统称为分支点。

敏格尔定理: 定理5 (1) 设x 与y 是图G 中的两个不相邻点,则G 中分离点x 与y 的最小点数等于独立的(x, y)路的最大数目;2)设x 与y 是图G 中的两个不相邻点,则G 中分离点x 与y 的最小边数等于G 中边不重的(x, y)路的最大数目。

例2 (排课表问题) 在一个学校中,有7个教师12个班级。在每周5天教学日条件下,教课的要求由如下矩阵给出:

基本回路是点不重复,简单回来,边不重

问题可模型为一个偶图。

一节课对应边正常着色的一个色组。由于G 是偶图,所以边色数为G 的最大度35。这样,最少总课时为35节课。平均每天要安排7节课。 如果每天安排8节课,因为G 的总边数为240,所以需要的教室数为240/40=6。

定理5 一个n 阶图G 相和它的补图有相同的频序列。

边不重复的途径称为迹 ; 点不重复的途径称为路。显然路

必为迹。 图G 的直径定义为d(G) = max{ d(u, v) | u, v ∈V}

证明:若δ≥2,则G 中必然含有圈。证明:只就连通图证明即可!设W=v1v2…..vk-1vk 是G 中的一条最长路。由于δ≥2,所以vk 必然有相异于vk-1的邻接顶点。又W 是G 中最长路。

所以,这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为vm ,则vmvm+1….v kvm 为G 中圈。

设G 是具有m 条边的n 阶单图,证明:若G 的直径为2且Δ(G)=n-2,则m ≥2n-4. 证明:设d (v)=Δ=n-2,且设v 的邻接点为v1,v2,…,vn-2. u 是剩下的一个顶点。由于d (G)=2且u 不能和v 邻

接,所以u 必须和v1,v2…,vn-2中每个顶点邻接。

否则有d (G)>2.于是得: m ≥2n-4.

定理8 一个图是偶图当且当它不包含奇圈。

证明 设G 是具有二分类(X, Y )的偶图,并且C = v0 v1… vk v0是G 的一个圈。不失一般性,可假定v0 ∈ X 。这样, v2i ∈ X ,且v2i +1∈Y 。又因为v0 ∈ X ,所以vk ∈ Y 。由此即得C 是偶圈。显然仅对连通图证明其逆命题就够了。设G 是不包含奇圈的连通图。任选一个顶点u 且定义V 的一个分类(X, Y )如下:

X = {x | d (u, x) 是偶数,x ∈V(G)}

Y = {y | d (u, y) 是奇数,y ∈V(G)} 现在证明(X, Y )是G 的一个二分类。 假设v 和w 是X 的两个顶点,P 是最短的(u, v )路,Q 是最短的(u, w )路,以u1记P 和Q 的最后一个公共顶点。因P 和Q 是最短路,P 和Q 二者的(u1, u )节也是最短的路,故长相同。现因P 和Q 的长都是偶数,所以P 的(u1, v )节P1和Q 的(u1, w )节Q1必有相同的奇偶性。由此推出路(v, w )长为偶数。若v 和w 相连,则 就是一个奇圈,与假设矛盾,故X 中任意两个顶点均不相邻。

设A 为4圈C4 的邻接矩阵,求A 的谱。所以A 的特征值为 - 2 ,

0, 2 ; 其重数依次记为1,2,1。故Spec A = 3

233333333331360425133045055005050552

42424242423352203144325550055050550034343434330P ??

?

? ?

?

= ? ?

?

? ??

?

()

()2v V G d v m

∈=∑

G H

?1

m

n =-(*)

S

deg()2f f m

∈Φ

=∑2

n m φ-+=36m n ≤-5

δ≤,()m n K χ'=?

()G χ'=?

()()+1G G χχ''=?=?或()()

G G χ'=?()()1G G χ'=?+()()1

G G χ'=?+()()

G G χ≤?(1)1

m i t -=-()()d u d v n

+≥?

?

?

???-121202

1 设G是具有n个点m条边的图,则以下关于树的命题等价。(1)

G 是树。(2)G 中任意两个不同点之间存在唯一的路。(3)G 连通,删去任一边便不连通(4)G 连通,且m = n-1。5)G 无圈,且m = n-1 。(6)G 无圈,添加任一条边可得唯一的圈。

定义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

或有dm>m,或有dn-m ≧n-m,则G是H图。

证明:若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)种定向。

图论重要结论

图论重要结论

图论重要结论

)

(

)

(

)

(e

G

e

G

G?

+

-

τ

τ