Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел. 7021 326, е-mail: ri@kture.kharkov.ua 1 ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ГРАФОВ ЭЙЛЕРОВЫ. - презентация

1 Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ГРАФОВ ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ГРАФЫ ЛЕКЦИЯ 21 С.В.ЧУМАЧЕНКО Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ

2 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Тема: Эйлеровы и гамильтоновы графы Цель лекции – исследование вопросов построения эйлеровых и гамильтоновых циклов для решения задач оптимизации на графах Содержание: Понятие эйлерова цикла и графа Критерии и алгоритмы определения эйлеровых графов Применение эйлеровых графов Гамильтоновы циклы и графы Методы определения гамильтоновых циклов Применение гамильтоновых графов Сравнительный анализ эйлеровых и гамильтоновых графов

3 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, С Харари Ф. Теория графов: Пер. с англ. / под ред. Гаврилова. М.: Мир, С Новиков Ф.А. Дискретная математика для программистов. С.-П., С Бондаренко М.Ф., Кривуля Г.Ф., Рябцев В.Г., Фрадков С.А., Хаханов В.И. Проектирование и диагностика компьютерных систем и сетей. К.: НМЦ ВО с. Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу Дискретна математика. Харків, ХНУРЕ с. Семенец В.В., Хаханов В.И., Хаханова И.В. Проектирование цифровых систем с использованием языка VHDL. Харьков, с. Литература

4 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Термины Базовые понятия: множество граф маршрут цикл смежность инцидентность степень вершины Ключевые слова: эйлерова цепь эйлеров цикл эйлеров/полуэйлеров граф гамильтонов цикл гамильтонов граф

5 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, n Граф называется эйлеровым, если он содержит эйлеров цикл Эйлеров цикл замкнутый маршрут, который включает каждое ребро графа только один раз (вершины могут повторяться) n Пример n abcdefcghea Определение эйлерова цикла и графа

6 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, n Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения всех четырех частей суши в задаче о кенигсбергских мостах (1736) Из истории теории графов

7 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, n Задача может быть решена в другой постановке: если в граф добавить еще одно ребро, то можно составить маршрут, включающий каждое из ребер только один раз, который начинается в одной из вершин и заканчивается в другой n ABCDCBDAB n ABDCDABCB n Такой маршрут представляет собой эйлерову цепь n Граф, содержащий эйлерову цепь, называется полуэйлеровым Эйлерова цепь

8 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, n Эйлеровы цепи и степени вершин n Эйлеровы циклы и степени вершин Критерий эйлеровости графа. 1

9 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Граф является эйлеровым тогда и только тогда, когда все его вершины имеют четную степень: G= эйлеров v V degv=2n, n N n Если в графе имеется две вершины нечетной степени, то существует эйлерова цепь, которая начинается в одной из них и заканчивается в другой. При этом граф называется полуэйлеровым Критерий эйлеровости графа. 2

10 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Алгоритм Флери n Алгоритм построения эйлерова цикла: 1.Выбор произвольной вершины р с последующим вычеркиванием пройденного ребра 2.Запрещается проход по ребру, если его удаление приводит к разбиению графа на два компонента связности

11 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Применение эйлеровых графов Эйлеровы графы применяются в задачах: n доставки (товаров, почты, услуг), где требуется определить маршрут, проходящий один раз по каждой из улиц. Задача состоит в нахождении пути, минимизирующего общую длину, время или стоимость; n инспектирования распределенных систем, где необходима проверка электрических, телефонных, железнодорожных, других линий; n коммунального хозяйства и планирования; n теории игр и в головоломках; n компьютерной инженерии и управления

12 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Определение негативного влияния соседних ячеек памяти на запоминание информации в тестируемой ячейке осуществляется путем построения графовой модели и решения на ней задачи построения эйлерова цикла n Базовая запоминающая ячейка n Соседство взаимодействующих ячеек пятого порядка n Соседство взаимодействующих ячеек девятого порядка n Смежные ячейки n Будем рассматривать два типа смежных ячеек, расположенных по кресту и по квадрату относительно базовой Применение эйлеровых графов в задачах КИУ: методы обнаружения отказов в соседствах взаимодействующих ячеек Ñîñåäñòâо âçàèìîäåéñòâóþùèõ ÿ÷ååê 5-ãî è 9-ãî ïîðÿäêîâ

13 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Применение эйлеровых графов в задачах КИУ Соседства взаимодействующих ячеек 5-го и 9-го порядков Смежные образцы – комбинации состояний смежных ячеек Рассматриваются смежные образцы для соседства взаимодействующих ячеек 5-го и 9-го порядков Пассивные смежные образцы (ПСО) Активные смежные образцы (АСО)

14 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Эйлеров обход двоичного куба. 1 Все АСО и ПСО можно сформировать при помощи графа, дуги которого соединяют состояния запоминающих ячеек, различающиеся только в одной позиции. Формирование всех АСО и ПСО эквивалентно нахождению контура графа, в котором каждая дуга встречается только один раз. Такие контуры называются эйлеровыми. Направленный граф для трех запоминающих ячеек

