Connectivity (graph theory)

From Wikipedia for FEVERv2
(Redirected from Connected graph)
Jump to navigation Jump to search

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 isolated subgraphs. Connectivity (graph theory)_sentence_0

It is closely related to the theory of network flow problems. Connectivity (graph theory)_sentence_1

The connectivity of a graph is an important measure of its resilience as a network. Connectivity (graph theory)_sentence_2

Connected vertices and graphs Connectivity (graph theory)_section_0

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. Connectivity (graph theory)_sentence_3

If the two vertices are additionally connected by a path of length 1, i.e. by a single edge, the vertices are called adjacent. Connectivity (graph theory)_sentence_4

A graph is said to be connected if every pair of vertices in the graph is connected. Connectivity (graph theory)_sentence_5

This means that there is a path between every pair of vertices. Connectivity (graph theory)_sentence_6

An undirected graph that is not connected is called disconnected. Connectivity (graph theory)_sentence_7

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. Connectivity (graph theory)_sentence_8

A graph with just one vertex is connected. Connectivity (graph theory)_sentence_9

An edgeless graph with two or more vertices is disconnected. Connectivity (graph theory)_sentence_10

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. Connectivity (graph theory)_sentence_11

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. 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. Connectivity (graph theory)_sentence_12

Components and cuts Connectivity (graph theory)_section_1

A connected component is a maximal connected subgraph of an undirected graph. Connectivity (graph theory)_sentence_13

Each vertex belongs to exactly one connected component, as does each edge. Connectivity (graph theory)_sentence_14

A graph is connected if and only if it has exactly one connected component. Connectivity (graph theory)_sentence_15

The strong components are the maximal strongly connected subgraphs of a directed graph. Connectivity (graph theory)_sentence_16

A vertex cut or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. Connectivity (graph theory)_sentence_17

The vertex connectivity κ(G) (where G is not a complete graph) is the size of a minimal vertex cut. Connectivity (graph theory)_sentence_18

A graph is called k-vertex-connected or k-connected if its vertex connectivity is k or greater. Connectivity (graph theory)_sentence_19

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. Connectivity (graph theory)_sentence_20

In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but κ(Kn) = n − 1. Connectivity (graph theory)_sentence_21

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). Connectivity (graph theory)_sentence_22

Moreover, except for complete graphs, κ(G) equals the minimum of κ(u, v) over all nonadjacent pairs of vertices u, v. Connectivity (graph theory)_sentence_23

2-connectivity is also called biconnectivity and 3-connectivity is also called triconnectivity. Connectivity (graph theory)_sentence_24

A graph G which is connected but not 2-connected is sometimes called separable. Connectivity (graph theory)_sentence_25

Analogous concepts can be defined for edges. Connectivity (graph theory)_sentence_26

In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. Connectivity (graph theory)_sentence_27

More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. Connectivity (graph theory)_sentence_28

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. Connectivity (graph theory)_sentence_29

A graph is called k-edge-connected if its edge connectivity is k or greater. Connectivity (graph theory)_sentence_30

A graph is said to be maximally connected if its connectivity equals its minimum degree. Connectivity (graph theory)_sentence_31

A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree. Connectivity (graph theory)_sentence_32

Super- and hyper-connectivity Connectivity (graph theory)_section_2

A graph is said to be super-connected or super-κ if every minimum vertex cut isolates a vertex. Connectivity (graph theory)_sentence_33

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. Connectivity (graph theory)_sentence_34

A graph is semi-hyper-connected or semi-hyper-κ if any minimum vertex cut separates the graph into exactly two components. Connectivity (graph theory)_sentence_35

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. Connectivity (graph theory)_sentence_36

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. Connectivity (graph theory)_sentence_37

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. Connectivity (graph theory)_sentence_38

Then the superconnectivity κ1 of G is: Connectivity (graph theory)_sentence_39

Connectivity (graph theory)_description_list_0

  • κ1(G) = min{|X| : X is a non-trivial cutset}.Connectivity (graph theory)_item_0_0

A non-trivial edge-cut and the edge-superconnectivity λ1(G) are defined analogously. Connectivity (graph theory)_sentence_40

Menger's theorem Connectivity (graph theory)_section_3

Main article: Menger's theorem Connectivity (graph theory)_sentence_41

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. Connectivity (graph theory)_sentence_42

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). Connectivity (graph theory)_sentence_43

Similarly, the collection is edge-independent if no two paths in it share an edge. Connectivity (graph theory)_sentence_44

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). Connectivity (graph theory)_sentence_45

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). Connectivity (graph theory)_sentence_46

This fact is actually a special case of the max-flow min-cut theorem. Connectivity (graph theory)_sentence_47

Computational aspects Connectivity (graph theory)_section_4

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. Connectivity (graph theory)_sentence_48

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. Connectivity (graph theory)_sentence_49

A simple algorithm might be written in pseudo-code as follows: Connectivity (graph theory)_sentence_50

Connectivity (graph theory)_ordered_list_1

  1. Begin at any arbitrary node of the graph, GConnectivity (graph theory)_item_1_1
  2. Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.Connectivity (graph theory)_item_1_2
  3. 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.Connectivity (graph theory)_item_1_3

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. Connectivity (graph theory)_sentence_51

The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), respectively. Connectivity (graph theory)_sentence_52

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. Connectivity (graph theory)_sentence_53

Hence, undirected graph connectivity may be solved in O(log n) space. Connectivity (graph theory)_sentence_54

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. Connectivity (graph theory)_sentence_55

Both of these are #P-hard. Connectivity (graph theory)_sentence_56

Number of connected graphs Connectivity (graph theory)_section_5

The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence , through n = 16. Connectivity (graph theory)_sentence_57

The first few non-trivial terms are Connectivity (graph theory)_sentence_58

Examples Connectivity (graph theory)_section_6

Connectivity (graph theory)_unordered_list_2

  • The vertex- and edge-connectivities of a disconnected graph are both 0.Connectivity (graph theory)_item_2_4
  • 1-connectedness is equivalent to connectedness for graphs of at least 2 vertices.Connectivity (graph theory)_item_2_5
  • 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.Connectivity (graph theory)_item_2_6
  • In a tree, the local edge-connectivity between every pair of vertices is 1.Connectivity (graph theory)_item_2_7

Bounds on connectivity Connectivity (graph theory)_section_7

Connectivity (graph theory)_unordered_list_3

  • The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ λ(G). 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.Connectivity (graph theory)_item_3_8
  • For a vertex-transitive graph of degree d, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.Connectivity (graph theory)_item_3_9
  • 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.Connectivity (graph theory)_item_3_10

Other properties Connectivity (graph theory)_section_8

Connectivity (graph theory)_unordered_list_4

  • Connectedness is preserved by graph homomorphisms.Connectivity (graph theory)_item_4_11
  • If G is connected then its line graph L(G) is also connected.Connectivity (graph theory)_item_4_12
  • A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.Connectivity (graph theory)_item_4_13
  • Balinski's theorem states that the polytopal graph (1-skeleton) of a k-dimensional convex polytope is a k-vertex-connected graph. Steinitz's previous theorem that any 3-vertex-connected planar graph is a polytopal graph (Steinitz theorem) gives a partial converse.Connectivity (graph theory)_item_4_14
  • 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. The converse is true when k = 2.Connectivity (graph theory)_item_4_15

See also Connectivity (graph theory)_section_9

Connectivity (graph theory)_unordered_list_5

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: (graph theory).