Let \(G(V,E,\gamma)\) be a non-empty undirected graph.
* \(G\) is called connected, if there is a path \(P=w-u\) between any two of its vertices \(w\) and \(u\). Equivalently, a connected graph has exactly one component, i.e. the output of the algorithm get_components(G) is a set \(C\) of subgraphs with \(|C|=1\).
* \(G\) is called disconnected, if it has more than one component, i.e. if it is not connected.
* An edge in a connected graph is a bridge, if its removal leaves a disconnected graph.
* A vertex of a connected graph is a cutvertex or articulation point, if its removal leaves a disconnected graph.
The above graph \(G\), consisting of \(14\) vertices is disconnected. However, It has the following conntected components:
The edge \((3,6)\) is a bridge of the component \(G[1,2,3,4,5,6,7,8]\) and the edge \((9,11)\) is a bridge of the component \(G[9,10]\).
The vertices \(3\) and \(4\) are articulation points of the component \(G[1,2,3,4,5,6,7,8]\).
Algorithms: 1
Corollaries: 2
Definitions: 3 4
Proofs: 5 6 7 8 9 10 11 12 13 14
Propositions: 15 16
Theorems: 17 18 19 20 21 22 23 24 25 26
