Читать курсовая по математике: "Эйлеровы графы" Страница 5

(Назад) (Cкачать работу)

Сопоставим плану города граф G, вершины которого соответствуют четырём разделяемым рекой участкам суши A, B, Cи D, а рёбра - мостам. Этот граф изображён на рис. 1.16.

Рисунок 1.15Рисунок 1.16

Эйлер доказал неразрешимость задачи о кёнигсбергских мостах. В своей работе, опубликованной в 1736 году, он сформулировал и решил следующую общую проблему теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

Цикл в графе называется эйлеровым, если он содержит все рёбра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

Например, граф, изображённый на рис. 1.17, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода рёбер.

Помимо задачи о кёнигсбергских мостах известен ряд других старинных занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета (рис. 1.18), не отрывая карандаша от бумаги и не повторяя линий.

Рисунок 1.17Рисунок 1.18 .2.3Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов

Возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым? Прежде чем дать полный ответ на вопрос в теореме 1, докажем простую лемму.

Лемма.Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные рёбра, то утверждение очевидно; поэтому предположим, что Gявляется простым графом. Пусть v - произвольная вершина графа G; построим по индукции маршрут

→→→ … , выбирая вершинусмежной вершине , а для i ≥ 1 - выбирая смежнойи отличной от (существование такой вершиныгарантировано условием леммы). Так как Gимеет конечное число вершин, то в конце концов мы придём к вершине, которая уже была выбрана раньше. Предположим, что- первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями , и является требуемым циклом.

Теорема 1.Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет чётную степень.

Доказательство. =>Предположим, что Pявляется эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Pчерез любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Pровно один раз, то каждая вершина должна иметь чётную степень.

3х = 200, чего не может быть при натуральном х. Значит, 100 дорог в таком государстве быть не может.

№10

Докажите, что число людей, живших когда-либо на Земле и сделавших нечётное число рукопожатий, чётно.

Доказательство.Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия - его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными.) Люди, сделавшие нечетное число рукопожатий, - нечетные вершины такого графа, поэтому по теореме о чётности числа нечётных вершин графа их количество четно. .3 Связность графа В стране Семёрка 15 городов, каждый из городов соединён дорогами не менее, чем с семью

Похожие работы