Question

В графе 100 вершин, и степень каждой вершины равна 3. Какое максимальное число компонент связности может быть в этом графе?

Answer 1

Этот граф весь состоит из многоугольников.

В минимальном случае это просто 100-угольник, у него 1 компонент.

В максимальном случае это 32 треугольника и один 4-угольник.

У него 33 компонента связности.

Answer 2

Для решения этой задачи нам нужно знать, что количество рёбер в графе со степенью каждой вершины равной 3 равно 3n/2, где n - количество вершин в графе.

В данном случае, граф имеет 100 вершин и каждая вершина имеет степень 3, поэтому количество рёбер в графе будет 3*100/2 = 150.

Мы можем использовать формулу Эйлера, которая устанавливает связь между количеством вершин, рёбер и компонент связности в графе:

количество компонент связности = количество рёбер - количество вершин + 1

Для данного графа мы можем подставить известные значения:

количество компонент связности = 150 - 100 + 1 = 51

Таким образом, максимальное число компонент связности в этом графе равно 51.