作者nayd (Mr.洋芋片)
站内Prob_Solve
标题Re: [问题] approximation
时间Mon May 21 03:21:11 2012
我假设每个点有编号 所以不会重覆选同个点
则此演算法为：
let N = # of edges at the cut
for all v in S
check all edges of v, say (u,v)
let n(S) be # of such u in S.
n(T) T
if n(T) > n(S), then add v to S, N = N - n(T) + n(S)
此演算法的问题在於，不同的点的顺序，会造成不同的结果
也就是题目所说的 hill-climbing
(6) V个点都看过之後 这个过程里 每个edge恰好被看过2次
因此复杂度为O(|E|)
(7) max deg(v) / 2 (考虑一个tree)
(8) 最倒楣的顺序为：每次都选到不同side的点
那麽 cut 上的 edge 数会是
2n + (2n-1) + (2n-1) + 2n + 2n + ... + (n+1) + (n+1)
= 2n + (3n-2)*(n+1)
※ 引述《DJWS (...)》之铭言：
: ※ 引述《wsx02 ()》之铭言：
: : http://ppt.cc/_7PH
: : 这是交大研究所的考题 不是作业0.0
: : 这题我找了一些答案
: : 想跟大大确认一下答案
: : (6) O(|E| * (|E|+|V|)) 或
: : O(|V| * (|E|+|V|))
: : 不知道哪个是正确的..
: 照字面看 每次V点可选，运气不好又重复选 O(无限大)
: 最普通的 每次V点可选，检查边需要E，总共要选V点 O(VVE)
: 强一点的 选过的点永不再选，检查边需要E，总共要选V点 O(VE)
: 最强的 如果一开始先把两点之间多重的edge拼起来 O(VV)
: 不知道考官喜欢哪一种......
: : (7) 1/2 或
: : |E|/2
: : 不知道应该填哪一个
: E
: 运气好的时候可以找到正解
: 运气好是什麽时候呢？ 正解最大会是多少呢？
: 例如下面那题的完全二分图 :p
: : (8) 找到的是2n^2 可是不是很确定
: : 谢谢
: 完全二分图(X,Y)一定可以找到正解
: 抓一个点过去 ---> a. 与X同侧: 边数为零，不会增加边，所以最後啥都没做
: b. 与Y同侧: 因为是完全图，一定会增加边
: 所以答案就是 K(2n, 2n) 的边数 2n * 2n = 4nn
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 76.100.250.242
※ 编辑: nayd 来自: 76.100.250.242 (05/21 03:21)
1F：推 wsx02:请问(6) 每个V被看过不是就花O(V) 每edge看两次不是O(V*2E)? 05/21 23:32
2F：→ nayd:楼上的情况是对於每个点 去看所有的edge 06/09 10:32
3F：→ nayd:每个edge会被重覆看|V|次 所以不是这样的 06/09 10:34
4F：→ nayd:应该是 每个v 去看跟它相邻的v 所以顶多O(V^2) 06/09 10:37
5F：→ nayd:仔细算的话只有O(|E|) 这个小於O(|V|^2)所以比较tight 06/09 10:39