Question

СРОЧНО!!! ДАЮ 100 БАЛЛОВ!!!!!!! в графе 18 вершин, причём степень каждой вершины равна 2 или 5, вершины обеих степеней присутствуют. сколько компонент связности может быть в таком графе?

Answer 1

Ответ:

От 1 до 5

Пошаговое объяснение:

На рисунке приведены примеры. Больше пяти из-за условия существования вершины степени 5 быть не может. Минимум 6 вершин будет в компоненте с вершиной степени 5 и минимум 3 должно быть в компонентах степени 2.

Answer 2

В данном графе 18 вершин, и каждая вершина имеет степень 2 или 5. Давайте рассмотрим возможные варианты компонент связности:

1. Все вершины со степенью 2 образуют циклы. Так как степень вершин ограничена 2 или 5, здесь могут быть только циклы размера 3 (треугольники). В этом случае будет 6 циклов. Каждый такой цикл вносит по 1 компоненту связности.

2. Остальные вершины (со степенью 5) образуют более сложную структуру. Поскольку степень каждой вершины равна 5, они могут быть организованы в циклы размера 5 (пятиугольники) или формировать более сложные графы с большим числом вершин.

Следовательно, максимальное количество компонент связности будет 6, соответствующее 6 циклам размера 3.

Может быть и другие сложные структуры, но для максимального числа компонент связности важно, чтобы второй тип вершин (степени 5) был как можно более объединен в одну компоненту.