работа на тему: Алгоритм Фаулкса и его приложения (стр. 2 из 3)
Это свойство выражается наличием единиц во всем столбце D и нулей во всей строке D (очевидно, за исключением их пересечения).
Может наблюдаться и обратная ситуация: если для некоторой точки вся строка состоит из единиц и весь столбец, за исключением пересечения, состоит из нулей, эта точка является началом каждого гамильтонова пути (если таковой существует).
Матрицу графа можно упростить вычеркивая предварительно все пары строк и столбцов, которым необходимо соответствует либо начало, либо конец каждого гамильтонова пути.
Так, в настоящем случае строка и столбец D могут быть заранее опущены; мы получаем матрицу М 1 . образуем элементарные произведения элементов какой-нибудь строки (например, строки А) на элементы какого-нибудь столбца (скажем С), как если бы мы хотели вычислить М 1[2].Элементарные произведения в порядке их следования таковы:
а) 1*0=0; б) 1*1=1; в) 0*1-0; г) 0*0=0; д) 1*0=0. проследим, что они означают. Пусть мы хотим отправиться из А в С.
Тогда:
а) не существует прямого пути из А в С;
б) существует прямой путь, идущий из А в B и путь из B в C; следовательно имеется путь длины 2 из А в С;
в) не существует прямого пути из А в С;
г) нет прямого пути из А в Е и так же нет пути из Е в С;
д) есть прямой путь из А в F, но нет ни какого пути из F в С.
Таким образом, мы получили все пути из А в С длины меньшей или равной 2.
Так же мы ищем пути, связывающие различные точки графа, то вместо образования арифметической суммы, как в обычном матричном произведении, мы составим булеву сумму.
Таким образом, мы приходим к матрице М 1[2] , все единицы которой обозначают существование путей единицы меньшей или равной 2, а нули - их отсутствие.
 |
Из матрицы М 1[2] мы заключаем, что точка С необходимо является крайней точкой гамильтонова пути, если таковой существует. Опять отбрасываем строку и столбец С, откуда получаем.
 |
Точно так же, как мы, вычислив М 11[2] , нашли пути длины меньшей или равной 2, найдем пути длины меньшей или равной 3, вычисляя М 11[3] . Матрица М 1[8] М 11[3] содержит только единицы; это доказывает существование путей длины меньшей или равной 3 между всеми точками ABEF, взятыми по две.
В частности, можно идти из Е в А через B и F. Вычислять М 11[4] которая, очевидно, содержит только единицы, уже нет смысла.
Вообще, когда вычисляют последовательные символические степени М, можно остановиться на том n для которого
М(n+1) = М (n)
ибо это означает, что в М не существует пути, длина которого превышает n. Матрица М [3] , полученная возвращением на место строк и столбцов C и D, может быть перегруппирована таким образом, чтобы все нули были расположены под главной диагональю, а единицы – над ней.
Квадратные матрицы, состоящие из единиц опирающихся на главную диагональ, образуют классы эквивалентности относительно закона: точка Х связана с точкой Y и обратно.
 |
Например, А связанная с Е через B или же через F и B; Е связанная с А через В и F. Мы упростим исходный граф, разбив его на классы. Определение единственного гамельтонова пути AFEBCD становится совсем простым (рис 16.5).
 |
