Дано:
- Для планарного графа с 5 вершинами (n = 5).
- Для планарного графа с 6 вершинами (n = 6).
Найти:
Максимальное количество рёбер (m) в планарном графе для n = 5 и n = 6.
Решение:
Согласно теореме Эйлера для планарных графов, выполняется следующее неравенство:
m ≤ 3n - 6,
где m — максимальное количество рёбер, а n — количество вершин.
1. Для n = 5:
Подставим значение n в формулу:
m ≤ 3 * 5 - 6
m ≤ 15 - 6
m ≤ 9.
Таким образом, для графа с 5 вершинами максимальное количество рёбер равно 9.
2. Для n = 6:
Подставим значение n в формулу:
m ≤ 3 * 6 - 6
m ≤ 18 - 6
m ≤ 12.
Таким образом, для графа с 6 вершинами максимальное количество рёбер равно 12.
Ответ:
Для планарного графа с 5 вершинами максимальное количество рёбер равно 9. Для планарного графа с 6 вершинами максимальное количество рёбер равно 12.