Question

求解一道离散数学题 慷慨悬赏~~~

设G是一个具有N个结点的简单无向图，N>=3，设G的结点表示N个人，G的边表示他们之间的友好关系，若两个结点被一条边连结，并且仅当对应的人是朋友。
a) 结点的度数能做怎样的解释。
b) G是连通图能做怎样的解释。
c) 假定任意两人合起来认识所留下的N-2个人，证明N个人能站成一排，使得中间每个人两旁站着自己的朋友，而两端的两个人，他们每个人旁边只站着他的一个朋友。
d) 证明对于N>=4,c)中的条件保证N个人能站成一圈，使每一个人的两旁站着自己的朋友

答案详细的朋友会追加悬赏~ 希望大家踊跃帮我解答 谢谢

Answer 1

a)结点的度数表示结点对应的人所认识的朋友的数目。

b)任何的两个人可以通过朋友的一次或多次介绍而相互认识。

c)G=<V,E>是一个有n(≥3)个结点的简单无向图，每一个结点表示一个人，两个结点相邻当且仅当对应的人是朋友。若任意两个人合起来认识剩下的n-2个人，表示对图G中任意两个结点u,v,有deg(u)+deg(v)≥n-2，且余下的n-2个结点必与u或v邻接。证明在这种条件下必有deg(u)+deg(v)≥n-1。

（1）若u与v邻接，则deg(u)+deg(v)≥2+n-2=n>n-1。

（2）若u与v不邻接，如果deg(u)+deg(v)≥n-2，而V-{u,v}中恰有n-2个结点(n-3,故V-{u,v}≠{φ}，其中每一个结点只能与u,v中的一个结点相邻，设w与u相邻，w与v不相邻。此时对于结点u,w来说，都不与v相邻，这与假设矛盾。所以对于任意u,v必有deg(u)+deg(v)>n-2，即deg(u)+deg(v)≥n-1，故图G存在一条汉密尔顿路，于是n个人能站成一排，使得中间每个人两旁站者自己的朋友，而两端的两个人，他们每个人旁边站者他的一个朋友。

d)由c)可知任一对结点u,v有deg(u)+deg(v)≥n-1,证明当n≥4时,有deg(u)+deg(v)≥n.当u和v相邻,有deg(u)+deg(v)≥n,当u和v不相邻,有deg(u)+deg(v)≥n-1,因为n≥4,在结点集V-{u,v}中至少有2个结点z和w,其中z和结点u和v相邻,而w只和u,v中1个相邻,假如和u相邻,此时结点u,w与结点v都不相邻,这与假设矛盾...所以任何结点u,v必有deg(u)+deg(v)≥n,故G存在1条汉密尔顿回路,所以,n个人能站成一圈，使每一个人的两旁站着自己的朋友.