助教你好
題目一圖片
請教一下a小題這證明的想法
目前可以理解
加入一點連到其他所有點
會造成所有點的degree+1
但是要怎麼證明到 ( d1 , d2 , ... dn ) 的圖形存在
就沒辦法理解怎麼證了
題目二圖片
也是想請教這題的證明的想法
參考答案是以HamiltonianPath下去證
但是實在想不到這與原題意的關聯
懇請助教or知道做法的同學開示
感激不盡~
Research Space for Linear Algebra & Discrete Mathematics
1 則留言:
1. (6-38) 可參考下面這篇:
http://zjhwang.blogspot.com/2010/02/blog-post_9769.html
建議先看我在2/2下午5:38回的那個例子 (裡面要勘誤一下: 倒數第三句的"將邊集去掉(v1,vj)以及(vi,vj)", 應改成"將邊集去掉(v1,vj)以及(vi,vk)"), 再回去看我的第一個回覆或是書上的解答, 這樣應該會比較容易懂
2. (6-66) 在棋盤中若可走一條長度為偶數的path, 則在這條path上必可合法放置2x1的dominoes, 這個應該還算好想像吧? 就從path的起點開始擺dominoes, 該轉彎時就轉彎
那麼現在考慮書上畫的那個cycle, 因為在cycle中要去掉一黑一白, 必定會將cycle分隔成兩條長度都是偶數的disjoint paths, 所以仿照上述的方法, 必可將這兩條path都擺滿2x1的dominoes
張貼留言