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. ...
路径规划算法 CH Contraction Hierarchies,bing地图现在使用的路径导航算法,注重路径规划算法开发的同学可以下载收藏,使用价值很高,原始论文。
表面键收缩的证据,孙长庆,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. ...
A Biophysical Mechanism For Muscle Contraction and Spontaneous Oscillation,郭维生,罗辽复,Based on a simplified model of mechanochemical actin–activated myosin ATPase cycle the muscle state ...
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...
Lorentz Contraction的矢量化表示和它的滤波器解释,杨正瓴,,1905年爱因斯坦提出了狭义相对论中的Lorentz收缩-----一个实数域的公式。1959年J. Terrell证明Lorentz收缩等效于一个旋转,并且给出了旋转角�
Caldesmon is a key factor in contraction and stiffness of vascular smooth muscle cells,JIANG Qifeng,,In this paper, the potential role of CaD in mediating mechanical properties of VSMCs was probed ...
MATLAB CODE FOR OPF to solve power flow for distribution feeders
一款日线级范围的信号指标。
贝叶斯反问题最优后验收缩率研究,林逵,陆帅,本文讨论了Hilbert空间下的贝叶斯反问题。在此工作中,作者主要研究了反演解的收缩率,也即后验分布收缩到一个Delta函数的速率。这样的�
共动坐标系下引力坍缩的精确解,辜英求,,星体的引力坍缩是一个被热烈讨论但让人困惑的问题。这个问题不仅涉及流体动力学,而且涉及选择坐标系的问题。在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.
纤维悬浮湍流收缩流场中纤维取向分布和流变特性的计算,林建忠,,本文用雷诺应力模式求解雷诺平均运动方程,得到了具有矩形截面纤维悬浮湍流收缩流场中的平均速度和湍动能。然后将流场的湍流脉动
图$G$的极小减边-缩边序列和$G$-泊车函数,马俊,叶永南,在这篇论文中,对一个无向连通图$G$, 从$G$的极小减边-缩边序列的集合到$G$-泊车函数的集合间的一个一一对应被建立。 利用这个一一对应
This communication proposes a ... Using this method, our studies indicat that the PVC (premature ventricular contraction) detection has at least a 92 percent sensitivity for MIT/BIH arrhythmia database.
变论域模糊控制中伸缩因子参数分析,郭海刚,李洪兴,伸缩因子在变论域模糊控制中有着至关重要的作用,它的设计直接关系到控制性能的好坏。比例型和指数型伸缩因子是常用的两种伸缩因
On the Use of Random Discretization and Dimensionality Reduction in Ensembles for Big Data Chapter 3. Hybrid Deep Learning Based on GAN for Classifying BSR Noises from Invehicle Sensors Chapter 4. ...