Граф Эйлера

Реферат 3 Введение 5 1 Описание алгоритма поиска эйлеровых циклов 7 1.1 Эйлеров путь и эйлеров цикл 7 1.2 Существование эйлеровых путей и эйлеровых циклов 8 1.2 Алгоритм Флери 10 2 Программная реализация 14 2.1 Инструкция программисту 14 2.2 Инструкция пользователю 17 2.3 Инструкция по установке 18 3 Тестирование программы 19 Заключение 23 Список использованных источников 24 Приложение 1. Исходный код программы 25

Введение

Теория графов – раздел дискретной математики, изучающий свойства графов. Одно из применений теории графов – дать единый формализм для многих совершенно разных задач, что позволит сформулировать алгоритмы решения этих задач в более общих терминах. Достижения дискретной математики в этом направлении поспособствовали появлению особого класса алгоритмов, так называемых графовых алгоритмов. В этих алгоритмах большую роль также играют вопросы структуры данных. Основная цель данной работы – изучить граф Эйлера (содержащий так называемый эйлеров цикл) и его различные аспекты в нашем реальном мире. Определение эйлерова цикла и других важнейших понятий рассматривается в основной части работы. Эйлеров граф нашел свое применение во многих ситуациях, возникающих в компьютерных науках, физике, коммуникационных технологиях, экономике и многих других областях, которые можно проанализировать с помощью методов теории графов. Граф Эйлера можно использовать для представления практически любой задачи, связанной с дискретным расположением объектов, когда речь идет не о внутренних свойствах этих объектов, а об их взаимосвязи. В частности, использование эйлеровых циклов особенно полезно при организации работы городского транспорта – снегоочистителей, автобусов и почтовых курьеров. В этих приложениях пересечение улиц более одного раза является пустой тратой ресурсов. Эйлеровы цклы представляют оптимальные решения с точки зрения сохранения ресурсов. Методы, подобные этим, были внедрены и привели к значительной экономии средств для участвующих муниципалитетов [1]. Таким образом, задача изучения особенностей работы эйлеровых циклов и программной реализации алгоритмов их поиска является актуальной задачей. Цель работы – на основе изучения особенностей алгоритмов поиска эйлеровых циклов реализовать пользовательское приложение. Исходя из цели курсовой работы, были поставлены следующие задачи: 1. Изучить основные понятия эйлеровых графов, рассмотреть идею работы и особенности алгоритма Флери для поиска эйлеровых циклов в неориентированных графах; 2. Разработать программу, реализующую алгоритм Флери. Объектом исследования является практическое применение теории графов для разработки программных средств. Предметом курсовой работы является алгоритмы поиска эйлеровых циклов и путей в неориентированных графах.

1 Описание алгоритма поиска эйлеровых циклов

Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек – вершин, представляющих основные элементы ситуации, и линий – ребер, соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки называются графами. Многие проблемы теоретического и прикладного характера могут быть сформулированы в терминах графовых моделей. Этим объясняется бурное развитие алгоритмической теории графов в XX веке. Кроме того, большое количество задач, встречающихся на олимпиадах по программированию, используют в решении алгоритмы на графах. Более формально, графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами). Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними). Граф называется неориентированным, если его ребра не имеют направлений. В ориентированном графе некоторая вершина может быть соединена с другой вершиной в определенном направлении, а обратное соединение при этом может отсутствовать. Схематично граф часто изображают точками на плоскости, причем соседние вершины соединены дугами (для ориентированного графа направление обычно отмечается стрелкой).

1.1 Эйлеров путь и эйлеров цикл

Неориентированный граф G может быть описан парой (V, E), где V – множество вершин, E – множество ребер графа, то есть соединений между парами вершин. Для графа G определена конечная последовательность ребер и вершин S = {a0, E0, a1, E1, …, En-1, an} такая, что каждые два соседних ребра Ei-1 и Ei имеют общую вершину ai. Последовательность S в таком случае называется путем в графе G. Здесь a0 является начальной, а an – конечной вершиной пути. Последовательность также может быть бесконечной: S = {…, a0, E0, a1, E1, …, En-1, an, …}. Необходимо также отметить, что одно и то же ребро может быть включено в путь неоднократно. Путь называется циклическим, если совпадают начальная и конечная вершины пути. Циклический путь называется циклом, если каждое ребро пути встречается не более одного раза (вершины могут быть включены многократно, в таком случае цикл чаще всего называют цепью). Эйлеров путь – это такой путь в графе, который посещает каждое ребро графа, включая его в набор ровно один раз. Эйлерова цепь, или эйлеров цикл – это эйлеров путь, который начинается и заканчивается в одной и той же вершине, то есть являющийся циклом. Граф называется эйлеровым, если он содержит эйлеров цикл. Как узнать, является ли данный граф эйлеровым или нет? Эту задачу можно сформулировать следующим образом: «можно ли нарисовать данный граф, не снимая карандаш с бумаги и не обводя ни одного ребра больше одного раза?». Граф называется эйлеровым, если он имеет эйлеров цикл, и называется полуэйлеровым, если он имеет эйлеров путь. Определить, является ли граф эйлеровым, можно за полиномиальное время со затратами O(V + Е), где V – множество вершин, E – множество ребер графа [2]. В следующем подразделе приведены некоторые интересные свойства неориентированных графов с эйлеровым путем и циклом. Эти свойства могут быть использованы для того, чтобы определить, является ли данный граф эйлеровым или нет.

