几个观念请教
http://ppt.cc/9uZQ
http://ppt.cc/2jHQ
[NCTU 100 19题组(54)]
Problem I 是 constraint TSP
Problem III 是 H.C. (Hamilton Cycle)
题干的叙述是 III reduce到 I , 印象中, 两个问题之间证明reduce关系
需要说明两个问题能再多项式复杂度内的转换下,彼此互相对应
　　G有H.C. 　←→　G'在constraint n(1+e)内有TSP
注: G'是加入题干中D[i,j]修正后的图
不知道我这样解释正确吗 ?
[NCTU 99]
想找反例
解释是因为只增加某根capacity仍无确保多出来的flow可以透过augment path 到达t吗?
[NCTU98]
我自己标了几个比较恶心的复杂度 , 好奇他们之间的比序关系是?
a < e < b < d < c < f
[NCTU 97 4(7)]
查版上之前分享的答案是T , 不过好像争议不多 , 没有太多讨论
WIKI上的weight-balance tree的叙述和题干说明不太类似??
http://en.wikipedia.org/wiki/Weight-balanced_tree
[NCTU 97 6]
版上之前的分享答案是 (c,d)增加到4 , max flow=5
不过我直接把附图当成没有作完的 residual network不用增加(c,d)得到也是5
min cut在(s,a),(s,c),(s,e)
不晓得2,3小题之间是不是我误会了什么主要的概念 ?

99. s->m->t 容量都是1 则不管增加哪条容量 都只能流过1

100 (54) B只要是 n ~ n(1+e)+1 之间的数字都可以因为只是要产生一个gap而已 这是一种reduction的技巧99 反例是个有多个min-cut的graph97 4(7) usually determined <- 这定义得很模糊..

复杂的那题是a>e 喔 e是常数

reduce是这样没错啊 最困难的就是第一步课本上的reduce大多都是性质相近的问题 所以步骤123不难

推一下 我也想知道97 6 23小题 有人会吗？

想问一下reduce为啥要证双向？