Connectivity (graph theory)

The relationship is a mathematical term from graph theory. A graph is called connected if any two nodes can be connected by a sequence of edges of the graph.

Definition

Undirected graphs

An undirected graph is called connected if there is, for any two arbitrary nodes and from an undirected way with a start node and a leaf node. A maximal connected subgraph of is called a component or connection component. If there is not contiguous breaks the graph into its connected components.

Directed graphs

A directed graph is called (strongly ) connected by a from node if there is a directed path to each node in with a start node and a leaf node. is called strongly connected if is strongly connected from each node.

A directed graph is called (weakly ) connected if the corresponding undirected graph (ie the graph which arises when we replace each directed edge by an undirected edge ) is connected.

An induced subgraph of a subset is called strongly connected component of, if is strongly connected and not strongly connected induced subgraph of exists that contains genuine.

Note: There is exactly one way then with a start node and a leaf node, if there is a path with a start node and a leaf node. In the above definitions we can therefore replace path by path.

Important statements and phrases

Relatively light shows you the following statements:

Important algorithms

Using depth-first search is easy to implement a linear algorithm that computes the connected components of a graph, and so implies a simple test whether the graph is connected. The test for whether a directed graph from a node v from is connected, is analogous. From Tarjan (1972 ) where a linear algorithm for determining strong connected components, which is also based on depth-first search and calculated in the directed graph strongly connected components and slightly modified in undirected graphs the blocks and articulations.

Generalizations

A significant generalization of the concept represents the concept of k -fold node context, the edge-connectivity and the arc connection