Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Дискретная математика
Содержание
- 1. Дискретная математика
- 2. Цикломатическое числоЦикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.
- 3. Цикломатическое число Рис. 1
- 4. Цикломатическое числоЦикломатическое число графа G находится по формуле:
- 5. Цикломатическое числоЗамечание 1. Цикломатическое число дерева равно
- 6. Цикломатическое числоПример 1.
- 7. Цикломатическое числоПример 2.
- 8. Число внутренней устойчивостиВнутренне устойчивым множеством графа G
- 9. Число внутренней устойчивости
- 10. Число внешней устойчивостиВнешне устойчивым множеством графа G
- 11. Число внешней устойчивости
- 12. Хроматическое числоГраф G называется h- хроматическим, если
- 13. Хроматическое число
- 14. Хроматическое индексГраф G называется k-раскрашиваемым, если его
- 15. Хроматическое индексСогласно теореме Визинга, если максимальная локальная
- 16. Хроматическое число
- 17. Пример 1В пунктах Х1, Х2, Х3, Х4,
- 18. Слайд 18
- 19. Пример 2Объекты Х1, Х2, … , Х9
- 20. Слайд 20
- 21. Пример 3. Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту.
- 22. Заменим страны на вершины,
- 23. Раскраска карты в три цвета
- 24. Скачать презентанцию
Цикломатическое числоЦикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.
Слайды и текст этой презентации
Слайд 2Цикломатическое число
Цикломатическим числом графа G называется число ребер, которые надо
убрать, что бы граф стал ацикличным.
Слайд 5Цикломатическое число
Замечание 1. Цикломатическое число дерева равно 0.
Замечание 2. Цикломатическое
число леса равно 0.
Замечание 3. Если цикломатическое число графа равно
1, то в графе ровно 1 цикл.
Слайд 8Число внутренней устойчивости
Внутренне устойчивым множеством графа G называется множество вершин
S, все вершины которого попарно несмежны.
Число внутренней устойчивости:
Слайд 10Число внешней устойчивости
Внешне устойчивым множеством графа G называется множество вершин
Q, таких, что из всех вершин множества ┐Q ведут ребра
в вершины множества Q.Число внутренней устойчивости:
Слайд 12Хроматическое число
Граф G называется h- хроматическим, если его вершины можно
раскрасить h различными красками так, чтобы никакие две смежные (различные)
вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.
Слайд 14Хроматическое индекс
Граф G называется k-раскрашиваемым, если его ребра можно раскрасить
k различными красками так, чтобы никакие два смежные ребра не
были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.
Слайд 15Хроматическое индекс
Согласно теореме Визинга, если максимальная локальная степень вершины графа
равна k, то хроматический индекс подчиняется условию:
Слайд 17Пример 1
В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут
быть источники излучения. Если источники расположены в пунктах Xi и
Xj влияют друг на друга (поражают друг друга), то на графе они соединены ребром (Xi, Xj). Можно ли расположить в каких-либо из данных пунктов 4 или 3 источника, не поражающих друг друга?
Слайд 18
Надо найти
максимальное
внутренне
устойчивое
множество.
S1={X2, X5}, S2={X1, X4}, S3={X3, X6},
S4={X1, X3, X5}.
Слайд 19Пример 2
Объекты Х1, Х2, … , Х9 расположены так, как
показано на графе. Объекты, которые просматриваются друг из друга соединены
ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.
Слайд 21Пример 3. Дана политическая карта континента. Найти минимальное число цветов,
чтобы раскрасить карту.
Слайд 22 Заменим страны на вершины, а границы между
ними на ребра. Найдем хроматическое число графа.
χ(G) = 3.
