CFA LogoCFA Logo Computer
Новости Статьи Магазин Прайс-лист Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

В графском парке

Юрий ДОВГАНЬ freeyuran@ukrpost.net

Продолжение, начало см. в МК № 33-34, 38, 43, 46, 48 (256-257, 261, 266, 269, 271).
В прошлый раз мы остановились на проблеме эйлеровых циклов в графах. С большой долей серьезности не побоюсь назвать ее эйлеровой проблемой. Почему так? Давайте на некоторое время перенесемся в далекий 1736 год.

Именно в этом году великий математик Леонард Эйлер доказал невозможность существования решения задачи о кенигсбергских мостах. Заключается задача в следующем. Город Кенигсберг (более известный нам сейчас как Калининград) исторически поделен на четыре части: правый и левый берега речки Прегель и два острова. Разные части этого города в то время соединялись семью мостами. Требовалось найти маршрут, который бы проходил по каждому мосту ровно один раз и в итоге заканчивался бы в начальной точке пути.

На рисунке отчетливо видны все 4 части города зеленого цвета, речка и 7 мостов желтого цвета. В виде графа город можно представить следующим образом:

Пусть A, B, C, D — вершины, соответствующие частям Кенигсберга. Ребра графа представляют собою мосты, которые соединяют разные части города. Возле каждой вершины в скобочках указана ее степень — количество мостов, которые соединяют эту часть города с соседними частями. Идея доказательства невозможности такого маршрута состоит в следующем: при посещении каждой вершины мосту, по которому мы вошли в часть города, должен соответствовать мост, по которому мы ее покинем. Другими словами, количество ребер, инцидентных каждой вершине должно быть четным, что и доказал Эйлер в своей теореме, огорчив всех своих предшественников. Вот такая вот грустная история :-).

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

Часть 12. Гамильтоновы циклы и гамильтоновы графы.

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

Достаточным условием «гамильтоновости» графа может служить такая теорема: если в графе с N вершинами для любых его двух несмежных вершин v1 и v2 справедливо неравенство St(v1)+St(v2)N, где St(vi) — степень i-й вершины, то в нем существует цикл Гамильтона. Поскольку теорема отображает лишь достаточные условия существования гамильтоновых циклов в графе, то найдутся и такие экземпляры, которые не удовлетворяют неравенству теоремы, но в то же время являются гамильтоновыми. Другими словами, если неравенство справедливо, то граф гарантировано будет содержать гамильтонов цикл. В противном же случае мы не можем утверждать наверняка отсутствие оных.

Пускай на входе имеется связный неориентированный граф G с N вершинами. Требуется найти все гамильтоновы циклы графа G, если таковые в нем имеются.

К большому нашему сожалению, науке пока еще неизвестны эффективные методы решения поставленной задачи. Поэтом предлагается воспользоваться «дешевым и сердитым» методом перебора с возвратом, в народе именуемым как back-tracking алгоритм.

А выглядит он следующим образом. Начиная с определенной вершины (пускай это будет вершина с номером 1) будем продвигаться вперед по графу, включая очередное ребро в гамильтонов цикл. При найденных первых k компонент решения рассматриваем ребра, которые выходят из последней вершины. Если находим ребро, которое ведет в неучтенную ранее вершину, добавляем новую вершину в цикл — она становятся просмотренной. (k+1)-я компонента решения при этом получена. При отсутствии такой вершины возвращаемся к предыдущей и ищем другие смежные с ней. Цикл считается найденным, если просмотрены все вершины графа, и из последней можно достичь начальной. Такой цикл можно вывести на экран и продолжить поиск других.

Давайте попробуем записать все это на инопланетном языке :-).

Вспомним некоторые глобальные типы:

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

К примеру, для графа

программа выдаст следующие циклы с порядком вершин:

Здесь указан порядок вершин. Разумеется, каждый цикл замыкается в 1-й вершине, то есть начальной.

Часть 13. Раскраски

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

Как ни странно, такими вещами тоже занимается теория графов. Представим, что политическая карта мира — это граф. Здесь каждое государство представляет собой его вершину, границы — ребра, а материки и острова — компоненты связности графа. Теперь попробуем определиться с понятием раскраски графа. Это произвольная функция f: VC, где V — множество вершин графа, а C={1, 2, 3, …, k} — конечное подмножество натуральных чисел. Более простым языком, функция раскраски f каждой вершине графа ставит в соответствие некоторое натуральное число (раскрашивает вершины цветами из определенной палитры). Если каждый цвет пронумеровать натуральным числом, то такой палитрой как раз и выступает множество С.

Отсюда можно заметить, что вершины графа можно раскрашивать как угодно: хоть все одним цветом. Напрашивается еще одно определение. Правильной раскраской графа называется такая его раскраска, когда любые его две смежные вершины раскрашены в разные цвета. То есть f(u)f(v) для любых двух смежных вершин u и v.

Давайте же попробуем научиться раскрашивать графы правильно :-)! Вместо названий цветов будем использовать натуральные числа. Метод правильного раскрашивания базируется на такой простой идее: раскрашивать очередную вершину в минимально возможный цвет. Для реализации метода мы используем множество цветов:

Получается, что каждой вершине будет приписан цвет в виде числа. Для этого введем переменную

которая покажет, что значение элемента Col[j] определяет номер цвета вершины j. Здесь j принадлежит множеству вершин {1, 2, …, N}, а Col — множеству цветов {1, 2, …, k} правильной раскраски графа. Очевидно, что kN.

Правильная раскраска получена. Давайте рассмотрим примерчик, который поможет нам осознать весь смысл алгоритма:

После запуска процедуры Colorize имеем на выходе массив Col:

Таблица

Таким образом, мы с вами научились раскрашивать графы правильно. К счастью, это еще не пик совершенства :-).

(Продолжение следует)

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © www.sector.biz.ua 2006-2015 design by Vadim Popov