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

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

2 дейкстра Условие 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

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

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

5 Клика 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 города выходит дорог

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

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

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

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

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

11 Хроматический полином Цикла/Цепи. 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

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

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

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

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

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

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

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

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

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

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