【人工智能学习笔记】 1.5离散数学 -7.图的基本概念

北京大学慕课学习笔记

图的基本概念

可图化充要条件

非负整数列$d=(d_1,d_2,…,d_n)$d=(d1​,d2​,…,dn​)可图化$\Leftrightarrow$⇔
$d_1+d_2+…+d_n \equiv 0 (mod 2).$d1​+d2​+…+dn​≡0(mod2).
• 证: ($\Rightarrow$⇒) 握手定理
($\Leftarrow$⇐) 奇数度点两两之间连一边,
剩余度用环来实现. #

可简单图化

• 设非负整数列$d=( d_1, d_2, …, d_n )$d=(d1​,d2​,…,dn​), 若存在简单图G, 使
得G的度数列是d, 则称d为可简单图化的
• 例：d = ( 5, 3, 3, 2, 1 ) 不可简单图化
– $\Delta =n (\Delta \leq n-1)$Δ=n(Δ≤n−1)
• 例：d = ( 4, 4, 3, 2, 1 ) 不可简单图化
– (n-1, n-1, … ,1)

可简单图化充要条件(Havel定理)

• 设非负整数列$d=( d_1, d_2, …, d_n )$d=(d1​,d2​,…,dn​)满足:
$d_1+d_2+…+d_n \equiv 0 (mod 2).$d1​+d2​+…+dn​≡0(mod2).,
$n-1 \geq d_1 \geq d_2 \geq … \geq d_n \geq 0,$n−1≥d1​≥d2​≥…≥dn​≥0,
则d可简单图化$\Leftrightarrow$⇔
$d’=(d_2-1,d_3-1,…,d_{d_1+1}-1,d_{d_1+2},…,dn)$d’=(d2​−1,d3​−1,…,dd1​+1​−1,dd1​+2​,…,dn)
可简单图化
• 例: d=(4,4,3,3,2,2), d’=(3,2,2,1,2)

Havel定理举例

• 判断下列非负整数列是否可简单图化. (1)
(5,5,4,4,2,2) (2)(4,4,3,3,2,2)
• 解: (1) (5,5,4,4,2,2), (4,3,3,1,1),
(2,2,0,0), (1,-1,0), 不可简单图化.
(2) (4,4,3,3,2,2), (3,2,2,1,2), (3,2,2,2,1),
(1,1,1,1), (0,1,1), (1,1), 可简单图化. #

可简单图化充要条件

• 定理7.4(P.Erdös,T.Gallai,1960):
设非负整数列$d=( d_1, d_2, …, d_n )$d=(d1​,d2​,…,dn​)满足:
$n-1 \geq d_1 \geq d_2 \geq … \geq d_n \geq 0,$n−1≥d1​≥d2​≥…≥dn​≥0,
则d可简单图化$\Leftrightarrow$⇔
$d_1+d_2+…+d_n=0(mod 2)$d1​+d2​+…+dn​=0(mod2)
并且对r=1,2,…,n-1有
$d_1+d_2+…+d_r \leq r(r-1)+min\{r,d_{r+1}\}+ min\{r,d_{r+2}\}+…+min\{r,d_n\}.$d1​+d2​+…+dr​≤r(r−1)+min{r,dr+1​}+min{r,dr+2​}+…+min{r,dn​}.

定理7.4等价形式

• 定理7.4’(P.Erdös,T.Gallai,1960):非负整数列
$d=( d_1, d_2, …, d_n )$d=(d1​,d2​,…,dn​)可简单图化 $\Leftrightarrow$⇔
$d_1+d_2+…+d_n \equiv 0 (mod 2).$d1​+d2​+…+dn​≡0(mod2).,
并且对r=1,2,…,n有
$d_1+d_2+…+d_r \leq r(r-1)+min\{r,d_{r+1}\}+ min\{r,d_{r+2}\}+…+min\{r,d_n\}.$d1​+d2​+…+dr​≤r(r−1)+min{r,dr+1​}+min{r,dr+2​}+…+min{r,dn​}.#
• 说明: $n-1 \geq d_1 \geq d_2 \geq … \geq d_n \geq 0,\Rightarrow d_1+d_2+…+d_n \leq n(n-1)$n−1≥d1​≥d2​≥…≥dn​≥0,⇒d1​+d2​+…+dn​≤n(n−1)

定理7.4举例

• 下列非负整数列是否可简单图化?
(1) (5,4,3,2,2,1)
(2) (5,4,4,3,2)
(3) (3,3,3,1)
(4) (6,6,5,4,3,3,1)
(5) (5,5,3,3,2,2,2)
(6)$( d_1, d_2, …, d_n ), d_1>d_2>…>d_n \geq 1$(d1​,d2​,…,dn​),d1​>d2​>…>dn​≥1

定理7.4举例

• (1) 5+4+3+2+2+1=17 $\neq$​= 0(mod 2).
不可(简单)图化.
• (2) 5+4+4+3+2=18=0(mod 2).
但是$d_1$d1​=5>n-1=4,不满足n-1$\geq d_1$≥d1​
, 不可简单图化.
( 或者: 但是r=1时, $d_1$d1​=5>1(1-1)+min{1,4} +min{1,4}+min{1,3}
+min{1,2}=4, 不可简单图化.)
• (3) 3+3+3+1=10=0(mod 2). $d_1$d1​=3=n-1,满足n-1$\geq d_1$≥d1​
,
但是r=2时, $d_1+d_2$d1​+d2​=6 > 2(2-1) + min{2,3} + min{2,1} = 5,
不可简单图化.

Paul Erdös

“My mother said, ‘Even you, Paul, can be in only one
place at one time.’
Maybe soon I will be relieved of this disadvantage.
Maybe, once I’ve left, I’ll be able to be in many places
at the same time.
Maybe then I’ll be able to collaborate with
Archimedes and Euclid.”