computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

, connectivity is one of the basic concepts of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

: it asks for the

minimum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...

number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. 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 In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

, two '' vertices'' and are called connected if contains a

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...

from to . Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length , i.e. by a single edge, the vertices are called adjacent. A

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is said to be connected if every pair of vertices in the graph is connected. This means that there is a

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 In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

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 to or a directed path from to for every pair of vertices . It is strongly connected, or simply strong, if it contains a directed path from to and a directed path from to for every pair of vertices .

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 In graph theory, a vertex subset is a vertex separator (or vertex cut, separating set) for nonadjacent vertices and if the removal of from the graph separates and into distinct connected components. Examples Consider a grid graph with ...

or separating set of a connected graph is a set of vertices whose removal renders disconnected. The vertex connectivity (where is not a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

) is the size of a minimal vertex cut. A graph is called '-vertex-connected or '-connected if its vertex connectivity is or greater. More precisely, any graph (complete or not) is said to be ''-vertex-connected'' if it contains at least vertices, but does not contain a set of vertices whose removal disconnects the graph; and is defined as the largest such that is -connected. In particular, a

with vertices, denoted , has no vertex cuts at all, but . A vertex cut for two vertices and is a set of vertices whose removal from the graph disconnects and . The local connectivity is the size of a smallest vertex cut separating and . Local connectivity is symmetric for undirected graphs; that is, . Moreover, except for complete graphs, equals the minimum of over all nonadjacent pairs of vertices . -connectivity is also called '' biconnectivity'' and -connectivity is also called ''triconnectivity''. A graph which is connected but not -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 A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...

''. More generally, an edge cut of is a set of edges whose removal renders the graph disconnected. The ''

edge-connectivity In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration ...

'' is the size of a smallest edge cut, and the local edge-connectivity of two vertices is the size of a smallest edge cut disconnecting from . Again, local edge-connectivity is symmetric. A graph is called ''-edge-connected'' if its edge connectivity is 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.

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. More precisely: a 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 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. A cutset of is called a non-trivial cutset if does not contain the neighborhood of any vertex . Then the ''superconnectivity'' κ1 of G is: : κ1(G) = min. A non-trivial edge-cut and the ''edge-superconnectivity'' λ1(G) are defined analogously.

Menger's theorem

One of the most important facts about connectivity in graphs is

Menger's theorem In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of Vertex (graph theory), vertices. Pro ...

, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices. If and are vertices of a graph , then a collection of paths between and is called independent if no two of them share a vertex (other than and themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between and is written as , and the number of mutually edge-independent paths between and is written as . Menger's theorem asserts that for distinct vertices ''u'',''v'', equals , and if ''u'' is also not adjacent to ''v'' then equals . This fact is actually a special case of the

max-flow min-cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...

Computational aspects

The problem of determining whether two vertices in a graph are connected can be solved efficiently using a

search algorithm In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...

, such as

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...

. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a

disjoint-set data structure In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set ...

), or to count the number of connected components. A simple algorithm might be written in

pseudo-code In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...

as follows: #Begin at any arbitrary node of the graph, #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 , the graph is connected; otherwise it is disconnected. By Menger's theorem, for any two vertices and in a connected graph , the numbers and can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of can then be computed as the minimum values of and , 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 Omer Reingold ( he, עומר ריינגולד) is an Israeli computer scientist. He is the Rajeev Motwani professor of Computer Science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the T ...

in 2004. Hence, undirected graph connectivity may be solved in space. The problem of computing the probability that a

Bernoulli Bernoulli can refer to: People *Bernoulli family of 17th and 18th century Swiss mathematicians: ** Daniel Bernoulli (1700–1782), developer of Bernoulli's principle **Jacob Bernoulli (1654–1705), also known as Jacques, after whom Bernoulli numbe ...

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.

Number of connected graphs

The number of distinct connected labeled graphs with ''n'' nodes is tabulated in the

On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...

as sequence . The first few non-trivial terms are

Examples

* The vertex- and edge-connectivities of a disconnected graph are both . * -connectedness is equivalent to connectedness for graphs of at least 2 vertices. * The

on vertices has edge-connectivity equal to . Every other simple graph on vertices has strictly smaller edge-connectivity. * In a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

, the local edge-connectivity between every pair of vertices is .

Bounds on connectivity

* The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, . Both are less than or equal to the minimum degree of the graph, since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph. * For a

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

of degree , we have: . * For a

of degree , or for any (undirected) minimal

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

of degree , or for any

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

of degree , both kinds of connectivity are equal: .

Other properties

* Connectedness is preserved by

graph homomorphism In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...

s. * If is connected then its

line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

is also connected. * A graph is -edge-connected

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is b ...

it has an orientation that is strongly connected. *

Balinski's theorem In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected ...

states that the

polytopal graph A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

(- skeleton) of a -dimensional convex

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

is a -vertex-connected graph.

Steinitz Steinitz may refer to: * Steinitz, Germany, a town in the district of Altmarkkreis Salzwedel in Saxony-Anhalt in Germany * Steinitz (surname) {{Disambiguation ...

'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 -connected for , then for every set of vertices in the graph there is a cycle that passes through all the vertices in the set.. The converse is true when .

References

{{reflist