|
离散数学期末考试要考握手定理，复习一下。 定理1 无向图
G
=
<
V
,
E
>
G=
G= 是
(
p
,
q
)
(p,q)
(p,q)图(
∣
V
∣
=
p
,
∣
E
∣
=
q
|V|=p,|E|=q
∣V∣=p,∣E∣=q)，则
∑
v
∈
V
d
G
(
v
)
=
2
q
\sum_{v\in{V}}d_{G}(v)=2q
∑v∈VdG(v)=2q. 证明很简单，一条边会产生两个度，进行q次除边操作，剩下p个零图时，可计算得总度数是边数的两倍。 定义1 度为奇数的结点是奇结点，度为偶数的结点是偶结点。 引理1 任何图都有偶数个奇结点。 例1 一次集会中，相互认识的人会彼此握手，试证明与奇数个人握手的人数是偶数。 证明： 每个人看成是一个结点，两个人之间如果握手则存在一条边，否则无边。则可以对问题建立图模型，由引理1，得证。 扩展：自然数集有限子集上与奇数个数互素的数字个数必为偶数。 例2 每个碳氢化合物的分子所含氢原子数必然是偶数。 证明： H在碳氢化合物中一定是+1价。建立图模型：每个原子是一个结点，价数决定了某原子与其他原子之间的化学键数，看作是边数（度数）。则由引理1，问题得证。 例3 搬砖问题。 n个码农搬k块砖，其中
k
%
2
=
=
0
k\%2==0
k%2==0.每人自愿搬一定数目的砖，但是最终要搬完所有的砖（抱一个大腿就可以摸鱼了 ).求证：搬奇数块砖的码农必有偶数个。 证明：
n
个
码
农
为
v
1
,
v
2
,
.
.
.
.
.
.
,
v
n
,
记
v
0
是
那
k
块
砖
。
n个码农为v_1,v_2,......,v_n,记v_0是那k块砖。
n个码农为v1,v2,......,vn,记v0是那k块砖。
v
i
搬
了
m
块
砖
，
则
在
v
0
与
v
i
之
间
连
接
m
条
边
。
v_i搬了m块砖，则在v_0与v_i之间连接m条边。
vi搬了m块砖，则在v0与vi之间连接m条边。 已知
d
e
g
(
v
0
)
=
k
deg(v_0)=k
deg(v0)=k是偶数，则根据定理1,
∑
v
i
d
e
g
(
v
i
)
+
k
=
2
×
∑
v
i
m
i
\sum_{v_i}{deg(v_i)}+k=2\times{\sum_{v_i}{m_i}}
∑videg(vi)+k=2×∑vimi 按照度数奇偶划分码农为奇偶码农，显然奇码农应该有偶数个。因为度数之和应该为偶数，而奇结点的度数已经是奇数了，那么奇结点的个数必然是偶数。得证。 例4（原题是清华大学的运筹学教材中，《图论》这一章习题的第2题）整理自某帖子[1] 已知9个人中v1和两人握过手，v2,v3各和4个人握过手，v4,v5,v6,v7各和5个人握过手，v8,v9各和6个人握过手，证明：这9个人中一定可以找出3个人互相握过手。 证明： 即证，这个图中一定有子图是
K
3
K_3
K3(三角形). 根据题目条件，可以计算图的边数为
1
×
2
+
2
×
4
+
4
×
5
+
2
×
6
2
=
21
\frac{1\times2+2\times{4}+4\times{5}+2\times{6}}{2}=21
21×2+2×4+4×5+2×6=21 而
K
9
K_9
K9应该有36条边。
v
9
v_9
v9只与六个人握手，除去自己，最多会与8个人握手，因此，在
K
9
K_9
K9中减去与
v
9
v_9
v9关联的两条边。则总边数剩下34条。不妨记
v
i
,
i
=
1
,
2
,
.
.
.
,
6
v_i,i=1,2,...,6
vi,i=1,2,...,6与
v
9
v_9
v9握手。 关注
v
9
,
v
1
,
v
2
,
.
.
.
,
v
6
v_9,v_1,v_2,...,v_6
v9,v1,v2,...,v6.假设他们中不存在
K
3
K_3
K3子图。而
v
9
v_9
v9与
v
i
v_i
vi中已经存在一条边，则
v
i
v_i
vi之间必然不会有边，否则会构成
K
3
K_3
K3。则需要再减去
C
6
2
=
15
C_6^2=15
C62=15条边，剩下19条边，19 |