# Connection (graph theory)

The **relationship** is a mathematical term from graph theory . A graph is called connected if the nodes are connected in pairs by an edge sequence of the graph.

## definition

### Undirected graph

An undirected graph is **connected** if for any two nodes , an undirected way in with a start node and available as a terminal node.

A maximally connected subgraph of any graph is called a **component** or **connected ****component** . A non-connected graph is partitioned by its connected components.

### Directed graph

A directed graph is called **(strong) connected by a node ****from** , if for every node in a directed way in from after there. is called **strongly connected** if it is **strongly connected** from every node. In other words, it means **strongly connected** if there is a directed path from to and a directed path from to in between any two nodes and from .

A directed graph is called **(weakly) connected** if the associated undirected graph (i.e. the graph that arises when you replace each directed edge with an undirected edge) is connected.

An induced subgraph for a subset is **strongly connected component** of case is strongly connected and not to a larger strongly connected subgraph of can be extended.

## Important statements and sentences

The following statements can be made relatively easily:

- Every connected undirected graph with nodes contains at least edges .
- Every strongly connected directed graph with nodes contains at least edges.
- An undirected graph is connected if and only if it contains a spanning tree .
- A directed graph is strongly connected if and only if its adjacency matrix is irreducible . An undirected graph is connected if and only if its adjacency matrix is irreducible.
- The class of all connected graphs cannot be axiomatized.

## Generalizations

An essential generalization of the term is represented by the concept of the k-fold node connection , the edge connection and the arc connection .

## Algorithms

Using depth-first search , a linear algorithm can easily be implemented that calculates the connected components of a graph and thus implies a simple test as to whether the graph is connected. The test of whether a directed graph is connected from a node *v* works analogously. Of Tarjan (1972) derived a linear algorithm for determining strong correlation components , which is also based on depth-first search in a directed graph and the strongly connected components and easily modified in undirected graph , the blocks and articulations calculated. See also union find structure .

The question of whether two nodes in a graph are connected can be accomplished using a search algorithm such as the breadth-first search , can be solved efficiently. In general, it is easy to determine with a computer whether a graph is connected, for example using a disjoint data structure , or to count the number of connected components. A simple algorithm can be formulated as follows:

- Start at any node on the graph.
- Drive from this node from either the depth-first search or breadth-first search continues and count all reached node.
- As soon as the graph has been completely traversed and the number of nodes counted is equal to the number of nodes in the graph, the graph is connected. Otherwise the connection will be terminated.

According to Menger's theorem , for any two nodes and in a connected graph, the numbers and can be determined efficiently using the Max-Flow-Min-Cut algorithm. The connection and the edge connection of graphs can then be calculated as minimum values of and .

The number of connected undirected graphs with nodes increases rapidly with the number of nodes, namely approximately exponentially to the number of edges of the complete graph , i.e. approximately proportionally to . If the nodes are not numbered, i.e. isomorphic graphs are not counted, this number is roughly proportional to , because for most isomorphism classes all graphs that result from the permutation of the numbered nodes are different. The following table shows the numbers determined with the help of a computer for :

Number of connected undirected graphs | ||
---|---|---|

n | with numbered nodes | without numbered nodes |

2 | 1 | 1 |

3 | 4th | 2 |

4th | 38 | 6th |

5 | 728 | 21st |

6th | 26704 | 112 |

7th | 1866256 | 853 |

8th | 251548592 | 11117 |

## literature

- Lutz Volkmann:
*Foundations of the graph theory.*Springer, Vienna 2001, ISBN 3-211-82774-9 . - Reinhard Diestel:
*graph theory.*Springer 2006, ISBN 3-540-21391-0 . ( English version )

## Web links

- Wolfram Mathworld:
*Connected Graph*