Взвешенные графы. 
Математическая обработка информации

Взвешенный граф — это граф, дугам которого поставлены в соответствие веса, так что дуге (x_if xj) сопоставлено некоторое число с (x_jy Xj) = называемое длиной (или весом, или стоимостью) дуги (табл. 3.9). Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном графе — это сумма длин (весов) тех ребер, из которых состоит путь.

Расстояние между вершинами — это длина кратчайшего пути. Например, расстояние от вершины а до вершины d во взвешенном графе, изображенном на рис. 3.33, равно 6.

Рис. 3.33. Пример взвешенного графа.

Таблица 3.9

Примеры взвешенных графов

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

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф — эйлеровым графом.

Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф — полуэйлеровым графом.

Эти понятия возникли в статье Эйлера в 1735 г., в которой он решал задачу о кенигсбергских мостах и впервые ввел понятие графа. На рис. 3.34а приведен план расположения семи мостов в Кенигсберге (ныне Калининграде). Задача состоит в том, чтобы пройти каждый мост, но одному разу и вернуться в исходную точку С. Поскольку в конце обхода нужно вернуться в исходную часть города и на каждом мосту побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие циклы и стали называть эйлеровыми, а графы, имеющие эйлеров цикл — эйлеровыми графами.

Рис. 334. Задача Эйлера о кенигсбергских мостах:

а — план расположения семи мостов в Кенигсберге (ныне Калининграде); б — граф семи мостов в Кенигсберге: мосты изображены в виде ребер графа, вершины изображают части города, к которым ведут мосты Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы — это графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной и той же точке.

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

Теорема Эйлера. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было не больше двух.

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

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

Граф называется гамильтоновым, если он обладает гамильтоновым циклом.

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

Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, такие как, например, расстояние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.

Теорема Кёнига. В полном конечном графе всегда существует гамильтонов путь.

Если в графе G (X) с п вершинами для любой пары вершин Xj и Xj справедливо неравенство.

где m (x_t), m (xj) — степени вершин х, и х_у то граф G (X) имеет гамильтонову цепь.

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

Пример 3.12. Четырем студентам (Иванову, Петрову, Семенову и Захарову) поручено от имени группы выбрать подарок девушке Алисе на день рождения (Захаров — староста группы, в случае равного разделения голосов его голос решающий). После долгих споров ребята остановились на четырех предметах:

• • плюшевый медведь — П.М.;
• • МПЗ-плеер —МПЗ;
• • коробка конфет — К. К.;
• • парфюмерный набор — П.Н.

При обсуждении выяснилось, что по отношению к этим предметам у каждого из ребят своя система предпочтений. Системы эти представляют собой полные ориентированные графы с четырьмя вершинами (рис. 3.35). Стрелка от одной вершины к другой обозначает, что первая вершина предпочтительнее второй. Например, стрелка от МПЗ к П.М. на рис. 3.35а обозначает, что Иванов при сравнении плюшевого медведя и МПЗ-плеера предпочитает последний. По рисункам читаем, что Иванов наибольшее предпочтение отдает коробке конфет, Петров — плюшевому медведю, Захаров — МПЗ-плееру, Семенов не отдает большего предпочтения ни одному из четырех предметов.

Ребята договорились о системе выбора подарка, которая на первый взгляд не вызывает возражений. Было решено выбирать большинством голосов (каждый голосует в соответствии со своими предпочтениями) один из двух предметов в следующем порядке:

• 1) либо П.М., либо МПЗ;
• 2) либо предмет, получивший большинство голосов на первом шаге голосования, либо К.К.;
• 3) либо предмет, получивший большинство голосов на втором шаге голосования, либо П.Н.

Какой же подарок они должны выбрать при этой системе голосования? Следим по графам на рис. 3.35. На первом шаге при сравнении П.М. и МПЗ большинством голосов (Иванов, Семенов и Захаров) должны были выбрать МПЗ-плеер. На втором шаге при сравнении МПЗ-плеера и коробки конфет большинством голосов (Иванов, Петров и Семенов) должны были выбрать коробку конфет. На третьем шаге при сравнении коробки конфет и парфюмерного набора большинством голосов (Петров, Семенов и Захаров) должны были выбрать парфюмерный набор.

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

Если бы, например, Иванов вник в особенности системы голосования с предпочтением и ему очень хотелось бы подарить Алисе коробку конфет, то он предложил бы друзьям изменить порядок сравнения пар предметов так, чтобы коробка конфет рассматривалась только в последней паре. Тогда, какие бы пары ни сравнивались на I и II этапах голосования, будет выбрана коробка конфет.

Рис. 3.35. Полные ориентированные графы предпочтений:

а — Иванов; б — Петров; в — Семенов; г — Захаров Пример 3.13. В одном общежитии в разных комнатах на одном этаже живут четыре друга-студснта: Алексей, Егор, Виктор и Михаил. Известно, что каждый из них учится в университете на разных факультетах: технологии, славянской филологии, художественнографическом и обществознания, но неизвестно, кто на каком факультете, и неизвестно, кто в какой комнате. Однако известно, что:

• 1) студент факультета технологии живет левее студента славянской филологии;
• 2) студент художественно-графического факультета живет правее студента факультета обществознания;
• 3) студент факультета обществознания живет рядом со студентом факультета славянской филологии;
• 4) студент факультета технологии живет не рядом со студентом факультета славянской филологии;
• 5) Виктор живет правее студента факультета обществознания;
• 6) Михаил не учится на факультете технологии;
• 7) Егор живет рядом с учащимся факультета славянской филологии;
• 8) Виктор живет левее Егора.

Выясните, кто на каком факультете учится и кто где живет?

Решение. Введем обозначения: А — Алексей; Е — Егор; В — Виктор; М — Михаил; Т — факультет технологии; С — факультет славянской филологии; Xхудожественно-графический факультет; О — факультет общсствознания.

Начнем в первого условия и выпишем варианты, которые удовлетворяют ему (на рис. 3.36 это первая строка). Далее будем накладывать следующее условие на выбранные варианты. И так будем делать до тех пор, пока не рассмотрим все условия. На рис. 3.36 описан ход решения.

Рис. 3.36. Решение задачи с помощью ориентированного

графа

Пример 3.14. В соревнованиях по настольному теннису, проходящих по олимпийской системе, участвуют 10 спортсменов. За какое минимальное время можно провести соревнование, если в спортивном зале установлено два теннисных стола, и на каждую встречу, включая разминку и отдых, отводится час? Изобразите схему соревнований с помощью корневого дерева (рис. 3.37).

Рис. 3.37. Схема соревнований — корневое дерево

Минимум 5 ч необходимо, чтобы провести соревнования.

Пример 3.15. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств:

• 1) учитель истории может дать либо первый, либо второй, либо третий урок, но только один;
• 2) учитель литературы может дать либо один, либо второй, либо третий урок;
• 3) математик готов дать либо только первый, либо только третий урок;
• 4) преподаватель физкультуры согласен дать только последний урок.

Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?

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

Рис. 3.38. Граф — расписание уроков

Итого получается три возможных варианта расписания уроков (табл. 3.10).

Варианты расписания уроков