Теория графов

| Категория реферата: Рефераты по математике
| Теги реферата: сочинение сказка, отчет по производственной практике
| Добавил(а) на сайт: Wegolev.

Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным.

Так, в нашем случае к участку A ведут пять мостов, а к остальным

– по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка.

Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.

История с мостами города Кенигсберга имеет современное продолжение.
Откроем, например, школьный учебник по математике под редакцией Н.Я.
Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

Задача № 569. На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?

(РИСУНОК 1.2)

Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров
E или F, чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.

В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-
1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ

Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.

Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.

Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).

(РИСУНОК 2.1)

В дальнейшем вершины графа мы будем обозначать латинскими буквами A,
B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.

Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.

Определение 2.03. Граф, состоящий только из изолированных вершин, называется нуль-графом.

Обозначение: O' – граф с вершинами, не имеющий ребер (рис. 2.2).

(РИСУНОК 2.2)

Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным.

Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали (рис. 2.3).

(РИСУНОК 2.3)

Определение 2.05. Степенью вершины называется число ребер, которым принадлежит вершина.