0.7 Graphs  (Page 20/21)

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 O(logn) 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.

7.5.1. non-direction connectivity

(From Wikipedia, the free encyclopedia)

A undirected graph G is an ordered pair G: = (V,E) that is subject to the following conditions:

• V is a set, whose elements are called vertices or nodes,
• E is a set of pairs (unordered) of distinct vertices, called edges or lines

The vertices belonging to an edge are called the ends, endpoints, or end vertices of the edge.

V (and hence E) are usually taken to be finite sets, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case. The order of a graph is | V | (the number of vertices). A graph's size is | E | , the number of edges. The degree of a vertex is the number of other vertices it is connected to by edges.

The edge set E induces a symmetric binary relation ~ on V that is called the adjacency relation of G. Specifically, for each edge {u,v} the vertices u and v are said to be adjacent to one another, which is denoted u ~ v.

For an edge {u, v} graph theorists usually use the somewhat shorter notation uv.