1.2 Существование эйлеровых путей и эйлеровых циклов

Неориентированный граф имеет цикл Эйлера, если выполняются следующие два условия [3]: 1. Все вершины с ненулевой степенью являются смежными. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершины с нулевой степенью не принадлежат циклу Эйлера или пути (рассматриваются только все ребра). 2. Все вершины имеют четную степень. Неориентированный граф имеет путь Эйлера, если выполняются следующие два условия. 1. Такое же, как и первое условие для эйлерова цикла. 2. Если две вершины имеют нечетную степень, а все остальные вершины имеют четную степень. Следует обратить внимание, что наличие только одной вершины с нечетной степенью невозможно в неориентированном графе (сумма всех степеней всегда четна). Граф без ребер считается эйлеровым, потому что в нем нет никаких ребер для прохождения. Примеры графов рассматриваются ниже, на рисунках 1 – 3. Рисунок 1 – Полуэйлеров граф Граф на рисунке 1 имеет эйлеров путь, например, «4 3 0 1 2 0», но не имеет ни одного эйлерова цикла. В этом графе есть две вершины с нечетной степенью (4 и 0). Рисунок 2 – Эйлеров граф Граф на рисунке 2 имеет эйлеров цикл, например, «2 1 0 3 4 0 2». Все вершины графа имеют четную степень. Рисунок 3 – Граф, не являющийся эйлеровым или полуэйлеровым Граф на рисунке 3 не является эйлеровым или полуэйлеровым. В нем сразу четыре вершины имеют нечетную степень (0, 1, 3 и 4). 1.2 Алгоритм Флери Алгоритм Флери [4] позволяет не только обнаружить существование, но и получить полный цикл Эйлера. Идея заключается в том, чтобы «не сжигать мосты» – выполнять обход ребер с их вычеркиванием так, чтобы можно было вернуться к просмотренной ранее вершине и обойти оставшиеся ребра. Мостом графа G называется ребро x такое, что в G существуют вершины u и v, любой простой путь между которыми проходит через ребро x [5]. Простым путем называется путь, все вершины которого попарно различны (путь не проходит дважды через одну вершину). Суть алгоритма Флери состоит в следующей последовательности действий: 1. Убедиться, что в графе ровно две вершины с нечетной степенью либо все вершины имеют четную степень. 2. Если нет нечетных вершин, можно начать обход с любой вершины. Если есть ровно две нечетных вершины, необходимо начинать с одной из них. 3. Следует просматривать ребра по одному. Если есть выбор между мостом и обычным ребром без моста, всегда необходимо выбирать ребро без моста. 4. Продолжать до тех пор, пока все ребра не будут просмотрены. Способ, предложенный Флери, является простейшим методом в категории алгоритмов поиска эйлерова графа и выполняется за время O(|E|2), где E – множество ребер графа, что в данный момент является неэффективным в сравнении с другими алгоритмами (например, алгоритма на основе циклов, который работает также и для ориентированных графов). Ниже приводится пример работы алгоритма Флери [4]. На рисунке 4 изображен граф, в котором есть две вершины с нечетной степенью, 2 и 3, поэтому можно начать обход с любой из них, например, с вершины 2 (рисунок 5). Итак, из вершины 2 выходят три ребра, какое из них необходимо выбрать для вычеркивания? Нельзя выбрать ребро 2-3, потому что это мост (его вычеркивание не позволит вернуться к 3), поэтому можно выбрать любое из оставшихся двух ребер. Допустим, выбрано ребро 2-0. Его необходимо удалить и перейти к вершине 0 (рисунок 6). Рисунок 4 – Неориентированный граф с четырьмя вершинами и четырьмя ребрами Рисунок 5 – Стартовая вершина для поиска эйлерова цикла – вершина 2 Рисунок 6 – Граф после удаления ребра 2-0 Теперь осталось здесь только одно ребро из вершины 0, поэтому можно его удалить и перейти к вершине 1 (рисунок 7). Путь теперь имеет вид «2-0 0-1». Рисунок 7 – Граф после удаления ребра 0-1 Из вершины 1 есть только одно ребро, поэтому можно его удалить и перейти к вершине 2 (рисунок 8). Путь теперь имеет вид «2-0 0-1 1-2». Рисунок 8 – Граф после удаления ребра 1-2 По аналогии, у вершины 2 есть только одно ребро, поэтому его можно удалить и перейти к вершине 3. Путь теперь имеет вид «2-0 0-1 1-2 2-3». Больше нет ребер, поэтому алгоритм завершает свою работу. Итоговый путь – «2-0 0-1 1-2 2-3». Путь является эйлеровым, но не является циклом, и граф, таким образом, является полуэйлеровым.

