ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 30759
Темы:    [ Планарные графы. Формула Эйлера ]
[ Деревья ]
[ Инварианты ]
Сложность: 3+
Классы: 7,8,9
Название задачи: Формула Эйлера.
В корзину
Прислать комментарий

Условие

Пусть связный плоский граф с V вершинами и E рёбрами разрезает плоскость на F кусков. Докажите формулу Эйлера:  V – E + F = 2.


Решение

Будем удалять рёбра по одному, пока граф не превратится в дерево (как в задаче 31098 а). На каждом шаге число как число рёбер, так и число кусков уменьшается на 1 (при удалении ребра два примыкающих к нему куска сливаются в один). Поэтому величина  V – E + F  не меняется. Но для полученного дерева она равна 2, поскольку  E = V – 1  (см. задачу 31098 б), а  F = 1.

Источники и прецеденты использования

книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 5
Название Графы
Тема Теория графов
задача
Номер 38

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .