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