Английская Википедия:Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs.[1] It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.
Connected vertices and graphs
In an undirected graph Шаблон:Mvar, two vertices Шаблон:Mvar and Шаблон:Mvar are called connected if Шаблон:Mvar contains a path from Шаблон:Mvar to Шаблон:Mvar. Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length Шаблон:Math (that is, they are the endpoints of a single edge), the vertices are called adjacent.
A graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called disconnected. An undirected graph G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. A graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected.
A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from Шаблон:Mvar to Шаблон:Mvar or a directed path from Шаблон:Mvar to Шаблон:Mvar for every pair of vertices Шаблон:Mvar.[2] It is strongly connected, or simply strong, if it contains a directed path from Шаблон:Mvar to Шаблон:Mvar and a directed path from Шаблон:Mvar to Шаблон:Mvar for every pair of vertices Шаблон:Mvar.
Components and cuts
A connected component is a maximal connected subgraph of an undirected graph. Each vertex belongs to exactly one connected component, as does each edge. A graph is connected if and only if it has exactly one connected component.
The strong components are the maximal strongly connected subgraphs of a directed graph.
A vertex cut or separating set of a connected graph Шаблон:Mvar is a set of vertices whose removal renders Шаблон:Mvar disconnected. The vertex connectivity Шаблон:Math (where Шаблон:Mvar is not a complete graph) is the size of a minimal vertex cut. A graph is called Шаблон:Mvar-vertex-connected or Шаблон:Mvar-connected if its vertex connectivity is Шаблон:Mvar or greater.
More precisely, any graph Шаблон:Mvar (complete or not) is said to be Шаблон:Mvar-vertex-connected if it contains at least Шаблон:Math vertices, but does not contain a set of Шаблон:Math vertices whose removal disconnects the graph; and Шаблон:Math is defined as the largest Шаблон:Mvar such that Шаблон:Mvar is Шаблон:Mvar-connected. In particular, a complete graph with Шаблон:Mvar vertices, denoted Шаблон:Mvar, has no vertex cuts at all, but Шаблон:Math.
A vertex cut for two vertices Шаблон:Mvar and Шаблон:Mvar is a set of vertices whose removal from the graph disconnects Шаблон:Mvar and Шаблон:Mvar. The local connectivity Шаблон:Math is the size of a smallest vertex cut separating Шаблон:Mvar and Шаблон:Mvar. Local connectivity is symmetric for undirected graphs; that is, Шаблон:Math. Moreover, except for complete graphs, Шаблон:Math equals the minimum of Шаблон:Math over all nonadjacent pairs of vertices Шаблон:Mvar.
Шаблон:Math-connectivity is also called biconnectivity and Шаблон:Math-connectivity is also called triconnectivity. A graph Шаблон:Mvar which is connected but not Шаблон:Math-connected is sometimes called separable.
Analogous concepts can be defined for edges. In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. More generally, an edge cut of Шаблон:Mvar is a set of edges whose removal renders the graph disconnected. The edge-connectivity Шаблон:Math is the size of a smallest edge cut, and the local edge-connectivity Шаблон:Math of two vertices Шаблон:Mvar is the size of a smallest edge cut disconnecting Шаблон:Mvar from Шаблон:Mvar. Again, local edge-connectivity is symmetric. A graph is called Шаблон:Mvar-edge-connected if its edge connectivity is Шаблон:Mvar or greater.
A graph is said to be maximally connected if its connectivity equals its minimum degree. A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree.[3]
Super- and hyper-connectivity
A graph is said to be super-connected or super-κ if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected or hyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. A graph is semi-hyper-connected or semi-hyper-κ if any minimum vertex cut separates the graph into exactly two components.[4]
More precisely: a Шаблон:Mvar connected graph is said to be super-connected or super-κ if all minimum vertex-cuts consist of the vertices adjacent with one (minimum-degree) vertex. A Шаблон:Mvar connected graph is said to be super-edge-connected or super-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex.[5]
A cutset Шаблон:Mvar of Шаблон:Mvar is called a non-trivial cutset if Шаблон:Mvar does not contain the neighborhood Шаблон:Math of any vertex Шаблон:Math. Then the superconnectivity κ1 of G is:
- κ1(G) = min{|X| : X is a non-trivial cutset}.
A non-trivial edge-cut and the edge-superconnectivity λ1(G) are defined analogously.[6]
Menger's theorem
One of the most important facts about connectivity in graphs is Menger's theorem, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices.
If Шаблон:Mvar and Шаблон:Mvar are vertices of a graph Шаблон:Mvar, then a collection of paths between Шаблон:Mvar and Шаблон:Mvar is called independent if no two of them share a vertex (other than Шаблон:Mvar and Шаблон:Mvar themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between Шаблон:Mvar and Шаблон:Mvar is written as Шаблон:Math, and the number of mutually edge-independent paths between Шаблон:Mvar and Шаблон:Mvar is written as Шаблон:Math.
Menger's theorem asserts that for distinct vertices u,v, Шаблон:Math equals Шаблон:Math, and if u is also not adjacent to v then Шаблон:Math equals Шаблон:Math.[7][8] This fact is actually a special case of the max-flow min-cut theorem.
Computational aspects
The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. A simple algorithm might be written in pseudo-code as follows:
- Begin at any arbitrary node of the graph, Шаблон:Mvar
- Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
- Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of Шаблон:Mvar, the graph is connected; otherwise it is disconnected.
By Menger's theorem, for any two vertices Шаблон:Mvar and Шаблон:Mvar in a connected graph Шаблон:Mvar, the numbers Шаблон:Math and Шаблон:Math can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of Шаблон:Mvar can then be computed as the minimum values of Шаблон:Math and Шаблон:Math, respectively.
In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004.[9] Hence, undirected graph connectivity may be solved in Шаблон:Math space.
The problem of computing the probability that a Bernoulli random graph is connected is called network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are #P-hard.[10]
Number of connected graphs
Шаблон:Main The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence Шаблон:OEIS link. The first few non-trivial terms are
| n | graphs |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Examples
- The vertex- and edge-connectivities of a disconnected graph are both Шаблон:Math.
- Шаблон:Math-connectedness is equivalent to connectedness for graphs of at least 2 vertices.
- The complete graph on Шаблон:Mvar vertices has edge-connectivity equal to Шаблон:Math. Every other simple graph on Шаблон:Mvar vertices has strictly smaller edge-connectivity.
- In a tree, the local edge-connectivity between any two distinct vertices is Шаблон:Math.
Bounds on connectivity
- The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, Шаблон:Math.
- The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum degree of the graph because removing all the edges that are incident to a vertex of minimum degree will disconnect that vertex from the rest of the graph.[1]
- For a vertex-transitive graph of degree Шаблон:Mvar, we have: Шаблон:Math.[11]
- For a vertex-transitive graph of degree Шаблон:Math, or for any (undirected) minimal Cayley graph of degree Шаблон:Mvar, or for any symmetric graph of degree Шаблон:Mvar, both kinds of connectivity are equal: Шаблон:Math.[12]
Other properties
- Connectedness is preserved by graph homomorphisms.
- If Шаблон:Mvar is connected then its line graph Шаблон:Math is also connected.
- A graph Шаблон:Mvar is Шаблон:Math-edge-connected if and only if it has an orientation that is strongly connected.
- Balinski's theorem states that the polytopal graph (Шаблон:Math-skeleton) of a Шаблон:Mvar-dimensional convex polytope is a Шаблон:Mvar-vertex-connected graph.[13] Steinitz's previous theorem that any 3-vertex-connected planar graph is a polytopal graph (Steinitz theorem) gives a partial converse.
- According to a theorem of G. A. Dirac, if a graph is Шаблон:Mvar-connected for Шаблон:Math, then for every set of Шаблон:Mvar vertices in the graph there is a cycle that passes through all the vertices in the set.[14][15] The converse is true when Шаблон:Math.
See also
- Algebraic connectivity
- Cheeger constant (graph theory)
- Dynamic connectivity, Disjoint-set data structure
- Expander graph
- Strength of a graph
References
- ↑ 1,0 1,1 Шаблон:Cite web
- ↑ Chapter 11: Digraphs: Principle of duality for digraphs: Definition
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal.
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book Chapter 27 of The Handbook of Combinatorics.
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal.
- ↑ Шаблон:Cite journal.
