Connectivity (graph theory): Difference between revisions
mNo edit summary |
Undid revision 1212856941 by Jayy V (talk) partial revert: WP:NOTBROKEN, some MOS violations, pointless spacing twiddles; also take the time to improve some other bad formatting |
||
Line 6: | Line 6: | ||
== Connected vertices and graphs == |
== Connected vertices and graphs == |
||
[[File:UndirectedDegrees.svg|thumb|With vertex 0, this graph is disconnected. The rest of the graph is connected.]] |
[[File:UndirectedDegrees.svg|thumb|With vertex 0, this graph is disconnected. The rest of the graph is connected.]] |
||
In an [[ |
In an [[undirected graph]] {{mvar|G}}, two [[vertex (graph theory)|vertices]] {{mvar|u}} and {{mvar|v}} are called '''connected''' if {{mvar|G}} contains a [[Path (graph theory)|path]] from {{mvar|u}} to {{mvar|v}}. Otherwise, they are called '''disconnected'''. If the two vertices are additionally connected by a path of length {{math|1}} (that is, they are the endpoints of a single edge), the vertices are called '''adjacent'''. |
||
A [[Graph (discrete mathematics)|graph]] is said to be '''connected''' if every pair of vertices in the graph is connected. This means that there is a [[Path (graph theory)|path]] between every pair of vertices. An undirected graph that is not connected is called '''disconnected'''. An undirected graph {{mvar|G}} is therefore disconnected if there exist two vertices in {{mvar|G}} such that no path in {{mvar|G}} has these vertices as endpoints. A graph with just one vertex is connected. An [[Null graph|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|u}} to {{mvar|v}} or a directed path from {{mvar|v}} to {{mvar|u}} for every pair of vertices {{ |
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|u}} to {{mvar|v}} or a directed path from {{mvar|v}} to {{mvar|u}} for every pair of vertices {{math|''u'', ''v''}}.<ref>[http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2011.pdf#page=6 Chapter 11: Digraphs: Principle of duality for digraphs: Definition]</ref> It is '''strongly connected''', or simply strong, if it contains a directed path from {{mvar|u}} to {{mvar|v}} and a directed path from {{mvar|v}} to {{mvar|u}} for every pair of vertices {{math|''u'', ''v''}}. |
||
== Components and cuts == |
== Components and cuts == |
||
Line 19: | Line 19: | ||
A '''[[Cut (graph theory)|vertex cut]]''' or '''separating set''' of a connected graph {{mvar|G}} is a set of vertices whose removal renders {{mvar|G}} disconnected. The [[K-vertex-connected graph|'''vertex connectivity''']] {{math|''κ''(''G'')}} (where {{mvar|G}} is not a [[complete graph]]) is the size of a minimal vertex cut. A graph is called '''''{{mvar|k}}''-vertex-connected''' or '''''{{mvar|k}}''-connected''' if its vertex connectivity is {{mvar|k}} or greater. |
A '''[[Cut (graph theory)|vertex cut]]''' or '''separating set''' of a connected graph {{mvar|G}} is a set of vertices whose removal renders {{mvar|G}} disconnected. The [[K-vertex-connected graph|'''vertex connectivity''']] {{math|''κ''(''G'')}} (where {{mvar|G}} is not a [[complete graph]]) is the size of a minimal vertex cut. A graph is called '''''{{mvar|k}}''-vertex-connected''' or '''''{{mvar|k}}''-connected''' if its vertex connectivity is {{mvar|k}} or greater. |
||
More precisely, any graph {{mvar|G}} (complete or not) is said to be ''{{mvar|k}}-vertex-connected'' if it contains at least {{math|''k'' + 1}} vertices, but does not contain a set of {{math|''k'' − 1}} vertices whose removal disconnects the graph; and {{math|''κ'' |
More precisely, any graph {{mvar|G}} (complete or not) is said to be ''{{mvar|k}}-vertex-connected'' if it contains at least {{math|''k'' + 1}} vertices, but does not contain a set of {{math|''k'' − 1}} vertices whose removal disconnects the graph; and {{math|''κ''(''G'')}} is defined as the largest {{mvar|k}} such that {{mvar|G}} is {{mvar|k}}-connected. In particular, a [[complete graph]] with {{mvar|n}} vertices, denoted {{mvar|K<sub>n</sub>}}, has no vertex cuts at all, but {{math|''κ''(''K<sub>n</sub>'') {{=}} ''n'' − 1}}. |
||
A '''vertex cut''' for two vertices {{mvar|u}} and {{mvar|v}} is a set of vertices whose removal from the graph disconnects {{mvar|u}} and {{mvar|v}}. The '''local connectivity''' {{math|''κ'' |
A '''vertex cut''' for two vertices {{mvar|u}} and {{mvar|v}} is a set of vertices whose removal from the graph disconnects {{mvar|u}} and {{mvar|v}}. The '''local connectivity''' {{math|''κ''(''u'', ''v'')}} is the size of a smallest vertex cut separating {{mvar|u}} and {{mvar|v}}. Local connectivity is symmetric for undirected graphs; that is, {{math|''κ''(''u'', ''v'') {{=}} ''κ''(''v'', ''u'')}}. Moreover, except for complete graphs, {{math|''κ''(''G'')}} equals the minimum of {{math|''κ''(''u'', ''v'')}} over all nonadjacent pairs of vertices {{math|''u'', ''v''}}. |
||
2-connectivity is also called ''[[biconnected graph|biconnectivity]]'' and {{ |
{{math|2}}-connectivity is also called ''[[biconnected graph|biconnectivity]]'' and {{math|3}}-connectivity is also called ''triconnectivity''. A graph {{mvar|G}} which is connected but not {{math|2}}-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 (graph theory)|bridge]]''. More generally, an edge cut of {{mvar|G}} is a set of edges whose removal renders the graph disconnected. The ''[[edge-connectivity]]'' {{math|''λ'' |
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 (graph theory)|bridge]]''. More generally, an edge cut of {{mvar|G}} is a set of edges whose removal renders the graph disconnected. The ''[[edge-connectivity]]'' {{math|''λ''(''G'')}} is the size of a smallest edge cut, and the local edge-connectivity {{math|''λ''(''u'', ''v'')}} of two vertices {{math|''u'', ''v''}} is the size of a smallest edge cut disconnecting {{mvar|u}} from {{mvar|v}}. Again, local edge-connectivity is symmetric. A graph is called ''{{mvar|k}}-edge-connected'' if its edge connectivity is {{mvar|k}} or greater. |
||
A graph is said to be ''maximally connected'' if its connectivity equals its minimum [[ |
A graph is said to be ''maximally connected'' if its connectivity equals its minimum [[Degree (graph theory)|degree]]. A graph is said to be ''maximally edge-connected'' if its edge-connectivity equals its minimum degree.<ref>{{Cite book |
||
| title = Handbook of graph theory |
| title = Handbook of graph theory |
||
| first1 = Jonathan L. |
| first1 = Jonathan L. |
||
Line 57: | Line 57: | ||
}}</ref> |
}}</ref> |
||
A cutset {{mvar|X}} of {{mvar|G}} is called a non-trivial cutset if {{mvar|X}} does not contain the neighborhood {{math|N(''u'')}} of any vertex {{math|''u'' ∉ ''X''}}. Then the ''superconnectivity'' |
A cutset {{mvar|X}} of {{mvar|G}} is called a non-trivial cutset if {{mvar|X}} does not contain the neighborhood {{math|N(''u'')}} of any vertex {{math|''u'' ∉ ''X''}}. Then the ''superconnectivity'' <math>\kappa_1</math> of {{mvar|G}} is |
||
<math display="block">\kappa_1(G) = \min\{ |X| : X \text{ is a non-trivial cutset} \}.</math> |
|||
A non-trivial edge-cut and the ''edge-superconnectivity'' |
A non-trivial edge-cut and the ''edge-superconnectivity'' <math>\lambda_1(G)</math> are defined analogously.<ref>{{Cite journal|last1=Balbuena|first1=Camino|last2=Carmona|first2=Angeles|date=2001-10-01|title=On the connectivity and superconnectivity of bipartite digraphs and graphs|journal=Ars Combinatorica|volume=61|pages=3–22|citeseerx=10.1.1.101.1458}}</ref> |
||
== Menger's theorem == |
== Menger's theorem == |
||
Line 67: | Line 67: | ||
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. |
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|u}} and {{mvar|v}} are vertices of a graph {{mvar|G}}, then a collection of paths between {{mvar|u}} and {{mvar|v}} is called independent if no two of them share a vertex (other than {{mvar|u}} and {{mvar|v}} themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between {{mvar|u}} and {{mvar|v}} is written as {{math|'' |
If {{mvar|u}} and {{mvar|v}} are vertices of a graph {{mvar|G}}, then a collection of paths between {{mvar|u}} and {{mvar|v}} is called independent if no two of them share a vertex (other than {{mvar|u}} and {{mvar|v}} themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between {{mvar|u}} and {{mvar|v}} is written as {{math|''κ''′(''u'', ''v'')}}, and the number of mutually edge-independent paths between {{mvar|u}} and {{mvar|v}} is written as {{math|''λ''′(''u'', ''v'')}}. |
||
Menger's theorem asserts that for distinct vertices ''u'',''v'', {{math|''λ''(''u'', |
Menger's theorem asserts that for distinct vertices ''u'',''v'', {{math|''λ''(''u'', ''v'')}} equals {{math|''λ''′(''u'', ''v'')}}, and if ''u'' is also not adjacent to ''v'' then {{math|''κ''(''u'', ''v'')}} equals {{math|''κ''′(''u'', ''v'')}}.<ref>{{cite book|title=Algorithmic Graph Theory| author=Gibbons, A.|year=1985|publisher=[[Cambridge University Press]]}}</ref><ref>{{cite book|title=Algorithmic Aspects of Graph Connectivity|author1=Nagamochi, H. |author2=Ibaraki, T.|author2-link=Toshihide Ibaraki | year=2008 |publisher=Cambridge University Press}}</ref> This fact is actually a special case of the [[max-flow min-cut theorem]]. |
||
== Computational aspects == |
== 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#Applications|disjoint-set data structure]]), or to count the number of connected components. A simple algorithm might be written in [[pseudo-code]] as follows: |
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#Applications|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|G}} |
#Begin at any arbitrary node of the graph {{mvar|G}}. |
||
#Proceed from that node using either depth-first or breadth-first search, counting all nodes reached. |
#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|G}}, the graph is connected; otherwise it is disconnected. |
#Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of {{mvar|G}}, the graph is connected; otherwise it is disconnected. |
||
By Menger's theorem, for any two vertices {{mvar|u}} and {{mvar|v}} in a connected graph {{mvar|G}}, the numbers {{math|''κ''(''u'', |
By Menger's theorem, for any two vertices {{mvar|u}} and {{mvar|v}} in a connected graph {{mvar|G}}, the numbers {{math|''κ''(''u'', ''v'')}} and {{math|''λ''(''u'', ''v'')}} can be determined efficiently using the [[Max flow min cut|max-flow min-cut]] algorithm. The connectivity and edge-connectivity of {{mvar|G}} can then be computed as the minimum values of {{math|''κ''(''u'', ''v'')}} and {{math|''λ''(''u'', ''v'')}}, respectively. |
||
In [[computational complexity theory]], [[SL (complexity)|SL]] is the class of problems [[log-space reducible]] to the problem of determining whether two vertices in a graph are connected, which was |
In [[computational complexity theory]], [[SL (complexity)|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 (complexity)|L]] by [[Omer Reingold]] in 2004.<ref>{{Cite journal|first=Omer|last=Reingold|author-link=Omer Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|volume=55|issue=4|pages=1–24| doi=10.1145/1391289.1391291|s2cid=207168478}}</ref> Hence, undirected graph connectivity may be solved in {{math|O(log ''n'')}} space. |
||
The problem of computing the probability that a [[Bernoulli distribution|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 [[sharp-P|#P]]-hard.<ref>{{cite journal |
The problem of computing the probability that a [[Bernoulli distribution|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 [[sharp-P|#P]]-hard.<ref>{{cite journal |
||
Line 129: | Line 129: | ||
== Examples == |
== Examples == |
||
* The vertex- and edge-connectivities of a disconnected graph are both {{math|0}}. |
* The vertex- and edge-connectivities of a disconnected graph are both {{math|0}}. |
||
* 1-connectedness is equivalent to connectedness for graphs of at least 2 vertices. |
* {{math|1}}-connectedness is equivalent to connectedness for graphs of at least 2 vertices. |
||
* The [[complete graph]] on {{mvar|n}} vertices has edge-connectivity equal to {{math|''n'' − 1}}. Every other [[simple graph]] on {{mvar|n}} vertices has strictly smaller edge-connectivity. |
* The [[complete graph]] on {{mvar|n}} vertices has edge-connectivity equal to {{math|''n'' − 1}}. Every other [[simple graph]] on {{mvar|n}} vertices has strictly smaller edge-connectivity. |
||
* In a [[tree (graph theory)|tree]], the local edge-connectivity between any two distinct vertices is {{math|1}}. |
* In a [[tree (graph theory)|tree]], the local edge-connectivity between any two distinct vertices is {{math|1}}. |
||
== Bounds on connectivity == |
== Bounds on connectivity == |
||
* The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, {{math|''κ'' |
* The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, {{math|''κ''(''G'') ≤ ''λ''(''G'')}}. |
||
* The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum [[ |
* The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum [[Degree (graph theory)|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.<ref name="diestel">{{cite web|last=Diestel|first=R.|url=http://diestel-graph-theory.com/GrTh.html|title=Graph Theory, Electronic Edition|date=2005|pages=12}}</ref> |
||
* For a [[vertex-transitive graph]] of degree {{mvar|d}}, we have: {{math|2(''d'' + 1)/3 ≤ ''κ'' |
* For a [[vertex-transitive graph]] of degree {{mvar|d}}, we have: {{math|2(''d'' + 1)/3 ≤ ''κ''(''G'') ≤ ''λ''(''G'') {{=}} ''d''}}.<ref name="GandR">{{cite book|title=Algebraic Graph Theory| last1=Godsil | first1=C. |author1-link=Chris Godsil| last2=Royle| first2=G.| author2-link=Gordon Royle|year=2001|publisher=Springer Verlag}}</ref> |
||
* For a vertex-transitive graph of degree {{math|''d'' ≤ 4}}, or for any (undirected) minimal [[Cayley graph]] of degree {{mvar|d}}, or for any [[symmetric graph]] of degree {{mvar|d}}, both kinds of connectivity are equal: {{math|''κ'' |
* For a vertex-transitive graph of degree {{math|''d'' ≤ 4}}, or for any (undirected) minimal [[Cayley graph]] of degree {{mvar|d}}, or for any [[symmetric graph]] of degree {{mvar|d}}, both kinds of connectivity are equal: {{math|''κ''(''G'') {{=}} ''λ''(''G'') {{=}} ''d''}}.<ref>{{cite book|title=Automorphism groups, isomorphism, reconstruction|series=Technical Report TR-94-10|author=Babai, L.|author-link=László Babai|year=1996|publisher=University of Chicago|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|url-status=dead|archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|archive-date=2010-06-11}} Chapter 27 of ''The Handbook of Combinatorics''.</ref> |
||
== Other properties == |
== Other properties == |
||
* Connectedness is preserved by [[graph homomorphism]]s. |
* Connectedness is preserved by [[graph homomorphism]]s. |
||
* If {{mvar|G}} is connected then its [[line graph]] {{math|''L''(''G'' |
* If {{mvar|G}} is connected then its [[line graph]] {{math|''L''(''G'')}} is also connected. |
||
* A graph {{mvar|G}} is 2-edge-connected if and only if it has an orientation that is strongly connected. |
* A graph {{mvar|G}} is {{math|2}}-edge-connected if and only if it has an orientation that is strongly connected. |
||
* [[Balinski's theorem]] states that the [[polytopal graph]] 1-[[ |
* [[Balinski's theorem]] states that the [[polytopal graph]] ({{math|1}}-[[Skeleton (topology)|skeleton]]) of a {{mvar|k}}-dimensional [[convex polytope]] is a {{mvar|k}}-vertex-connected graph.<ref>{{cite journal|author = Balinski, M. L.|title = On the graph structure of convex polyhedra in {{mvar|n}}-space|journal = [[Pacific Journal of Mathematics]]|volume = 11|issue = 2|year = 1961|pages = 431–434|doi = 10.2140/pjm.1961.11.431|doi-access = free}}</ref> [[Ernst Steinitz|Steinitz]]'s previous theorem that any 3-vertex-connected [[planar graph]] is a polytopal graph ([[Steinitz theorem]]) gives a partial [[converse (logic)|converse]]. |
||
* According to a theorem of [[Gabriel Andrew Dirac|G. A. Dirac]], if a graph is {{mvar|k}}-connected for {{math|''k'' ≥ 2}}, then for every set of {{mvar|k}} vertices in the graph there is a [[cycle (graph theory)|cycle]] that passes through all the vertices in the set.<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | author-link = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao |
* According to a theorem of [[Gabriel Andrew Dirac|G. A. Dirac]], if a graph is {{mvar|k}}-connected for {{math|''k'' ≥ 2}}, then for every set of {{mvar|k}} vertices in the graph there is a [[cycle (graph theory)|cycle]] that passes through all the vertices in the set.<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | author-link = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao |
||
| last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8 |
| last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8 |
Revision as of 22:23, 9 March 2024
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 G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length 1 (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 u to v or a directed path from v to u for every pair of vertices u, v.[2] It is strongly connected, or simply strong, if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.
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 G is a set of vertices whose removal renders G disconnected. The vertex connectivity κ(G) (where G is not a complete graph) is the size of a minimal vertex cut. A graph is called k-vertex-connected or k-connected if its vertex connectivity is k or greater.
More precisely, any graph G (complete or not) is said to be k-vertex-connected if it contains at least k + 1 vertices, but does not contain a set of k − 1 vertices whose removal disconnects the graph; and κ(G) is defined as the largest k such that G is k-connected. In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but κ(Kn) = 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, except for complete graphs, κ(G) equals the minimum of κ(u, v) over all nonadjacent pairs of vertices u, v.
2-connectivity is also called biconnectivity and 3-connectivity is also called triconnectivity. A graph G which is connected but not 2-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 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.
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 G 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 G 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 X of G is called a non-trivial cutset if X does not contain the neighborhood N(u) of any vertex u ∉ X. Then the superconnectivity of G is
A non-trivial edge-cut and the edge-superconnectivity 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 u and v are vertices of a graph G, then a collection of paths between u and v is called independent if no two of them share a vertex (other than u and v themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between u and v is written as κ′(u, v), and the number of mutually edge-independent paths between u and v is written as λ′(u, v).
Menger's theorem asserts that for distinct vertices u,v, λ(u, v) equals λ′(u, v), and if u is also not adjacent to v then κ(u, v) equals κ′(u, v).[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 G.
- 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 G, the graph is connected; otherwise it is disconnected.
By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u, v) and λ(u, v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), 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 O(log n) 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
The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence A001187. 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 0.
- 1-connectedness is equivalent to connectedness for graphs of at least 2 vertices.
- The complete graph on n vertices has edge-connectivity equal to n − 1. Every other simple graph on n vertices has strictly smaller edge-connectivity.
- In a tree, the local edge-connectivity between any two distinct vertices is 1.
Bounds on connectivity
- The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ λ(G).
- 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 d, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.[11]
- For a vertex-transitive graph of degree d ≤ 4, or for any (undirected) minimal Cayley graph of degree d, or for any symmetric graph of degree d, both kinds of connectivity are equal: κ(G) = λ(G) = d.[12]
Other properties
- Connectedness is preserved by graph homomorphisms.
- If G is connected then its line graph L(G) is also connected.
- A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.
- Balinski's theorem states that the polytopal graph (1-skeleton) of a k-dimensional convex polytope is a k-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 k-connected for k ≥ 2, then for every set of k vertices in the graph there is a cycle that passes through all the vertices in the set.[14][15] The converse is true when k = 2.
See also
- Algebraic connectivity
- Cheeger constant (graph theory)
- Dynamic connectivity, Disjoint-set data structure
- Expander graph
- Strength of a graph
References
- ^ a b Diestel, R. (2005). "Graph Theory, Electronic Edition". p. 12.
- ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition
- ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.
- ^ Liu, Qinghai; Zhang, Zhao (2010-03-01). "The existence and upper bound for two types of restricted connectivity". Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.
- ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.
- ^ Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
- ^ Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
- ^ Nagamochi, H.; Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.
- ^ Reingold, Omer (2008). "Undirected connectivity in log-space". Journal of the ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478.
- ^ Provan, J. Scott; Ball, Michael O. (1983). "The complexity of counting cuts and of computing the probability that a graph is connected". SIAM Journal on Computing. 12 (4): 777–788. doi:10.1137/0212053. MR 0721012..
- ^ Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer Verlag.
- ^ Babai, L. (1996). Automorphism groups, isomorphism, reconstruction. Technical Report TR-94-10. University of Chicago. Archived from the original on 2010-06-11. Chapter 27 of The Handbook of Combinatorics.
- ^ Balinski, M. L. (1961). "On the graph structure of convex polyhedra in n-space". Pacific Journal of Mathematics. 11 (2): 431–434. doi:10.2140/pjm.1961.11.431.
- ^ Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311..
- ^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). "A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs". Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. MR 2297171..