【正确答案】：以图来表示题目中所给的情况,设顶点集V={v1, v 2,…, v20},每人都至少有10个朋友,即V中每个顶点的度≥10。在图中找一条哈密顿回路即可满足题目要求。
使用定理来判定:G的顶点数为n, G中每对顶点度数之和大于等于n-1。
对于图G=
∀u,v∈V,deg(u)+deg(v)≥20> n-1。故图中存在一条哈密顿回路,即能找到座次安排。
某次会议有20人参加,其中每人都至少有10个朋友,这20人围一圆桌入座,要想使相邻的两位都是朋友,是否可能?
- 2024-08-04 00:07:38
- 离散数学(02324)
- 1
某次会议有20人参加,其中每人都至少有10个朋友,这20人围一圆桌入座,要想使相邻的两位都是朋友,是否可能?
【正确答案】：以图来表示题目中所给的情况,设顶点集V={v1, v 2,…, v20},每人都至少有10个朋友,即V中每个顶点的度≥10。在图中找一条哈密顿回路即可满足题目要求。
使用定理来判定:G的顶点数为n, G中每对顶点度数之和大于等于n-1。
对于图G= ,V={v1,v2,…,v20},deg(vi)≥10 (i=1,2,…,20)。
∀u,v∈V,deg(u)+deg(v)≥20> n-1。故图中存在一条哈密顿回路,即能找到座次安排。
【正确答案】：以图来表示题目中所给的情况,设顶点集V={v1, v 2,…, v20},每人都至少有10个朋友,即V中每个顶点的度≥10。在图中找一条哈密顿回路即可满足题目要求。
使用定理来判定:G的顶点数为n, G中每对顶点度数之和大于等于n-1。
对于图G=
∀u,v∈V,deg(u)+deg(v)≥20> n-1。故图中存在一条哈密顿回路,即能找到座次安排。