0%

离散数学《图论与代数结构》第2周习题

习题一

2.

假设G存在孤立节点,不妨设其编号为n,则1…n-1号点的度数最大为n-2,则m<=(n-1)(n-2)/2,这与m>(n-1)(n-2)/2矛盾,则原命题成立。

6.

证明9个人中如果不存在4人互相认识,则存在3人互相不认识。


反证法。假设不存在4人互相认识,也不存在3人互相不认识(*)。从9人中任选一人,称为A.

Lemma 1:A至少认识5人。

反证法。假设A至少不认识4人,称为BCDE,则BCDE至少两人不认识,设为BC,则ABC互相不认识,与(*)矛盾。

Lemma 2:A至多认识5人。

反证法。假设A至少认识6人,称为BCDEFG。课上已证明:6个人中,如果没有 3 个人互相认识,则至少有 3 个人相互不认识。由(*)知不存在3个人互相不认识,则有3个人互相认识,设为BCD,则ABCD互相认识,与(*)矛盾。

Proof:综上,A认识恰好5个人。对所有人应用以上结论,则每个点度数为5,总度数9×5=45,不是偶数,矛盾。因此原命题成立。

8.

邻接矩阵

0 1 0 1 0 0
0 0 0 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
0 0 1 0 0 0
1 0 1 1 0 0

关联矩阵

1 1 0 -1 0 0 -1 0 0
-1 0 1 0 0 0 0 0 0
0 0 0 1 1 -1 0 -1 0
0 -1 0 0 -1 0 0 0 -1
0 0 -1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 1

边列表

A (1 1 2 3 3 5 6 6 6)

B (2 4 5 1 4 3 1 3 4)

正向表

A (1 3 4 6 6 7 10)

B (2 4 5 1 4 3 1 3 4)

习题二

1.

设k个联通支为。显然在集合大小不变的情况下,每个连通图内部均为完全图时,边数最多。记,则当前边数为。即最大化。假设对某个,则有,即,将点从小集合移至大集合,使总边数增加。因此边数最多的图含有一个大小为的完全图,和个孤立点。经计算,边数最多为.

2.

不妨设G不连通,存在k个联通支,组成k个集合,不妨设1…k号点对应属于。则对于,属于不同集合的两点间有边(无需考虑中相同集合的点之间的边)。因此,1号点和不属于的点都有边,2号点和属于的点都有边,1和2有边,因此联通。

3.

反证法。假设两条不相交道路的点分别依次为a1a2…ak, b1b2…bk(长度为k-1)。由于G联通,不妨ai, bj之间联通,即,存在道路aic1c2…ctbj,其中c1…ct不在{ai}, {bi}中(若c1中含有{ai}中的点ax,则不妨令ai=ax;含有{bi}中的点的情况同理)。则考虑道路a1a2…ai…bj…bk和b1…bj…ai…ak,由于互补性,这两条道路的长度之和一定为2(k-1)+2(t-1),因此存在一条长度大于k-1的道路,矛盾。

4.

在简单图中,若n>=4, m>=2n-3,则G中含有带弦的回路。


Lemma:如果简单图G的一条极长初级道路的一个端点的度数>=3,则G存在带弦回路。

不妨设道路的点依次为a1…ak,其中d(a1)>=3。由最长道路可知,与a1相连的点必须在此道路上。设与a1相连的另外两点为ai, aj (i<j),则a1a2…aja1为一个回路,(a1, ai)为它的弦。证毕。

Proof:数学归纳法。当n = 4时,命题显然成立;假设命题对于n = k时成立,考虑n = k + 1,即考虑对于顶点数是k + 1,边数大于等于2(k + 1) − 3的图G。设Γ是G的一条极长初级道路,v是Γ的一个端点, 如果d(v) ≥ 3,则引理可得G有带弦回路,否则(即d(v) < 3)G − v是有k个顶点, 边数>=2(k + 1) − 3 − 2 = 2k − 3的图,根据归纳假设,G − v含有带弦回路,那么G也必含有带弦回路。

5.

对任意 n 个结点、m 条边的简单图 G,若 G 不含 K3,则且m ⩽ n^2/4 .


考虑G的每一条边(a, b)。由于G不含K3,则(d(a)-1)+(d(b)-1)<=n-2(否则一定存在含a, b的三元环),故d(a)+d(b)<=n。对所有边应用此结论并求和,得到

由Cauchy不等式,

即,