助教您好...
P6-42範例四
這題的d小題
我不太了解解答的意思....
我要怎麼去想呢?
想請問的是 為什麼證明中間的部份
欲證{ a,v(i-1) }不為H之邊
為什麼突然要證這個呢?
因為這個定理老師上課略過了，自己看看得霧煞煞...我不太清楚這是用什麼樣的方式去證
不過順便問一下這個重要嗎XD
P6-63範例三
這題的題意我看不懂...可以麻煩助教解釋題目的意思嗎@@
P6-66範例7
這題是在問說13天內安排13個考試使得相同教授的考試不會連續嗎?
解答是讓13個考試為頂點，不同教授就連邊
若可形成Hamiltonian path(HP) 則得證
不過解答後面說，一條HP相當於一個指定instructor到13個考試的方式
我不太懂這個說法...這是什麼意思呢?
P6-68範例9
這題只是單純想問...題目說Hamiltonian還有Eulerian但是沒有說是path還是cycle...
那我要寫哪一種呢?
兩種都寫嗎?
最後想請問一點排列組合的觀念問題...
排列組合算到後面自己都被自己搞混了= ="
想請問的是函數對應 定義域m個→對應域n個
1-1對應時
是討論左邊1號點可以對到右邊n個點
然後2號點可以對到右點n-1...以此類推
我想請問的是為什麼是直接討論1號點、2號點...
如果不是用一個一個點討論的
那是要用C(m,1)去取左邊某個點然後可對應到右邊n個點
再來C(m-1,1)再對應右邊n-1個點
可是這樣子答案就不對了說...
這樣想法錯在哪裡呢?
5 則留言:
不好意思，助教我找不到地方貼。
我有補黃子嘉老師的課。
想請問該怎麼發文呢？
我的問題 p6-23
範例2:老師的解答分成兩種情況討論
，但事實上我想了很久發覺還有其他種情況，沒討論到。
例如 假設G中有一點具degree不為0 & n-1
這個情況沒討論到。
感謝
1. P6-42範例四: 先考慮 G 中一個點 v, 假設它有兩個neighbor u1,u2, 那麼這個 v 會貢獻有 deg(v)^2=4 這麼多條在 G 中走兩步且中途經過 v 的走法, 包括 u1-v-u1, u1-v-u2, u2-v-u1, u2-v-u2, 所以在考慮過所有的點當中點的情況後, 這些加總起來的deg平方和就會等於 A^2 的每一項相加
2. P6-58定理10: 證那個是為了要推導出 deg_H(a)+deg_H(b)<n 這個結果來矛盾已知
至於這個定理重不重要嘛...第五版書上有加註這是98長庚資管的考題, 另外, 台大資工今年也有考 (他問的是四版同頁下方的那個推廣5), 雖然題目有給證明的過程所以考法比較單純, 沒看過應該也會寫, 但他請你解釋的部分剛好就是你問的這一段, 所以我覺得這部分你可能要稍微留意一下
3. P6-63範例三: 題目是說, 只要走過一個move, 不用考慮是由哪個方向經過的, 那個move就算完成了, 請問......, 我覺得你不懂的可能是knight的移動方式, 在西洋棋中, 騎士的走法就像是象棋中的馬, 這樣你在回去看書上的那個degree表應該就會懂了
4. P6-66範例7: 意思就是說只要找到一個HP, 則該HP所對應的就會是一個合法安排考試的方法, 因為假設找到的Hamiltonian path為 v_1-v_2-...-v_n, 那麼我們只要在第 i 天安排 v_i 這一科, i=1,...,n, 根據該圖的建構方法, 因為 (v_i,v_(i+1))∈E, 所以 v_i 與 v_(i+1) 必定是不同教授所開授的課
5. P6-68範例9: 寫 cycle, 一般 Hamiltonican graph 指的就是具 H.C. 的 graph, Eulerian graph 就是具有 Euler circuit 的 graph
6. 關於排列組合的問題: 因為定義域裡的每個點都要對出去, 如果把定義域裡的東西想成是球, 要把 m 個相異球放進 n 個箱子裡, 其中每個箱子最多只能裝一顆球, 那我們就把球一個一個的拿來放來討論可能的放法就好了; 你的想法問題出在會有重複, 譬如說假設 A={1,2}, B={a,b}, 算 f:A->B 為 1-1 的個數, 當你在算 c(2,1)*2*c(1,1)*1 時, 以下這些狀況你都有考慮到:
(1) f(1)=a 且 f(2)=b
(2) f(1)=b 且 f(2)=a
(3) f(2)=a 且 f(1)=b
(4) f(2)=b 且 f(1)=a
但(1)和(4)還有(2)和(3)其實都是同一個函數
To Jeremy:
你要通過身分認證才可以在首頁的右上角看到發新文章的按鈕, 認證的方式請點選網頁右邊的"公告"進去看最下面的那一篇文章
關於你問的那一題, 的確像你說的, 那兩個case並不包含所有的狀況, 這裡可分成 (1) G為connected 和 (2)G為disconnected 這兩種case來討論, 寫法和書上的差不多, 你可以自己練習看看
謝謝助教的解答
不過我對P6-58定理10還有些問題...
欲證{ a,v(i-1) }不為H之邊
抱歉沒有把問題描述清楚..冏
我應該說我從
欲證{ a,v(i-1) }不為H之邊
這邊開始看不太懂....
這邊是用什麼想法下去証呢?
是利用若不加{a,b}之邊
不會有Hamilton cycle證明了不會有b-v3-...-vn-a-v(i-1)-...-v3-b之情況嗎?
然後接著下面我看證明的想法是..
因為H是Kn之子圖
所以每個點的degree<=n-1
又i=4,..,n
(因為我想說如果i=3那變成a=v1連到b=v2了)
接著..
deg_H(a)+deg_H(b)<=2n-1-(n-3)=n+1
可是這樣沒有<n
這樣錯在哪裡呢?
是我想錯方向了嗎...
還有一點是...證明上面是證{b,vi}和{a,vi-1}
{a,vi-1}這個邊是不是不一定要是i-1?
像是i-2,..,v3可以嗎?
非常謝謝助教
你可以畫個 v1-v2-...-vn 的圖出來想看看
1. 欲證{a,v_(i-1)}不為H之邊那裡的想法是, 如果在那一條 HC 中有一個點與 b 相連且他的前一點與 a 也相連, 這樣會導致我們在不經由 (a,b) 的情況下亦可走出一 HC, 而矛盾了我們原本假設 H 不為Hamiltonian
2. 你有點想得太複雜了, 因為 b 與 deg_H(b) 的點相鄰, 則由上面欲證的結論, 因為 a 與那deg_H(b) 個點的前一個點都必不相鄰, 所以與 a 相鄰的點數不會超過 n-deg_H(b) 的, 且因為(a,b)不為H知邊, 所以要再扣掉1個, i.e., deg_H(a)≦n-deg_H(b)-1, 則 deg_H(a)+deg_H(b) ≦ (n-deg_H(b)-1)+deg_H(b) = n-1
3. 應該是不太能隨便取一個 v_(i-k) 來證, 如果你有看懂欲證的那一段, 應該就會知道為什麼了, 把圖畫出來繞繞看你就會發現如果不取 v_(i-1) 就很難繞出一個新的 HC, 因為假設你取 v_(i-k), 在原本繞法中的 v_(i-k+1),...,v_(i-1) 這些點可能會繞不到, 這樣子原本的想法會證不下去
張貼留言