Дано:
V - число вершин графа.
E - число рёбер графа.
F - число областей, на которые граф разбивает плоскость (включая внешнюю).
Найти:
х = V - E + F, показать, что х = 2 для связного плоского графа.
Решение:
1. Используем теорему Эйлера для плоских графов, которая гласит, что для любого связного плоского графа выполняется следующее равенство:
V - E + F = 2.
2. Доказательство:
а) Рассмотрим минимальный случай - треугольник. У него 3 вершины, 3 рёбра и 2 области (внешняя и внутренняя). Подставим в формулу:
3 - 3 + 2 = 2.
б) Теперь, если мы добавим одну вершину к графу, соединённую с существующими вершинами, то увеличится число вершин на 1 и рёбер на количество рёбер, которые соединяют новую вершину с другими. Таким образом, для добавления новой вершины и рёбер:
1) Если добавляем одну вершину и соединяем её с k рёбрами, то:
V' = V + 1, E' = E + k.
2) Число областей не изменится или увеличится на 1, если добавление вершины создаёт новую область:
F' = F + 1 или F' = F (если не создаётся новая область).
В итоге, для увеличенного графа:
х' = (V + 1) - (E + k) + (F + 1 или F).
Подставляя и упрощая, получим:
х' = V - E + F + 1 - k + 1 или V - E + F - k = х + 1 - k.
в) Если k = 1 (новая вершина соединяется с одной), то:
х' = х + 1 - 1 = х.
г) Если k > 1, то количество новых областей тоже будет увеличиваться, и формула останется верной. Таким образом, после добавления любой вершины и рёбер, значение х не меняется или может уменьшиться, но всегда остается равным 2.
3. Таким образом, мы показали, что для любого связного плоского графа выполняется равенство:
х = V - E + F = 2.
Ответ:
Эйлерова характеристика связного плоского графа равна 2: х = 2.