看到一題:
1.how many paths length 4 are there in K7?
這題的path應該是指5個點的path吧?
假設考試時,忘了是哪種定義,可以自己假設lenght長度為4
是4個點的path嗎?
也就是在不確定的題目裡面,可以自己假設嗎......
2.還有,題目問求 largest value entries in matrix A是指在A的第一行裡面最大的元素
還是指A矩陣所有元素裡面最大的?
3.what formulas will make the nonlinear transformation into matrix transformation?
4.in what situation will you use compute a least square solution through a QR factorization?
5.請問min cut的定義是? 在做 flow network時,有時候不大確定要怎麼切....
麻煩解答了 感謝
5 則留言:
1. 沒辦法的時候也只好這樣囉, 但length一般都是指邊數, 你可以把它想成是你走的路的長度, 走一步兩步...的距離, 一個點因為是沒有長度的, 所以如果你的假設讓老師覺得差太多, 他大概也很難給你對
2. A矩陣所有元素裡面取最大的
3. 我覺得這樣問似乎有些籠統, 這裡的nonlinear有什麼限制嗎? 對某些nonlinear的transformation, 有個方法是對每個向量再加一個維度, 然後同樣對matrix做增廣
4. 這應該是和數值分析有關, 因為解normal equation會比較不穩定, 也就是說有些矩陣會使得我們在解least square sol時會得到很大的誤差, 而用QR來解比較不會有這樣的問題
5. 就是具有最小capacity的cut, cut和capacity的定義在p8-24, 大略的說就是你的cut會把原來的network切成分別包含有起終點的兩個sides, 則將所有跨越這兩個sides的edge的weight全部加起來就是這個cut的capacity
謝謝回答~
另外弱弱請問一下,min cut是不是會切在
flow滿的或是空的edge上?還是不一定?
還有再問一下
K6裡最長的trail和最長的circuit要怎麼去想呢?
感謝~
我想cut set是定義是爆掉水管的部份(滿)
水管沒爆掉不就可以繼續流了
這樣就沒有切集了阿
1. 你要問的是最長trail和circuite的長度嗎? 如果是的話, 最長的trail應該是有13個邊, 最長circuit則是具12的邊, 我的想法是將最長的trail視為是一個K6中具有Euler trail的subgraph, circuit同理
(1) 將K6中去掉三個不含共同點的邊, 這個subgraph有12個邊且具有Euler circuit, 因為這個subgraph已為最大具有Euler circuit的subgraph, 所以可得K6之最長circuit具有12個邊
(2) 另外對再對(1)的那個圖再加上一個之前被去掉的邊, 所形成之新的具有13個邊且具Euler trail的subgraph, 且一樣不可能再有比他更大具有Euler trail的subgraph了
2. labeling procedure做到最後min cut就是切在順向的邊(a->z)要是滿, 而逆向(z->a)要是空的edge上
張貼留言