Дано:
Количество домов (вершин) V = 5.
Количество рёбер E = C(5, 2) = 10 (каждая пара домов соединена дорожкой).
Найти:
Является ли граф K5 пленарным (можно ли его нарисовать так, чтобы дорожки не пересекались)?
Решение:
1. Граф K5 — полный граф на 5 вершинах, который имеет 10 рёбер.
2. Согласно теореме о плоских графах, граф можно нарисовать на плоскости без пересечений, если V - E + F = 2 и F ≥ 1.
3. Для полного графа K5:
- V = 5.
- E = 10.
4. Подставим в уравнение Эйлера:
5 - 10 + F = 2.
5. Упрощаем уравнение:
F - 5 = 2.
6. Переносим -5 в правую часть:
F = 7.
7. Теперь, проверим условия: для плоского графа максимальное количество рёбер E в зависимости от вершин V должно удовлетворять неравенству E ≤ 3V - 6.
8. Подставим значения:
10 ≤ 3(5) - 6.
9. Упрощаем:
10 ≤ 15 - 6.
10. Получаем:
10 ≤ 9 (неверно).
Ответ:
Граф K5 не является пленарным.