Re: [問題] 不能跟一樣的人坐在一起的問題
看板Prob_Solve (計算數學 Problem Solving)作者KOFXI時間10年前 (2014/02/16 23:34)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《entryword (chiahua)》之銘言：
: 題目大意是
: 有19個學生參加夏令營
: 每天晚上圍著圓桌吃飯
: 而每天必須跟不一樣的人坐在隔壁
: 請問根據這種座位方法
: 可以吃幾天的飯
: 我以為是排列組合的問題
: 但問同學他說是complete graph K19的問題
: 有人可以指點一下嗎?
: 感激不盡
你問的是今年台科大資工所的題目吧
第一小題因為一個 Kn 裡面包含 (n-1)/2 個互斥的漢米爾頓 cycle
所以第二小題把19個人想成點 他們晚上座位相鄰想成邊
因為是環狀所以從第一個人連回自己會形成一個 漢米爾頓 cycle
又因為每晚要不一樣 所以就是算互斥的漢米爾頓 cycle有幾個
(19-1)/2 = 9 所以是9天
憑印象打的 不是很確定 再有煩其他大大幫忙回大~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.94.193
推
02/28 23:13, , 1F
02/28 23:13, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
