- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ДМ граф презентация
Содержание
- 1. ДМ граф
- 2. дейкстраУсловие b+c (a+d+c)/3 |a-b|+1 o c+1 3d+1
- 3. Цепь.Цикл. n=1 n=2 n=3
- 4. Дерево n=1 n=2 n=3
- 5. Клика n=1 n=2 n=3
- 6. Клика n городов n-1 дорога n(n-1)
- 7. Доказательство по индукции n-1 -доказано Докажем для
- 8. Примеры Клик
- 9. Хроматический полином.
- 10. Хроматический полином.
- 11. Хроматический полином Цикла/Цепи. n=1 n=2
- 12. 4-верш гр. по d mod 7/9 посчитать
- 13. Найти количество раскрасок в k цветов 5ти-верш
- 14. Определение Хроматическое число графа — минимальное
- 15. Двудольный г. U1 U5 U6
- 16. Проблема четырёх красок Раскрасить карту в минимальное число цветов
- 17. Двойственность Двойственный граф –
- 18. Задача – матрица инцидентности восстановите
- 19. Эйлеров граф Полуэйлеров граф (содержащий эйлеров путь(цепь)) кёнигсберг
- 20. Планарность Граф иокасаэдра
- 21. Гамильтонов граф/цикл /путь. Гамильтонов путь выделенн красным
Слайд 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
B
L
D
C
E
H
L
F
K
L
N
G
2b
Слайд 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 города
выходит
дорог
Слайд 7Доказательство по индукции
n-1 -доказано
Докажем для n вершин
В дереве n≥2 вершин есть
Удалим лист с ребром
Получим дерево n-1 вершин
n-2 рёбер
Вновь прибавив 1 вершину и ребро
получим n вершин
n-1 ребро
n=1
Формула верна
Иначе сумма степеней 2n
подразумевает n рёбер
(все вершины степени ≥2)
n-1 вершин
n-2 рёбер
противоречие
Слайд 9Хроматический полином.
=
исх граф
Без ребра
Убираем варианты с одинаковыми раскрасками
-
Вершины отождествлены
Разложение по Оn
=
-
=
=
-
-
-
=
-
-
-
-
-
-
-
=
-
-
-
-
-
-
+
-
+
-
+
-
+
-
=
-
+
-
-
+
-
+
=
Слайд 10Хроматический полином.
=
исх граф
Без ребра
Прибавляя считаем все варианты с одинаковыми раскрасками
+
Вершины отождествлены
Разложение
=
+
=
=
+
+
+
=
=
=
Граф с ребром
+
+
+
=
=
=
=
=
=
+
=
+
+
+
+
Слайд 11Хроматический полином Цикла/Цепи.
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n
Итого k(k-1)n-1 способов
цепь
n вершин
k способов
k-1 способ
k-1 способ
k-1 способ
k-1 способ
k-1
k-1 способ
k-1 способ
k-1 способ
k-1 способ
k способов
k-1 способ
k-1 способ
k-1 способ
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
Слайд 13Найти количество раскрасок в k цветов 5ти-верш графы вар по d mod
1
2
3
4
5
6
7
8
10
11
9
12
13
14
15
16
Слайд 14
Определение
Хроматическое число графа — минимальное число k, такое что множество V
таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.
Двойственный граф
Слайд 17Двойственность
Двойственный граф – это граф, у которого количество вершин равно количеству
В изоморфном графе ребро восстанавливается в том случае, если в исходном графе рёбра смежные.
X1
X2
X4
X3
X5
U1
U2
U3
U4
U5
U8
U7
U6
U1
U2
U3
U4
U5
U6
U7
U8
Слайд 18Задача – матрица инцидентности
восстановите граф и определите следующие характеристики.
Число вершин
Ребер
Компонент связности
Цикломатическое
Хроматическое число
Эйлеров
Полу-Эйлеров