Возвращаясь к задаче Фреголи, которую мы решили выше, мы устанавливаем, что вычисление М [2] дало нам пути длины <= 2, вычисление М [4] - пути длины <= 4. Если бы мы вычислили М [7] , мы имели бы пути длины <= 7; в действительности мы вычислили М [8] , которая дает все пути, ибо каждый путь длины больше 7 проходит два раза через одну точку. Мы констатировали совпадении М [8] и М [4] .
Затем мы нашли классы эквивалентности, представляя М [4] в форме ABDFGCEH; в частности, BDF и EH образуют классы эквивалентности.
Замечание
Очевидно, что когда записывают отношения порядка (как, например, отношения предшествования) в некотором множестве, алгорифм Фаулкса представляет собой один из методов выяснения их совместимости (поскольку не должно существовать цикла). Он позволяет, кроме того, найти все отношения порядка между двумя, которые выводятся из предположений в силу транзитивности отношения порядка (из А<B и В<С следует, что А<С, хотя это отношение не было явно выражено ранее).
Только тогда, когда между точками нет связи виде отношения, можно вводить законно отношение индифферентности ><.
Зато на практике часто приходится иметь дело с соотношением частичного упорядочения, допускающим циклы. В этом случае этот алгорифм дает нам метод, хорошо приспособленный для решения задач.
Гамильтоновы циклы
Название «гамильтонов цикл» произошло от задачи «Кругосветноепутешествие» предложенной ирландским математиком Вильямом Гамильтоном в
1859 году. Нужно было, выйдя из исходной вершины графа, обойти все еговершины и вернуться в исходную точку. Граф представлял собой укладкудодекаэдра, каждой из 20 вершин графа было приписано название крупногогорода мира.
Основные понятия и определения
Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.
Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеконе в каждом графе.
Замечание.
Любой граф G можно превратить в гамильтонов граф, добавив достаточноеколичество вершин. Для этого, например, достаточно к вершинам v1,…,vp графа
G добавить вершины u1,…,up и множество ребер {(vi,ui)}[pic]{(ui,vi+1)}.
Степенью вершины v называется число ребер d(v), инцидентных ей, приэтом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим.
Условия существования гамильтонова цикла
В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной.
Большинство известных фактов имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.
Теорема Дирака. Если в графе G(V,E) c n вершинами (n ? 3) выполняется условие d(v) ? n/2 для любого v[pic]V, то граф G является гамильтоновым.
Доказательство.
От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u1, … ,un, соединяя их со всеми вершинами G так, чтобы G’:= G + u1 + … + un был гамильтоновым.
Пусть v, u1, w, … ,v — гамильтонов цикл в графе G’, причем v[pic]G,u1[pic]G’, u1[pic]G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда w[pic]G, w
[pic] {u1,…,un}, иначе вершина u1 была бы не нужна. Более того, вершина vнесмежна с вершиной w, иначе вершина u1 была бы не нужна.
Далее, если в цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взявпоследовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w.
Но для любой вершины w графа G d(w) ? p/2+n по построению, в том числе d(v)
? p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1.
Таким образом, имеем: n+p-1 = d(v)+d(V) ? d(w)+d(v) ? p/2+n+p/2+n = 2n+p.
Следовательно, 0 ? n+1, что противоречит тому, что n > 0.
Теорема Оре. Если число вершин графа G(V,E) n ? 3 и для любых двух несмежных вершин u и v выполняется неравенство: d(u)+d(v) ? n и [pic](u,v)[pic]E, то граф G — гамильтонов.
Граф G имеет гамильтонов цикл если выполняется одно из следующихусловий:
Условие Поша: d(vk) ? k+1 для k < n/2.
Условие Бонди: из d(vi) ? i и d(vk) ? k => d(vi)+d(vk)?n (k?i)
Условие Хватала: из d(vk) ? k ? n/2 => d(vn-k) ? n-k.
Далее, известно, что почти все графы гамильтоновы, то есть где H(p) — множество гамильтоновых графов с p вершинами, а G(p) —множество всех графов с p вершинами. Таким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего несуществует) эффективный алгоритм решения.
Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.
[pic]
N = 8; d(vi) = 3; 3 ? 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)
Задачи связанные с поиском гамильтоновых циклов
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен быть перенастроен после того как был произведен продукт pi (но до того как начато производство продукта pj), в зависимости от комбинации (pi,pj). Стоимость перенастройки аппаратуры постоянна и независит от производимых продуктов. Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле производство первого продукта.