2 Программная реализация

2.1 Инструкция программисту

Курсовая работа выполнена в интегрированной среде разработки Visual Studio 2019. Она является ведущей IDE для языка программирования С# и одной из самых популярных среди программистов под Windows. Стоит отметить, что в данной работе используется интерфейс для создания приложений с графическим пользовательским интерфейсом Windows.Form, доступный только в этой среде разработки. Предполагается, что заданный граф имеет эйлеров путь или цикл. Основное внимание уделяется нахождению эйлеровых путей и циклов в графе с непустым набором ребер. Граф представлен списком смежности и числом вершин; для добавления и удаления новых ребер используются функции addEdge и removeEdge соответственно. public class Graph { private int vertices; // число вершин private List<int>[] adj; // список ребер графа public Graph(int numOfVertices) { this.vertices = numOfVertices; initGraph(); } public Graph(){} private void initGraph() { adj = new List<int>[vertices]; for (int i = 0; i < vertices; i++) { adj[i] = new List<int>(); } } public void addEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); } public void removeEdge(int u, int v) { adj[u].Remove(v); adj[v].Remove(u); } }; Для проверки типа графа используется функция isEulerian, которая проверяет, является ли граф эйлеровым или полуэйлеровым. Функция возвращает одно из следующих значений: 0, если граф не является эйлеровым; 1, если граф имеет эйлеров путь (является полуэйлеровым); 2, если в графе есть цикл Эйлера (граф является эйлеровым). private int isEulerian() { // все ли вершины с ненулевой степенью являются смежными if (isConnected() == false) return 0; // посчитать число вершин с нечетной степенью int odd = 0; for (int i = 0; i < vertices; i++) if (adj[i].Count % 2 != 0) odd++; // если это число больше 2, граф не является ни эйлеровым, ни полуэйлеровым if (odd > 2) return 0; // если 2, то граф является полуэйлеровым. // если 0, то эйлеровым // для неориентированного графа количество не может быть равным 1 return (odd == 2) ? 1 : 2; } Алгоритм поиска состоит в следующем. Сначала находится начальная точка, которая должна быть вершиной с нечетной степенью (если есть такие вершины), и сохраняется в переменной u. Если искомых вершин нет, то начальной считается вершина 0. Затем выполняется вызов функции printEulerUtil для печати пути Эйлера, начинающегося с вершины u. Обходятся все смежные вершины с u, и, если есть только одна смежная вершина, то включается она. Если существует более одной смежной вершины, то смежная вершина v включается только в том случае, когда ребро u-v не является мостом. private void printEulerUtil(int u, ref string res) { for (int i = 0; i < adj[u].Count; i++) { int v = adj[u][i]; // если ребро u-v не является мостом, оно включается в результат if (isValidNextEdge(u, v)) { res += u + » -> » + v + System.Environment.NewLine; // ребро использовано, теперь его можно вычеркнуть removeEdge(u, v); // рекурсивный вызов для всех смежных вершин: printEulerUtil(v, ref res); } } } Как узнать, является ли данное ребро мостом? Посчитать количество вершин, достижимых из u. Ребро u-v удаляется, затем снова подсчитывается количество достижимых вершин из u. Если число достижимых вершин уменьшается, то ребро u-v является мостом. Для подсчета достижимых вершин можно использовать обход графа в глубину или в ширину (в данной работе был использован поиск в глубину). Функция dfsCount (u) возвращает количество вершин, достижимых из u. private int dfsCount(int v, bool[] isVisited) { isVisited[v] = true; int count = 1; foreach (int i in adj[v]) { if (!isVisited[i]) { count = count + dfsCount(i, isVisited); } } return count; } Как только ребро обработано (включено в эйлеров путь), оно удаляется из набора ребер графа. Чтобы удалить ребро, запись вершины заменяется на -1 в списке смежности. Простое удаление узла может не сработать, поскольку код является рекурсивным, а вызов родителя может быть в середине списка смежности. Полный исходный код программы представлен в приложении 1.

2.2 Инструкция пользователю

