ДМ граф Ж.Алгоритм Дп Управление проектом задание характеристики раскраска Эйлеровость Гамильтоновы графы Кривошеев О.И. МЭСИ, каф. Прикладной математики.

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



Advertisements
Похожие презентации
1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936.
Advertisements

Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Глава III. ТЕОРИЯ ГРАФОВ Граф – диаграмма связей между объектами. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Многие.
Задачи раскраски графов А.В.Пяткин. Вершинная раскраска Раскрасить вершины графа в минимальное число цветов так, чтобы смежные вершины получали бы разные.
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
NP-полные задачи. Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да»
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
Тема: Графы Преподаватель Белгородцева Н.А. Дискретная математика.
ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.
Задача Эйлера То, что не получилось на рисунке, не является доказательством невозможности соединения дорожками домиков и колодцев. Для доказательства воспользуемся.
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Эйлеровы графы. Гамильтоновы графы G.
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Транксрипт:

ДМ граф Ж.Алгоритм Дп_Управление проектом задание характеристики раскраска Эйлеровость Гамильтоновы графы Кривошеев О.И. МЭСИ, каф. Прикладной математики

дейкстра Условие b+c (a+d+c)/3 |a-b|+1 o c+1 3d+1 c+d 3b 3d-1 3(d+c+1 3d-1 a+10 3a d+1 |4-c| b+c 5+a b a+b+c 8-a+b D BL D C EH L F K L N G 2b

Цепь.Цикл. n=1n=2n=3n=4n=5n=6n=7n=8n Итого n-1 рёбер цепь n рёбер

Дерево n=1n=2n=3n=4n=5n=6n=7n=8n Итого n-1 рёбер переклеим

Клика n=1 n=2 n=3 n=4 n=5 r=0 r=1 r=3 n городов Полный граф r=6 r=10 n-1 дорога n(n-1) каждая дорога работает на 2 города выходит дорог

Клика n городов n-1 дорога n(n-1) каждая дорога работает на 2 города выходит дорог

Доказательство по индукции n-1 -доказано Докажем для n вершин В дереве n2 вершин есть хоть 1 лист Удалим лист с ребром Получим дерево n-1 вершин n-2 рёбер Вновь прибавив 1 вершину и ребро получим n вершинn-1 ребро n=1 Формула верна Иначе сумма степеней 2n подразумевает n рёбер (все вершины степени 2) n-1 вершин n-2 рёбер противоречие

Примеры Клик. Пустые графы раскраски Граф икосаэдра

Хроматический полином. = исх граф Без ребра Убираем варианты с одинаковыми раскрасками - Вершины отождествлены Разложение по О n – пустым графам = - = = - -- = = = =

Хроматический полином. = исх граф Без ребра Прибавляя считаем все варианты с одинаковыми раскрасками + Вершины отождествлены Разложение по кликам = + = = + ++ = == Граф с ребром +++ = = = = = = + =

Хроматический полином Цикла/Цепи. n=1n=2n=3n=4n=5n=6n=7n=8 n Итого k(k-1) n-1 способов цепь n вершин k способов k-1 способ k способов k-1 способ цепьn вершин Цикл - цепьn-1 вершина = = k(k-1) n-1 - k(k-1) n-2 = (k-1-1) х k(k-1) n-2 = k(k-2) (k-1) n-2

4 - верш гр. по d mod 7/9 посчитать по K n, O n сопоставить результат Не брать

Найти количество раскрасок в k цветов 5 ти - верш графы вар по d mod 12 посчитать по K n, O n сопоставить результат

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

Двудольный г. U1U1 U5U5 U6U6

Проблема четырёх красок Раскрасить карту в минимальное число цветов

Двойственность Двойственный граф – это граф, у которого количество вершин равно количеству рёбер исходного графа. В изоморфном графе ребро восстанавливается в том случае, если в исходном графе рёбра смежные. X1X1 X2X2 X4X4X3X3 X5X5 U1U1 U2U2 U3U3 U4U4 U5U5 U8U8 U7U7 U6U6 U1U1 U2U2 U3U3 U4U4 U5U5 U6U6 U7U7 U8U8

Задача – матрица инцидентности восстановите граф и определите следующие характеристики. 1. Число вершин 2. Ребер 3. Компонент связности 4. Цикломатическое число 5. Хроматическое число 6. Эйлеров 7.Полу-Эйлеров

Эйлеров граф Полуэйлеров граф (содержащий эйлеров путь(цепь)) кёнигсберг

Планарность Граф икосаэдра

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