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

Презентация:



Advertisements
Похожие презентации
Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ.
Advertisements

Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ.
Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 СОЧЕТАНИЯ. РАЗМЕЩЕНИЯ. ЛЕКЦИЯ 17 С.В.ЧУМАЧЕНКО.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ГРАФОВ СПОСОБЫ.
ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Транспортные сети ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 15 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.
Оптимизация на графах Студент Гр. Пи-08 Пушной А.Б. КУРСОВАЯ РАБОТА.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
1 Исследование алгоритмов решения задачи k коммивояжеров Научный руководитель, проф., д.т.н. Исполнитель, аспирант Ю.Л. Костюк М.С. Пожидаев Томский государственный.
Научно -исследовательская работа Авторы: Быстрякова Наталья, Шайахметова Алина ученицы 9 В класса МАОУ « СОШ9» г.Нурлат, РТ Руководитель: Мустафина Наталья.
Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче.
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы.
Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Методы определения гамильтоновых циклов: метод перебора Робертса и Флореса. 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, добавление которой не приводит к преждевременному замыканию цикла.

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Эйлеровы и гамильтоновы графы Декабрь, Метод перебора Робертса и Флореса. 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б) следует предпринять возвращение. Гамильтоновы циклы, найденные к этому моменту, являются всеми гамильтоновыми циклами в графе

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

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

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

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

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

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