早教吧作业答案频道 -->数学-->
设G是一个具有N个结点的简单无向图,N>=3,设G的结点表示N个人,G的边表示他们之间的友好关系,若两个结点被一条边连结,并且仅当对应的人是朋友.a)结点的度数能做怎样的解释.b)G是连通图能
题目详情
设G是一个具有N个结点的简单无向图,N>=3,设G的结点表示N个人,G的边表示他们之间的友好关系,若两个结点被一条边连结,并且仅当对应的人是朋友.
a) 结点的度数能做怎样的解释.
b) G是连通图能做怎样的解释.
c) 假定任意两人合起来认识所留下的N-2个人,证明N个人能站成一排,使得中间每个人两旁站着自己的朋友,而两端的两个人,他们每个人旁边只站着他的一个朋友.
d) 证明对于N>=4,c)中的条件保证N个人能站成一圈,使每一个人的两旁站着自己的朋友
a) 结点的度数能做怎样的解释.
b) G是连通图能做怎样的解释.
c) 假定任意两人合起来认识所留下的N-2个人,证明N个人能站成一排,使得中间每个人两旁站着自己的朋友,而两端的两个人,他们每个人旁边只站着他的一个朋友.
d) 证明对于N>=4,c)中的条件保证N个人能站成一圈,使每一个人的两旁站着自己的朋友
▼优质解答
答案和解析
a)结点的度数表示结点对应的人所认识的朋友的数目.
b)任何的两个人可以通过朋友的一次或多次介绍而相互认识.
c)G=是一个有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个人能站成一圈,使每一个人的两旁站着自己的朋友.
b)任何的两个人可以通过朋友的一次或多次介绍而相互认识.
c)G=是一个有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个人能站成一圈,使每一个人的两旁站着自己的朋友.
看了 设G是一个具有N个结点的简单...的网友还看了以下:
(2013•普陀区一模)设函数f(x)和g(x)都是定义在集合M上的函数,对于任意的x∈M,都有f 2020-06-08 …
请问.有数一到二十七.做成一个魔方.如何将魔上的每条直线上三个数相加的和都是同一个数?可以...请 2020-07-04 …
设f(N)、g(N)是定义在正数集上的正函数.如果存在正的常数C和自然数N0,使得当N≥N0时有f 2020-07-31 …
非空集合G关于运算○满足;1,对于任意a,b∈G,都有a○b∈G;2,存在e∈G,使对一切a∈G都 2020-08-01 …
1已知f(x),g(x)的定义域相同,f(x)是增函数,g(x)是减函数,且g(x)不等于0,则在 2020-08-01 …
1两人轮流报数,报出的数字从1到10任选,每次报数后把所有数一一加起来,谁先报到100谁获胜,请问如 2020-11-17 …
甲,乙两人轮流报数,报出的数从1~10任选,每次报一个数,每次报数后把所有数一一累加起来,谁先得到4 2020-11-17 …
正确反映唯物主义三种基本形态的发展顺序的是()①万物生于水,又复归于水②有力而后有象,有象而后有数③ 2020-12-01 …
正确反映唯物主义三种基本形态的发展顺序的是()①万物生于水,又复归于水②有理而后有象,有象而后有数③ 2020-12-01 …
找出下列各句与“兴尽悲来,识盈虚之有数”一句中“兴”字意义用法相同的一项()A清风徐来,水波不兴(《 2020-12-15 …