Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its robustness as a network.

Definitions of components, cuts and connectivity

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. A connected component is a maximal connected subgraph of G. Each vertex belongs to exactly one connected component, as does each edge.

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

2-connectivity is also called "biconnectivity" and 3-connectivity is also called "triconnectivity".

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; that is, κ(u,v)=κ(v,u). Moreover, κ(G) equals the minimum of κ(u,v) over all pairs of vertices u,v.

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.

All of these definitions and notations carry over to directed graphs. Local connectivity and local edge-connectivity are not necessarily symmetric for directed graphs.

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 greatest number of independent paths between u and v is written as λ(u,v), and the greatest number of edge-independent paths between u and v is written as λ′(u,v).

Menger's theorem asserts that κ(u,v) = λ(u,v) and κ′(u,v) = λ′(u,v) for every pair of vertices u and v. 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.

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. Hence, directed graph connectivity may be solved in space.

Examples

  • The vertex- and edge-connectivities of a disconnected graph are both 0.
  • 1-connectedness is synonymous with connectedness.
  • 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 every pair of vertices is 1.

Properties

  • Connectedness is preserved by graph homomorphisms.
  • If G is connected then its line graph L(G) is also connected.
  • The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ κ′(G).
  • If a graph G is k-connected, then for every set of vertices U of cardinality k, there exists a cycle in G containing U. The converse is true when k = 2.
  • A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.

See also

Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge may not exceed the capacity of the edge.
..... Click the link for more information.
graph is the basic object of study in graph theory. Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges.
..... Click the link for more information.
vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered
..... Click the link for more information.
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex.
..... Click the link for more information.
graph is the basic object of study in graph theory. Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges.
..... Click the link for more information.
In an undirected graph, a connected component or component is a maximal connected subgraph. Two vertices are in the same connected component if and only if there exists a path between them.
..... Click the link for more information.
In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.

In other words, a biconnected graph is nonseparable, meaning if any edge were to be removed, the graph will remain connected.
..... Click the link for more information.
11 (2): 431–434.
..... Click the link for more information.
In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. The complete graph on vertices has vertices and edges, and is denoted by . It is a regular graph of degree .
..... Click the link for more information.
In graph theory, a graph with edge set is said to be -edge-connected if is connected for all with . In plain English, a graph is -edge-connected if the graph remains connected when you delete fewer than edges from the graph.
..... Click the link for more information.
In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and for vertex-connectivity by Karl Menger in 1927.
..... Click the link for more information.
The max-flow min-cut theorem is a statement in optimization theory about maximum flows in flow networks. It derives from Menger's theorem. It states that:
The maximum amount of flow is equal to the capacity of a minimal cut.

..... Click the link for more information.
In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions.
..... Click the link for more information.
General Data

Class: Search Algorithm
Data Structure: Graph
Time Complexity:
Space Complexity:
Optimal: yes (for unweighted graphs)
Complete: yes

In graph theory, breadth-first search (
..... Click the link for more information.
In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity
..... Click the link for more information.
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers.
..... Click the link for more information.
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space.
..... Click the link for more information.
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs.
..... Click the link for more information.
In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. The complete graph on vertices has vertices and edges, and is denoted by . It is a regular graph of degree .
..... Click the link for more information.
In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any connected graph with no cycles is a tree. A forest is a disjoint union of trees.
..... Click the link for more information.
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.
..... Click the link for more information.
In graph theory, the line graph L(G) of an undirected graph G is a graph such that
  • each vertex of L(G) represents an edge of G; and
  • any two vertices of L(G

..... Click the link for more information.
Cycle in graph theory and computer science has several meanings:
  • A closed walk, with repeated vertices allowed. See path (graph theory). (This usage is common in computer science. In graph theory it is more often called a closed walk.

..... Click the link for more information.
The algebraic connectivity of a graph G is the second smallest eigenvalue of the Laplacian matrix of G.

This eigenvalue is greater than 0 if and only if G is a connected graph.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.