Теоремы теории графов

Здесь собраны теоремы из теории графов.

Лемма о рукопожатиях

Основная статья: Лемма о рукопожатиях

Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:

$\Sigma_{v\in V(G)}deg v=2 |E(G)|$

Следствие. В любом графе число вершин нечетной степени четно

Существование эйлерова пути и цикла

Основная статья: Эйлеров цикл

Теорема (Л. Эйлер, 1736 г.)

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Теорема для орграфов

Связный орграф $G$ тогда и только тогда является эйлеровым орграфом, когда для любой его вершины $v$ выполняется равенство $d^+(v) = d^-( v)$. В связном орграфе G существует эйлеров путь в том и только в том случае, когда в этом орграфе имеются такие две вершины $u$ и $v$, что $d^+(u) = d^-(u) + 1$ и $d^-( v) = d^+(v) + 1$, а для каждой из остальных вершин степень исхода совпадает со степенью захода.

Литература

• Оре О. Теория графов. 2-е изд. — М.: Наука, 1980. — 336 с.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9

Для улучшения этой статьи по математике желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Проставить интервики в рамках проекта Интервики. Добавить иллюстрации.