You get a bonus - 1 coin for daily activity. Now you have 1 coin

Graph connectivity component

Lecture




  Graph connectivity component

Disconnected graph with three connected components

A connected component of a graph is a set of vertices of a graph such that for any two vertices from this set there is a path from one to another, and there is no path from the vertex of this set to a vertex not from this set.

For oriented graphs, the concept of a strong connected component is defined.

Algorithm

To search for components of connectivity, you can use the search in width or search in depth. In this case, the elapsed time will be linear (relative to the number of vertices and edges).

See also

  • Connected graph
  • Completely disconnected graph
  • Glossary of graph theory
  • The component of strong connectivity in the digraph
  • Percolation theory

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.