Приложение поставляется в виде единственного исполняемого файла «FleuryProject.exe». Программное средство реализует алгоритм Флери поиска эйлерова цикла в заданном графе; с помощью интерфейса Windows.Form пользователю будет предложено ввести количество вершин графа, а также задать соединения вершин для всех ребер. По нажатию кнопки «Найти эйлеров цикл» будет выполнен алгоритм, который запишет в текстовое поле тип графа (содержит эйлеров путь, эйлеров цикл или не содержит ни того, ни другого), а также эйлеров путь или эйлеров цикл в зависимости от типа заданного графа.

2.3 Инструкция по установке

Установка приложения не требуется; для запуска необходимо запустить исполняемый файл FleuryProject.exe двойным щелчком мыши.

3 Тестирование программы

Как было упомянуто в подразделе 2.1, в программе используется интерфейс Windows Forms. Для работы программы необходимо задать количество вершин, а также заполнить граф списком ребер, выбрав числовые значения (номера соответствующих ребру From-To вершин From и To) в соответствующих регуляторах типа «вверх-вниз» (см. рисунок 9). Рисунок 9 – Окно программы при запуске После ввода значения количества вершин необходимо нажать кнопку «Установить», в результате чего кнопка добавления ребер «Добавить», кнопка удаления ребер «Удалить» и кнопка для выполнения задания «Найти эйлеров цикл» станут активными (рисунок 10). Затем предлагается добавить информацию о дугах графа. Регуляторы с заголовками «From» и «To» представляют числовые значения u, v, описывающие дугу (u, v) задаваемого графа. После ввода каждой дуги по нажатию на кнопку «Добавить» в таблице в левой верхней части окна отображается информация о добавленных ребрах. Рисунок 10 – Окно программы после ввода количества вершин графа и (после нажатия кнопки «Установить») После нажатия на кнопку «Найти эйлеров цикл» будет выведена информация о типе графа и найденный путь (при его наличии), как показано на рисунке 11. Здесь для проверки работы программы был взят полуэйлеров граф из рисунка 4. Для получения новых результатов необходимо сбросить заданные значения нажатием кнопки «Очистить» – это позволить очистить текстовое поле и поля таблицы, а также сделать неактивными кнопки добавления ребер и вывода результатов. После проведенного тестирования программа выдает правильный ответ и не имеет проблем с выполнением алгоритма, как следует из рисунков 12 (проверка для эйлерова графа) и 13 (проверка для графа, не являющегося эйлеровым или полуэйлеровым). Рисунок 11 – Окно программы после вывода результатов для полуэйлерова графа Рисунок 12 – Окно программы после вывода результатов для эйлерова графа Рисунок 13 – Окно программы после вывода результатов для графа, который не является ни эйлеровым, ни полуэйлеровым

Заключение

В данной курсовой работе были рассмотрены основные понятия эйлеровых графов, а также проанализирован алгоритм Флери для поиска эйлеровых циклов, изучен псевдокод алгоритма, произведена оценка его вычислительной сложности. Также был рассмотрен пример работы алгоритма Флери для неориентированного графа и выполнена реализация алгоритма на языке высокого уровня C# в виде оконного приложения Windows.Forms. Также были достигнуты поставленные задачи – описан алгоритм и разработан его программный код. Разработанная на языке C# программа отлажена и протестирована. Корректность работы программы подтверждается полученными результатами – выходные данные программы полностью соответствуют ожидаемым. Описанный в приложении 1 исходный код позволяет расширить функциональные возможности программы – входные данные могут быть не только считаны с клавиатуры, но и введены из текстового файла. Эйлеровы и полуэйлеровы графы активно используются в различных областях знаний, находя широкое применение в многочисленных научных и практических приложениях.

Список использованных источников

1. Subramanian K. G., Hasni Roslan and Ismail Abdul Samad [2009]: Some applications of Eulerian graphs International Journal of Mathematical Science Education, Vol. 2, Series 2, pp. 1 – 10. 2. В. Алексеев, В. Таланов, Курс «Графы и алгоритмы», Лекция № 2 «Маршруты, связность, расстояния»: Маршруты и связность в орграфах // Интуит.ру, 27.09.2006 3. Кристофидес Н. Теория графов. Алгоритмический подход (глава 9.5) — М.: Мир, 1978. 4. Fleury’s Algorithm for printing Eulerian Path or Circuit [Электронный ресурс] / URL: https://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/ (Дата обращения: 24.01.2021) 5. Mikkel Thorup. Near-optimal fully[sic]-dynamic graph connectivity // Proceeding STOC ’00 Proceedings of the thirty-second annual ACM symposium on Theory of computing. — Portland: Association for Computing Machinery, 2000. — С. 343–350. — DOI:10.1145/335305.335345.