Connection (graph theory)

A connected graph : two nodes can be connected by an edge sequence. An edge sequence between the nodes v and w is highlighted in red as an example.

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

This disconnected graph has two components. The nodes v and w cannot be connected.

An undirected graph is connected if for any two nodes , an undirected way in with a start node and available as a terminal node. ${\displaystyle G=(V,E)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle \in V}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle w}$

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 . ${\displaystyle G=(V,E)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle G}$

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. ${\displaystyle G[U]}$ ${\displaystyle U\subset V}$ ${\displaystyle G}$ ${\displaystyle G[U]}$ ${\displaystyle G}$

Important statements and sentences

The following statements can be made relatively easily:

1. Every connected undirected graph with nodes contains at least edges . ${\displaystyle n}$ ${\displaystyle n-1}$
2. Every strongly connected directed graph with nodes contains at least edges. ${\displaystyle n}$ ${\displaystyle n}$
3. An undirected graph is connected if and only if it contains a spanning tree .
4. 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.
5. 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 . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \kappa (u,v)}$ ${\displaystyle \lambda (u,v)}$ ${\displaystyle \kappa (u,v)}$ ${\displaystyle \lambda (u,v)}$

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 : ${\displaystyle n}$ ${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle K_{n}}$ ${\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle n!}$ ${\displaystyle n\leq 8}$

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

Individual evidence

1. ^ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic . 2018, doi : 10.1007 / 978-3-662-58029-5 .
2. ↑ sequence A001187 in OEIS
3. ↑ Follow A001349 in OEIS