《离散数学》题库及答案

m=n+k-2 及

3k?n+k-2 2故 k?2n-4。

98、证明对于连通无向简单平面图,当边数e<30时,必存在度数≤4的顶点。 证明:

若结点个数小于等于3时,结论显然成立。 当结点多于3 个时,用反证法证明。 记|V|=n,|E|=m,|F|=k。

假设图中所有结点的度数都大于等于5。 由欧拉握手定理得

?v?Vdeg(v)=2|E|得 5n?2m。

又因为G=〈V,E,F〉是一个连通简单无向平面图,

所以对每个面f,deg(f)?3。 由公式

?deg(f)=2|E|可得,2m

?3k。

221m-m+m=m 5315f?F再由欧拉公式|V|-|E|+|F|=2可得2?从而30?m,这与已知矛盾。

99、在一个连通简单无向平面图G=〈V,E,F〉中若|V|?3,则 |E|?3|V|-6。 证明:

? |V|?3,且G=〈V,E,F〉是一个连通简单无向平面图,

?

由公式

d(f) ?3,?f?F。

?deg (f)=2|E|可得,2|E|

?3|F|。

2|E|?2。 3f?F再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+

?|E|?3|V|-6。

100、给定连通简单平面图G=,且|V|=6, |E|=12, 则对于任意f?F, d(f)=3。 证明:

因为|V|=6?3,且G=〈V,E,F〉是一个连通简单无向平面图, 所以对任一f?F,deg(f)?3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式

?deg(f)=2|E|,

f?F?deg(f)=24。

f?F因为对任一f?F,deg(f)?3,故要使上述等式成立, 对任一f?F,deg(f)=3。

101、设G=是n个顶点的无向图(n>2),若对任意u,v?V,有d(u)+d(v)?n,则G是连通图。 证明:

用反证法证明。

41

若G 不连通,则它可分成两个独立的子图G1和G2,其中|V(G1)|+|V(G2)|-2=n ,且G1中的任一个顶点至多只和G1中的顶点邻接,而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则 d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。

故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2 =n-2

102、一次会议有20人参加,其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友?为什么? 证明:

可以。

将每个人对应成相应的顶点,若两人是朋友,则对应的两个顶点间连上一条无向边,作出一个简单无向图。由已知,图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20,即顶点数。故这个图是一个哈密尔顿图,从而存在哈密尔顿回路。任取一条哈密尔顿回路,按回路经过的顶点的次序安排对应的人的座位,就可满足要求。

103、证明在任何两个或两个以上人的组内,存在两个人在组内有相同个数的朋友。 证明:

将每个人对应成相应的顶点,若两人是朋友,则对应的两个顶点间连上一条无向边,作出一个简单无向图。则原命题相当于在该无向图中一定存在两个顶点的度数相等。

设该简单无向图中有n个顶点,则图中n个顶点的度数只能为0,1,2,?,n-1。若图中有两个或两个以上的顶点度数为0,则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相等。

设该简单无向图中n个顶点中任何一对顶点的度数都不相等,即这n个顶点的度数两两不同。但每个顶点的度数只能是1,2,?,n-1这n-1个数中的某一种,这显然产生了矛盾。

因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内,存在两个人在组内有相同个数的朋友。 104、设有如下有向图G=

(1)求G的邻接矩阵;(2)G中v1到v4的长度为4 的通路有多少条?(3)G中经过v1的长度为3 的回路有多少条?(4)G中长度不超过4 的通路有多少条?其中有多少条通路? 解:

(1)

?1?1A=??0??0110??2?1010??,A=??0001???010??0?324?213A=??000??0012

3121?111?? 010??001?2??53?321??,A=??001???0??004

74?43?? 10??01?(2)

G中v1到v4的长度为4 的通路有4条;

42

(3) G中经过v1的长度为3 的回路有3条;

(4) G中长度不超过4 的通路有72条,其中有19条回路。

?v ?v 14

? v2 ?v3

105、求下列无向图中每个顶点的度数;求下列有向图中每个顶点的出度、入度和度。 解:

a?

?b ?f

在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。

c b

a 在这个有向图中d(a)=3,d(b)=4, d(c)=3, d(a)=2, d(a)=1, d(b)=2 , d(b)=2,d(c)=1, d(a)=2。 a?

???????d ?e

?c ?d ?e

?c ?b ?f

106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。

解: c b

它的一个子图

d a

e

43

c

b f

它的一个生成子图

d a

c b

由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图 d a

b f

由顶点集{a,b,d,f}诱导出的子图 107、求下列赋权图顶点间的距离。

? d ? a

e ? 4 3 5 7 1 c? b ? 14 ?f 解:

d(a,b)=3, d(a,c)=3, d(a,d)=?, d(a,e)=8, d(a,f)=16,

d(b,c)=1, d(b,d)=?, d(b,e)=6, d(b,f)=13, d(c,d)=?, d(c,e)=5, d(c,f)=12, d(d,e)=?, d(d,f)=?, d(e,f)=7,

108、求下列赋权图中v1到其他顶点的距离。

v2 10 v4 3 v1 2 2 6 4 3 4 v6 v3 2 v5

44

联系客服:779662525#qq.com(#替换为@)