Connection (graph theory)
A maximally connected subgraph of any graph is called a component or connected component . A non-connected graph is partitioned by its connected components.
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 .
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.
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|
- 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 )
- Wolfram Mathworld: Connected Graph