- Теоремы теории графов
-
Здесь собраны теоремы из теории графов.
Содержание
Лемма о рукопожатиях
Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:
Следствие. В любом графе число вершин нечетной степени четно
Существование эйлерова пути и цикла
Теорема (Л. Эйлер, 1736 г.)
Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
Теорема для орграфов
Связный орграф тогда и только тогда является эйлеровым орграфом, когда для любой его вершины выполняется равенство . В связном орграфе G существует эйлеров путь в том и только в том случае, когда в этом орграфе имеются такие две вершины и , что и , а для каждой из остальных вершин степень исхода совпадает со степенью захода.
Литература
- Оре О. Теория графов. 2-е изд. — М.: Наука, 1980. — 336 с.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9
Для улучшения этой статьи по математике желательно?: - Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
- Проставить интервики в рамках проекта Интервики.
- Добавить иллюстрации.
Категория:- Теория графов
Wikimedia Foundation. 2010.