Дискретная математика. Ерош И.Л - 90 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

90
5. ТЕОРИЯ ГРАФОВ
Язык графов используется в ряде математических разделов, таких,
например, как теория управляющих автоматов, теория алгоритмов,
теория цепей Маркова. Широко применяется язык теории графов при
описании моделей в экономике, биологии и других областях.
5.1. «Задача о кёнигсбергских мостах»
Первой работой, в которой использовалось название «граф» и дава
лось его точное определение, была работа Л. Эйлера, которая появилась
в 1736 году в трудах Петербургской академии наук. В ней Эйлер предла
гает читателю головоломку «Задача о кёнигсбергских мостах». Город Кё
нигсберг (ныне Калининград) расположен на двух берегах реки Прегель
и двух островах. Районы города соединены мостами (рис. 5.1, а).
Вопрос состоит в том, можно ли, выйдя из одного района города, по
одному разу пройти по каждому из мостов и вернуться в исходный район?
Л. Эйлер каждому району сопоставляет вершину, каждому мосту –
ребро и уже на языке графов (рис. 5.1, b) формулирует задачу: суще
ствует ли циклический маршрут из последовательности ребер, выхо
дящий из любой вершины графа и проходящий по каждому ребру в точ
ности по одному разу?
Попытки найти такой маршрут к успеху не приводят, и тогда Л. Эй
лер формулирует и доказывает свою теорему: Для того чтобы существо+
вал циклический маршрут в графе G, необходимо и достаточно, чтобы
граф был связным и степени всех его вершин были четными.
Теперь мы можем сформулировать определение графа. Графом на
зывается пара (V, E), где V – множество вершин, E – множество инци
дентных им ребер. Под степенью вершины графа понимается число ре
бер, инцидентных этой вершине (связанных с ней).
Рис 5.1. Граф переходов по мостам г. Калининграда
a)
b)

Страницы