[理工] 離散 88清大圖論問題

作者: ss455032 (ss455032)   2017-08-25 12:12:28
http://i.imgur.com/vPrj3bj.jpg
想問這題畫紅線的地方
問題1.
題目不是說安排13個不同考試在十三天內在連續天中,兩個考試不能給相同的instructor

而為什麼是說在問兩個考試給不同的instructor 對應兩點有邊相連,而且是問存在HP
不太理解
2.
13個考試至多出現7個是由A處理,所以6個考試不由A.
為什麼這些考試會跟v相連?,deg(v)>=6但是它不是不能超過7。應該deg(v)只能6或7吧?
謝謝大大
作者: nat99up (NAt)   2017-08-25 13:07:00
1.每個點都是一個考試,而邊的實際意義就是這兩個考試可以排在鄰近兩天考(不同教授)用這種方式把圖畫完如果有一條HP代表這條長度12的路徑排程是不會有教授連續兩天監考2.這是HP的充要條件
作者: ss455032 (ss455032)   2017-08-25 21:05:00
瞭解,謝謝大大

Links booklink

Contact Us: admin [ a t ] ucptt.com