Erdos-Gallai定理与Havel算法
Erdos-Gallai定理与Havel算法度数列(d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)(d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0)(d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)可简单图化的充要条件是:∑i=1ndi\sum_{i=1}^nd_i∑i=1ndi为偶数
Erdos-Gallai定理
数列 ( d 1 , d 2 , . . . , d n ) ( n − 1 ≥ d 1 ≥ d 2 ≥ . . . ≥ d n ≥ 0 ) (d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0) (d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)可简单图化的充要条件是:
- ∑ i = 1 n d i \sum_{i=1}^nd_i ∑i=1ndi为偶数
- ∀ r ( 1 ≤ r ≤ n ) , ∑ i = 1 r d i ≤ r ( r − 1 ) + ∑ i = r + 1 n min { r , d i } \forall r(1\le r\le n),\sum_{i=1}^rd_i\le r(r-1)+\sum_{i=r+1}^n\min\{r,d_i\} ∀r(1≤r≤n),∑i=1rdi≤r(r−1)+∑i=r+1nmin{r,di}
证明
必要性:
考虑编号
1
∼
r
1\sim r
1∼r的点,内部连边数不超过
1
2
r
(
r
−
1
)
\frac{1}{2}r(r-1)
21r(r−1),与其他点连边总数不超过
∑
i
=
r
+
1
n
min
{
r
,
d
i
}
\sum_{i=r+1}^n\min\{r,d_i\}
∑i=r+1nmin{r,di}。即得
∑
i
=
1
r
d
i
≤
r
(
r
−
1
)
+
∑
i
=
r
+
1
n
min
{
r
,
d
i
}
\sum_{i=1}^rd_i\le r(r-1)+\sum_{i=r+1}^n\min\{r,d_i\}
∑i=1rdi≤r(r−1)+∑i=r+1nmin{r,di}。
充分性:
用数学归纳法证明。
①
n
=
1
n=1
n=1时,构造平凡图即可。
②假设
n
=
k
−
1
n=k-1
n=k−1时结论成立。当
n
=
k
n=k
n=k时,证明过程略(可以看这篇https://blog.csdn.net/hdmmblz/article/details/86506433)。
推论
数列 ( d 1 , d 2 , . . . , d n ) ( n − 1 ≥ d 1 ≥ d 2 ≥ . . . ≥ d n ≥ 0 ) (d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0) (d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)可简单图化当且仅当数列 s o r t e d ( d 2 − 1 , d 3 − 1 , . . . , d d 1 + 1 − 1 , d d 1 + 2 , . . . , d n ) sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n) sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化。
证明
充分性:
若
s
o
r
t
e
d
(
d
2
−
1
,
d
3
−
1
,
.
.
.
,
d
d
1
+
1
−
1
,
d
d
1
+
2
,
.
.
.
,
d
n
)
sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)
sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化,则将节点
1
1
1与节点
2
∼
d
1
+
1
2\sim d_1+1
2∼d1+1连边,即可得到度数列为
(
d
1
,
d
2
,
.
.
.
,
d
n
)
(d_1,d_2,...,d_n)
(d1,d2,...,dn)的简单图。
必要性:
若
(
d
1
,
d
2
,
.
.
.
,
d
n
)
(d_1,d_2,...,d_n)
(d1,d2,...,dn)可简单图化为图
G
G
G。设
G
−
v
1
G-{v_1}
G−v1的度数列
为
(
d
2
′
,
d
3
′
,
.
.
.
,
d
n
′
)
为(d_2',d_3',...,d_n')
为(d2′,d3′,...,dn′),则:
∀
r
(
2
≤
r
≤
n
)
,
∑
i
=
2
r
d
i
′
≤
(
r
−
1
)
(
r
−
2
)
+
∑
i
=
r
+
1
n
min
{
r
−
1
,
d
i
′
}
\forall r(2\le r\le n),\sum_{i=2}^rd_i'\le (r-1)(r-2)+\sum_{i=r+1}^n\min\{r-1,d_i'\}
∀r(2≤r≤n),∑i=2rdi′≤(r−1)(r−2)+∑i=r+1nmin{r−1,di′}
设
s
o
r
t
e
d
(
d
2
−
1
,
d
3
−
1
,
.
.
.
,
d
d
1
+
1
−
1
,
d
d
1
+
2
,
.
.
.
,
d
n
)
=
(
d
2
′
′
,
d
3
′
′
,
.
.
.
,
d
n
′
′
)
sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)=(d_2'',d_3'',...,d_n'')
sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)=(d2′′,d3′′,...,dn′′)。则:
∀
r
(
2
≤
r
≤
n
)
,
∑
i
=
2
r
d
i
′
′
≤
∑
i
=
2
r
d
i
′
,
∑
i
=
r
+
1
n
d
i
′
′
≥
∑
i
=
r
+
1
n
d
i
′
\forall r(2\le r\le n),\sum_{i=2}^rd_i''\le \sum_{i=2}^rd_i',\sum_{i=r+1}^nd_i''\ge \sum_{i=r+1}^nd_i'
∀r(2≤r≤n),∑i=2rdi′′≤∑i=2rdi′,∑i=r+1ndi′′≥∑i=r+1ndi′
∴
∑
i
=
2
r
d
i
′
′
−
∑
i
=
r
+
1
n
min
{
r
−
1
,
d
i
′
′
}
≤
∑
i
=
2
r
d
i
′
−
∑
i
=
r
+
1
n
min
{
r
−
1
,
d
i
′
}
≤
(
r
−
1
)
(
r
−
2
)
\therefore \sum_{i=2}^rd_i''-\sum_{i=r+1}^n\min\{r-1,d_i''\}\le \sum_{i=2}^rd_i'-\sum_{i=r+1}^n\min\{r-1,d_i'\}\le (r-1)(r-2)
∴∑i=2rdi′′−∑i=r+1nmin{r−1,di′′}≤∑i=2rdi′−∑i=r+1nmin{r−1,di′}≤(r−1)(r−2)
因此
s
o
r
t
e
d
(
d
2
−
1
,
d
3
−
1
,
.
.
.
,
d
d
1
+
1
−
1
,
d
d
1
+
2
,
.
.
.
,
d
n
)
sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)
sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化。
Havel算法
可以通过度数列构造一个简单图
具体做法就是利用推论,每次把点
1
1
1和点
2
∼
d
1
+
1
2\sim d_1+1
2∼d1+1进行连边,然后把序列重新排个序。朴素实现复杂度
O
(
n
2
log
n
)
O(n^2\log n)
O(n2logn)
更多推荐
所有评论(0)