1. (清大)問在求解flow network時,是可以直接隨便找一條p可以重s到t嗎??
還是無向圖示ok的,但有向圖有差?
(我貼便利貼是因為我先走紅色的p,再走紫色的p,就沒辦法讓流量到最大10了)
2.(元智)問b小題他應該是ture吧??要不然他正解是?
,
3.(清大)d小題,有點看不懂再問甚麼,
是在問在一spanning tree中,任一cut set不會有相同的邊
那 cut set不是求minimal嗎,那又在tree中每一邊都為bridge,
所以每一cut set都為一邊,那不就都不相同的邊??
4.(元智)b小題,雖然好像握得很明顯,答案是錯的吧??
2 則留言:
1. 要從上面走下來也OK, 不過您畫的圖還有三條沒走完, 一條a->d->c->e->z, 流量可加1, 另外一條a->d->c->b->e->z, 流量可加1, 第一條為a->d->f<-c->b->e->z, 這一條有一個邊是逆流, 整體流量可再加1, 就會達到network flow = 10
就如上課提的, 要檢查是否真的走完, 嚐試找minimum cut, 如果找不到minimum cut滿足順向全滿逆向全空, 那就是還沒走完
2. n^2[log^2(n+1)]!=n^2[log(n+1)^2]
所以log裡面的平方不可以提出來變成係數2倍
3. 上課筆記有提過, cut-set與spanning tree必含至少一個共同邊, cut-set指的是原來圖的cut-set, 不是spanning tree的cut-set, 所以不會只含一個邊, 另外, 這邊的cut-set定義不需要minimal
4. 答案應該如您寫的那個
1.沒考慮到逆流,也沒有檢查"順向全滿逆向全空"
2.很糟糕的粗心
3.回想起ETC的故事
非常感謝老師 :D
張貼留言