15 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Эйлеров обход двоичного куба. 2 набора

16 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Time-Out

17 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Гамильтоновы циклы в графах n Граф называется гамильтоновым, если он имеет гамильтонов цикл n Цикл называется гамильтоновым, если он содержит каждую вершину только один раз, при этом не обязательно все ребра графа должны включаться в обход Гамильтонов граф Негамильтонов граф

18 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, n Понятие гамильтонова цикла впервые появилось в связи с задачей о кругосветном путешествии, которую рассматривал Уильям Гамильтон: обойти все вершины графа столицы различных стран по одному разу и вернуться в исходный пункт n Для 20 государств задача представляет обход всех вершин додекаэдра n Историческая справка

19 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Методы определения гамильтоновых циклов: метод перебора Робертса и Флореса. 1 Для графа G= составляется матрица переходов М=||m ij || размера k n: k=max deg _ v i, v i V, n=|V| m ij i-я вершина v q, если в графе существует дуга из вершины v i в вершину v q. Вершины можно упорядочить произвольно, образовав элементы j-го столбца матрицы М. К составляемой гамильтоновой цепи добавляется первая вершина в столбце v 1 (например, вершина a). Затем к цепи добавляется первая возможная вершина (например, b) в столбце a, затем c – в столбце b и т.д. Под возможной понимается вершина, еще не принадлежащая гамильтоновой цепи S, добавление которой не приводит к преждевременному замыканию цикла.

20 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Метод перебора Робертса и Флореса. 2 На r-м шаге имеем S={ v 1, a, b, c,..., v r-1, v r }. Существуют две причины, препятствующие включению очередной вершины: 1.В столбце v r нет возможной вершины; 2.Цепь, определяемая множеством S, имеет длину n-1, т.е. является гамильтоновой, тогда а) в графе существует замыкающая дуга (v r,v 1 ), следовательно, найден гамильтонов цикл; б) в графе не существует замыкающей дуги (v r,v 1 ), следовательно, гамильтонов цикл не может быть получен. В случаях 1 и 2б) следует предпринять возвращение. Гамильтоновы циклы, найденные к этому моменту, являются всеми гамильтоновыми циклами в графе

21 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Пример реализации метода перебора n Для графа G= составляется матрица переходов М n По матрице переходов строятся гамильтоновы цепи из вершины а a b d c e a a d c b e a

22 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Применение гамильтоновых графов. Связь с задачей коммивояжера n Задача о нахождении гамильтонова цикла на взвешенном графе известна как задача коммивояжера Приложения: n задачи упорядочивания или планирования операций; n составление расписаний; n выполнение операций на ЭВМ; n проектирование электрических и компьютерных сетей; n управление автоматизированными линиями; n тестирование ОЗУ и распределенной памяти; n синтез тестов проверки цифровых систем; диагностирование неисправностей вычислительных систем и сетей

23 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Эйлеровы графы n Определены необходимые и достаточные условия существования эйлеровых циклов n Существуют эффективные алгоритмы отыскания эйлеровых циклов n Эйлеровы графы встречаются редко n Эйлеровы графы менее востребованы Гамильтоновы графы n Критерии не известны, но достаточные условия существуют n Алгоритмы поиска гамильтонова цикла в графе достаточно трудоемки n Почти все графы, встречающиеся в теории и практике, гамильтоновы n Гамильтоновы графы более востребованы на практике Сравнительный анализ и связь эйлеровых и гамильтоновых графов

24 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Выводы n Введены понятия эйлерова и гамильтонова циклов в графах n Выявлены закономерности существования эйлеровых цепей и циклов n Сформулированы критерии существования эйлеровых циклов n Изучены алгоритмы и методы определения эйлеровых и гамильтоновых циклов в графах n Рассмотрены возможности применения эйлеровых и гамильтоновых графов для оптимизационных задач n Приведены примеры решения практических задач методами теории графов n Проведен сравнительный анализ рассмотренных графов

25 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Тест-вопросы Какой граф является гамильтоновым? а б в 2. Эйлеров цикл графа содержит а) каждое ребро только один раз; б) каждую вершину только один раз; в) проходит через все вершины и ребра только один раз. 3. Гамильтонов цикл графа содержит а) каждое ребро только один раз; б) каждую вершину только один раз; в) проходит через все вершины и ребра только один раз. 4. В эйлеровом графе все вершины: а) нечетной степени; б) четной степени. 5. В полуэйлеровом графе допускается а) 3 вершины нечетной степени; б) 2 вершины нечетной степени; в) 1 вершина нечетной степени.

26 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Тест-вопросы Какой алгоритм определяет гамильтоновы циклы: а) Гильберта-Мура; б) Робертса и Флореса; в) Дейкстры; г) Флери? 7. Какой из графов является эйлеровым (полуэйлеровым)? аб 8. Какой алгоритм определяет эйлеровы циклы: а) Гильберта-Мура; б) Робертса и Флореса; в) Дейкстры; г) Флери? 9. Какой из графов является эйлеровым (а и/или б), полуэйлеровыми (а и/или б), гамильтоновыми (а и/или б)? а б