《离散数学》题库及答案

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个顶点中任何一

>>展开全文<<
12@gma联系客服:779662525#qq.com(#替换为@)