그래프 G에서 모든 노드들이 connected(directly 또는 indirectly) 일 때 그래프 G는 connected라고 말한다.
[ungirected graph G에서 connected에 대한 정의]
In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. A graph is called connected if every pair of distinct vertices in the graph is connected (directly or indirectly). A connected component is a maximal connected subgraph of G. Each vertex belongs to exactly one connected component, as does each edge.
[directed graph G에서 connected 에 대한 정의]
A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is strongly connected or strong if it contains a directed path from u to v for every pair of vertices u,v. The strong components are the maximal strongly connected subgraphs.
[cut 에 대한 정의]
cut (vertex cut)은 connected graph G를 두개의 connected graph G로 만드는 노드들의 집합
connectivity(vertex connectivity) k(G)는 cut의 집합 중 최소인 것
그래프가 k-connected (k-vertex-connected)란 connectivity가 k이상인 그래프
A cut or vertex cut of a connected graph G is a set of vertices whose removal renders G disconnected. The connectivity or vertex connectivity κ(G) is the size of a smallest vertex cut. A graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater. A complete graph with n vertices has no cuts at all, but by convention its connectivity is n-1. A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u,v) is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs; that is, κ(u,v)=κ(v,u). Moreover, κ(G) equals the minimum of κ(u,v) over all pairs of vertices u,v.
2-connectivity is also called "biconnectivity" and 3-connectivity is also called "triconnectivity".
[edge cut에 대한 정의]
Analogous concepts can be defined for edges. Thus an edge cut of G is a set of edges whose removal renders the graph disconnected. The edge-connectivity λ(G) is the size of a smallest edge cut, and the local edge-connectivity λ(u,v) of two vertices u,v is the size of a smallest edge cut disconnecting u from v. Again, local edge-connectivity is symmetric. A graph is called k-edge-connected if its edge connectivity is k or greater.
Lecture Note
invalid-file그래프를 파티션 하기 위한 방법으로 Graph G의 dual Graph G*을 구한다.
G*에서 루프를 찾으면 그 루프를 지나는 edge들이 Graph G의 cut 이 된다.
따라서 G*의 최소 cycle을 찾으면 이 edge들이 Graph G의 Min-Cut 이 된다.
Link
http://cskane.blogspot.com/2008/01/minimum-cut.html