Чтобы определить количество компонент связности в графе с заданными степенями вершин, можно использовать алгоритм серии обходов. 24

Суть алгоритма: запустить обход из первой вершины, и все вершины, которые он обойдёт, образуют первую компоненту связности. 24 Затем найти первую из оставшихся вершин, которые ещё не были посещены, и запустить обход из неё, найдя тем самым вторую компоненту связности. 24 И так далее, пока все вершины не станут помеченными. 24

Компонента связности — это множество вершин, в котором из любой вершины есть путь в любую другую вершину этого множества, но ни из какой вершины этого множества нельзя попасть в некоторую вершину вне этого множества. 2

Пример: в графе 18 вершин, степень каждой из которых равна 2 или 5, нужно определить, сколько компонент связности может быть в таком графе. 1 Решение: 1

1. Все вершины могут быть связаны — это 1 компонента связности. 1
2. Можно отделить 3 вершины со степенью 2, которые образуют треугольный подграф, а остальные 15 вершин будут связаны между собой — это 2 компоненты. 1
3. Можно отделить 2 таких треугольника — останется 12 связанных вершин, среди которых будет хотя бы одна вершина со степенью 5 — это 3 компоненты. 1
4. Можно отделить 3 таких треугольника — останется 9 вершин в большой компоненте — это 4 компоненты связности. 1
5. Можно отделить 4 треугольника — останется 6 вершин — это 5 компонент связности. 1 Больше отделять нельзя, так как 6 вершин — это минимально возможный граф, в котором может быть степень вершины 5. 1