Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 [ 9 ] 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

Глава 3 СЕТИ

И раздумался старый Илья Муромец, Илья Муромец, сын Иванович: Да в какую дороженьку буде ехати ?

3.1. Эйлеровы и гамильтоновы графы. Деревья

Проявление интереса к графам и сетям принято отсчитывать от работ Леонарда Эйлера и Уильяма Роуэна Гамильтона (см. [1] и [2]).

В задаче, решенной Эйлером в 1736 году и получившей в дальнейшем название задачи о семи кенигсбергских мостах, требовалось непрерывно обойти их (мосты), проходя только однажды через каждый мост [3] (рис. 1а и 16).



Рис. 1а

В 1859 году Гамильтон предложил владельцу фабрики игрушек в Дублине необычную головоломку, основной частью которой был деревянный додекаэдр (рис. 2а и 26). В каждую вершину додекаэдра, помеченную названием одного из известных городов (Брюссель, Дели, Франкфурт и т. д.), был вбит гвоздик и к одному из них была привязана нить. Требовалось соединить вершины додекаэдра этой нитью так, чтобы она проходила вдоль его ребер, обвивая каждый гвоздик




Рис. 2а Рис. 26

ровно один раз, и чтобы полученный в результате ниточный маршрут был замкнутым (циклом).

Владелец фабрики принял предложение Гамильтона и выплатил ему 25 гиней.

Интересно отметить, что обе эти разделенные более чем столетием задачи являются оптимизационными. Обратимся к первой из этих задач.

Ясно, что минимальное число мостов, которые нужно пройти с тем, чтобы в итоге были пройдены все, не меньше самого числа этих мостов.

Эйлеру удалось описать все ситуации, в которых эти два числа совпадают:

После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, при помощи которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может ([3], с. 153).

Сформулируем этот результат, пользуясь современной терминологией.

Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом (рис. За). Тем самым, начало и конец каждого ребра графа суть его вершины.





Рис. 36

Путем, соединяющим вершины А и В графа, называется упорядоченная совокупность его ребер, обладающая следующим свойством: начало каждого ребра, начиная со второго, совпадает с концом предыдущего ребра, при этом начало первого ребра совпадает с вершиной А, а конец последнего - с вершиной В (рис. 36). Вершины А и В называются связанными, если существует путь, соединяющий эти вершины. Граф называется связным, если связаны любые две его вершины. 1

Вершина графа называется четной, если число всех выходящих из нее (или, что то же, входящих в нее) ребер четно, и нечетной, если число всех выходящих из нее (или, что то же, входящих в нее) ребер нечетно. Вершина А на рисунке 36 четна (из нее выходит четыре ребра), а вершина В нечетна (из нее выходит три ребра).

Наконец, последнее: граф называется конечным, если конечны и число его ребер, и число его вершин.

Всюду в дальнейшем мы будем рассматривать только конечные и связные графы.

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

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



1 2 3 4 5 6 7 8 [ 9 ] 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92