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

Во - первых, принятие решений, допускаемых обстоятельствами дела, некоторого одного, вполне определенного решения. Таким образом, характерной особенностью процесса принятия решения является множественность имеющихся вариантов. Ясно, что чем большим числом вариантов мы располагаем, тем более громоздким оказывается описание всей задачи. Очень часто условие задачи принятия решений могут быть описаны не несколькими отдельными числами, а лишь целыми таблицами чисел, иногда довольно обширными.

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

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

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

Эйлеровы циклы

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

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

как это показано на рисунке.

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

Основные понятия и определения

видно также, что эйлеровым может быть только связный граф.

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

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

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

Критерий существования эйлерова цикла

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

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

Доказательство.

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

Достаточность. Пусть G — связный неориентированный граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины x₀ и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину x₀ и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф — только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем x_i, являющуюся конечной вершиной какого-либо до сих пор не использованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (0 является четным числом), инцидентных каждой вершине.

Начиная теперь с x_i, получаем цикл Ф’, начинающийся и оканчивающийся в x_i. Если все оставшиеся ранее ребра использованы для цикла Ф’, то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x₀ до x_i, затем циклом Ф’ и, наконец, частью цикла Ф от вершины x_i до x₀. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф’ дает новый цикл Ф. Мы снова можем найти вершину x_j, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф’, начинавшегося в x_j, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.

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

Следствие #1.

Для связного эйлерова графа G множество ребер можно разбить на простые циклы.

Следствие #2.

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

Алгоритмы построения эйлерова цикла

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

Алгоритм построения эйлерова цикла в эйлеровом графе.

Вход: эйлеров граф G(V,E), заданный матрицей смежности. Для простоты укажем, что Г[v]— множество вершин, смежных с вершиной v.

Выход: последовательность вершин эйлерова цикла.

S:=Ø {стек для хранения вершин}

select v

V {произвольная вершина}

v→S {положить v в стек S}

while S≠Ø do

v←S; v→S {v — верхний элемент стека}

if Г[v]=Ø then

v←S;

yield v

else

select u

Г[v] {взять первую вершину из списка смежности}

u→S {положить u в стек}

Г[v]:=Г[v]\{u}; Г[u]:=Г[u]\{v} {удалить ребро (v,u)}

end if

end while

Обоснование алгоритма.

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

работа по Теория информационных процессов и систем на тему Алгоритм Фаулкса и его приложения (стр. 1 из 4)

Номер зачётной книжки: 17421412

Введение.

Эйлеровы циклы

Основные понятия и определения

Критерий существования эйлерова цикла

Алгоритмы построения эйлерова цикла