问答题
20人会议,每人至少有10个朋友,能否安排座位使身边的人都是朋友?
【正确答案】
设V为与会20人的集合,{u,v}∈E当且仅当u和v是朋友.因为V中任意两人u和v其度数和deg(u)+deg(v)≥20=|V|=n,故由G是哈密顿图的充分条件知,G=(V,E)中存在哈密顿回路,按此回路安排会员入座可保证身边的人都是朋友.
【答案解析】
提交答案
关闭