1. Two ingredients of Graph:
a) vertices A.K.A. nodes (V)
b) edges = pairs of vertices (E)
can be undirected or directed A.K.A arcs
2. Definition of Cuts of Graphs:
A cut of Graph ( V, E) is a partition of V into two non-empty sets A and B.
The crossing edges of a cut (A, B) are those edges with:
a) one endpoint in each of (A, B) for undirected graph
b) tail in A, head in B for directed graph
3. Definition of the Minimum Cut Problem:
Input : an undirected graph G = (V, E) , parallel edges (multiple edges for the same node pair are allowed
Output : a cut with fewest number of crossing edges.
4. Applications for Min-Cut problem:
a) Identify network bottlenecks / weaknesses
b) Community detection in social networks
c) Image segmentation
5. Let n = # of vertices and m = # of edges.
In most applications, m is Ω(n) and O(n^2).
-- in a "Sparse Graph", m is O(n) or close to it.
-- in a "Dense Graph", m is Θ(n^2) or close to it.
6. The Ajacency Matrix :
Represent G by a nXn 0-1 matrix A, where Aij = 1 <==> G has an i-j edge
Variants:
a) Aij = # of i-j edges (if parallel edges allowed)
b) Aij = weight of i-j edge ( if any)
c) Aij = +1, if i --> j ; -1 if j --> i ;
Takes Θ(n^2) spaces.
7. The Ajacency Lists:
a) array ( or list ) of vertices
b) array ( or list ) of edges
c) each edge points to its endpoints
d) each vertex points to edges incident on it
Takes Θ(n+m) = Θ (max{n, m}) spaces.
8. Random Contraction Algorithm:
While there are more than 2 vertices :
a) pick a remaining edge (u, v) uniformly at random
b) merge ( or contract ) u and v into a single vertex
c) remove self-loops
Return cut represented by final 2 vertices.
9. Fix a graph G = (V, E) with n vertices , m edges.
Fix a minimum cut (A,B), ( there can be multiple minum cuts, here we fix the specific one)
Let k = # of edges crossing (A, B)
Let F = crossing edges of cut (A, B)
a) Suppose an edge of F is contracted at some point => algorithm will not output (A, B)
b) Suppose only edges inside A or inside B get contracted => algorithm will output (A, B)
So, P[ output is (A, B) ] = P[ never contracts an edge of F]
Let Si = event that an edge of F contracted in iteration i.
Goal : compute P[ !S1 and !S2 and ...and !Sn-2]
degree ( # of incident edges ) of each vertex is at least k. (otherwise # of crosing edges of min-cut <k)
Sum {degree(v) } = 2m >= kn , m >= kn/2
So for the first iteration, P[S1] = k/m <= 2/n. P[!S1] >= 1-2/n
P[!S1 and !S2] = P[!S1] P[!S2 | !S1] >= (1-2/n) ( 1- k/ # of remaining edges)
In the second iterfation, still degree(v) >= k , so Sum{degree(v)} = 2 * # remaining edges >= 2 (n-1)
So P[!S1 and !S2] >= (1-2/n) * (1- 2/(n-1) );
So P[ never contracts an edge of F]>= ( 1- 2/n ) * ( 1- 2/(n-1) ) * ... * ( 1- 2/(n-(n-3) ) ) (total n-2 iteration)
= (n-2)/n * (n-3)/(n-1) * (n-4) /(n-2) * ... * 2/4 * 1/3
= 2/(n * (n-1) ) >= 2/n^2
10. Run the random contraction algorithm a large number N times. Let Ti = event that the Min-Cut (A, B) is found on the ith try. By definition different Ti are independent.
So P[ all N trials failed] = P [ !T1 and !T2 and ... !TN] = P[!T1] * P[!T2] * ... * P[!TN] <= (1-1/n^2)^N
Since, for any real number x, 1+x <= e^x
let N= n^2 , P[ all N trails failed] <= e^(-N* 1/n^2) = 1/e
let N = n^2* lnn , P[ all N trails failed] <= 1/n
Each contraction algorithm takes O(m) (need to check each edges) and at most n^2 or n^2 * lnn times.
11. A tree with n vertices has n-1 min cuts.
12. What's the largest number of min cuts that a graph with n vertices can have?
Lower bound : n verices that forms a cycle. Each pair of the n edges defines a distinct min cut ( with two crossing edges) . so it has n * (n-1) / 2 min cuts.
Upper bound : Let (A1, B1) , (A2, B2), ... (At, Bt) be the min cuts of a Graph with n vertices. By random contraction algorithm, we know that P[ output = (Ai, Bi) ] >= 2/(n (n-1) ).
So Sum(i = 1, 2, ..., t) { P[output = (Ai, Bi)] } >= 2t/( n(n-1) ) <= 1 , so t <= n(n-1) /2
相关推荐
Computer global min-cut in a graph. Implements random contraction algorithm. Need to be run multiple time for better solutions.
The original CH algorithm was introduced in: * Exact Routing in Large Road Networks Using Contraction Hierarchies. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. ...
这种节点顺序被用于改进双向迪杰斯特拉算法(bidirectional Dijkstra algorithm),从而减少搜索空间,并通过在正向搜索中仅松弛指向更重要节点的边,在反向搜索中松弛来自更重要节点的边,以达到高效计算最短路径的...
表面键收缩的证据,孙长庆,S. Li,Experimental evidence is given on the surface bond contraction induced by coordination imperfection of atoms in the surface skin.
求解线性可分离变量凸优化的非精确交替方向法,顾国勇,何炳生,Alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems. ...
标题中的"contraction-mapping-master_opf_"暗示了这是一个与数学优化方法——收缩映射(Contraction Mapping)相关的MATLAB代码库,特别是针对解决配电网的最优潮流问题(Optimal Power Flow, OPF)。在电力系统...
The Vertices of Lower Degree in Contraction-Critical $\kappa$ Connected,袁旭东,李婷婷,Let $G$ be a contraction-critical $\kappa$ connected graph. It is known (see {\it Graphs and Combinatorics}, 7...
A Biophysical Mechanism For Muscle Contraction and Spontaneous Oscillation,郭维生,罗辽复,Based on a simplified model of mechanochemical actin–activated myosin ATPase cycle the muscle state ...
Lorentz Contraction的矢量化表示和它的滤波器解释,杨正瓴,,1905年爱因斯坦提出了狭义相对论中的Lorentz收缩-----一个实数域的公式。1959年J. Terrell证明Lorentz收缩等效于一个旋转,并且给出了旋转角�
Oracle-type posterior contraction rates意味着后验分布的收缩速率与真实参数的“Oracle”(即理想情况下的最优)收缩速率一致。Oracle rate是已知真实参数情况下的最优收缩速率。在实际应用中,真解的光滑性等信息...
一款日线级范围的信号指标。
共动坐标系下引力坍缩的精确解,辜英求,,星体的引力坍缩是一个被热烈讨论但让人困惑的问题。这个问题不仅涉及流体动力学,而且涉及选择坐标系的问题。在Oppenheimer & Snyder的�
纳米铋,锡固体 a- c-轴向同性晶格相对收缩,孙长庆,,The a- and c- axis of Sn and Bi were measured to contract anisotropically but considering the relative change, they are isotropy.
纤维悬浮湍流收缩流场中的取向分布和流变特性计算涉及复杂的流体动力学和数学建模问题。在造纸工业中,由于纸张是由稀释的纤维悬浮液在纸机开始时通过特制的管道形成的,故此问题尤为重要。本文探讨了纤维悬浮液在...