22. Гамельтоновы цепи и циклы.

Постановка задачи

Дан граф, в нём найти цикл проходящий по всем вершинам с точностью один раз.Такой цикл- Гамельтонов.Если задача построения Эйлерова цикла решена то гамельтонова до сих пор не решна.Простая цепь проходящая по всем вешинам –Гамильтонова цепь .

Задача коммиваяжёра.

Дано N Городов , расстояние между ними . Найти цикл , проходяший по всем всем вершинам графа и имеющий миним. длину.

НАХОЖДЕНИЕ КРАТЧАЙШЕГО Г – ЦИКЛА

Т-МА:

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

- нач и конеч вершины максим. Простой цепи.

Следствие.

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

l>=n (предположение)

n=2 →L=1. Педположим n→L=n-1

L не равно n след-но в графе сущ гамельтонов цикл. Длинна макс. простой цепи

L≥n-1 L Не больше n-1 L=n-1

Полный граф –это все возможные связи.

Ρ(а)=n-1

n-1≥(1/2)n n>2

в полном графе всегда существует гамельтонов цикл.

(n-1)!/2 гамельтоновых циклов. В ориентиров. Граф можно пост. Задачу нахождения гамельтонового контура.

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

Граф содержит гамельтонову цепь если он не содержит контуров.

Ориентированный граф без цикла содерж. Гамельт. Цепь если он тотален.

Тотальный граф = если в нём для каждой пары различных вершин сущ. Путь

Связывающий эти вершины в как-нибудь из направлений.

Полный антисимметр.- тотальный . Если сущ путь то граф тотален.

23. Алгоритм Райяна решения задачи коммиваяжёра.

Применяем для решения в плоском графе. Плоский- если может быть изображен на плоскости. Для любого плоского графа миним локальная степень Ρмин(а)≤5. это использ. Для разбиения задачи на ряд более простых.Пусть в графе G необходимо построить гамельтонов цикл . Вершина мин локальной степени А0. Локк степень не превосходит 5. рассмотрим совокупность частей графа . Каждая частьвключ в точн 2 ребра инциндентных вершинеи все остальные рёбра. Таких частей не больше 10

Задача нахождения всех гамельтоновых циклов свод к зад нахожд гамельт циклов во всех частях графа . Множество гам цикл в графеG = обьединение

Множ гамельт циклов граф .Докажем что любой гамельтонов цикл графаG

явл. Гам. циклом в как-нибудь части . Если есть гам цикл вG то он проходит

через а0.

АЛГОРИТМ.

1). Строится по шагам простая цепь, проходящая по новым вршинам(без повторений). В качстве 1-й вершины выбираем а0

2). В качестве а1 выбирается одна из 2-х соседних вершин, имеющих мин лок стпень.-часть цепи.

Пусть часть простой цепи уже построена . ниодна из вершин не повтор.

Выбирам вершину удовлетв условию:

1). не должна совпадать ни с одной из ранее выбранных вершин, если только речь не идёт о выборе последней вершины.

2). Выбор не должен разбивать оставшееся вершинына 2

несвязные компоненты.

После выбора оставш верш , включая а0, можно было соединить путём инцидентн. ранее выбран. вершинам.

Существует неск вершин . Выбираем одну из них а остальные варианты запоминаем. Если нет такой вершины то в этой части нет гамельтонова цикла.

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

Гпмельтонова цикла здесь нету. В части в которой сущ гам цикл можно найти несколько гамельтоновых циклов.

Если кратчайший гам цикл то проще найти . т.к. нах некот. гам цикл. Можно прекратить если найдены большие гамельтоновы циклы , чем какие либо.