Lecture
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.
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).
Comments
To leave a comment
Discrete Math. Set theory. Graph theory. Combinatorics.
Terms: Discrete Math. Set theory. Graph theory. Combinatorics.