🗊Презентация Характеристические числа графов

Категория: Математика
Нажмите для полного просмотра!
Характеристические числа графов, слайд №1Характеристические числа графов, слайд №2Характеристические числа графов, слайд №3Характеристические числа графов, слайд №4Характеристические числа графов, слайд №5Характеристические числа графов, слайд №6Характеристические числа графов, слайд №7Характеристические числа графов, слайд №8Характеристические числа графов, слайд №9Характеристические числа графов, слайд №10Характеристические числа графов, слайд №11Характеристические числа графов, слайд №12Характеристические числа графов, слайд №13Характеристические числа графов, слайд №14Характеристические числа графов, слайд №15Характеристические числа графов, слайд №16Характеристические числа графов, слайд №17Характеристические числа графов, слайд №18Характеристические числа графов, слайд №19Характеристические числа графов, слайд №20Характеристические числа графов, слайд №21Характеристические числа графов, слайд №22Характеристические числа графов, слайд №23
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Характеристические числа графов. Доклад-сообщение содержит 23 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Дискретная математика Характеристические числа графов
Описание слайда:
Дискретная математика Характеристические числа графов

Слайд 2


Цикломатическое число Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.
Описание слайда:
Цикломатическое число Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.

Слайд 3


Цикломатическое число Рис. 1 Рис. 2
Описание слайда:
Цикломатическое число Рис. 1 Рис. 2

Слайд 4


Цикломатическое число Цикломатическое число графа G находится по формуле:
Описание слайда:
Цикломатическое число Цикломатическое число графа G находится по формуле:

Слайд 5


Цикломатическое число Замечание 1. Цикломатическое число дерева равно 0. Замечание 2. Цикломатическое число леса равно 0. Замечание 3. Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.
Описание слайда:
Цикломатическое число Замечание 1. Цикломатическое число дерева равно 0. Замечание 2. Цикломатическое число леса равно 0. Замечание 3. Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.

Слайд 6


Цикломатическое число Пример 1.
Описание слайда:
Цикломатическое число Пример 1.

Слайд 7


Цикломатическое число Пример 2.
Описание слайда:
Цикломатическое число Пример 2.

Слайд 8


Число внутренней устойчивости Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны. Число внутренней устойчивости:
Описание слайда:
Число внутренней устойчивости Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны. Число внутренней устойчивости:

Слайд 9


Число внутренней устойчивости
Описание слайда:
Число внутренней устойчивости

Слайд 10


Число внешней устойчивости Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества ┐Q ведут ребра в вершины множества Q. Число внутренней устойчивости:
Описание слайда:
Число внешней устойчивости Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества ┐Q ведут ребра в вершины множества Q. Число внутренней устойчивости:

Слайд 11


Число внешней устойчивости
Описание слайда:
Число внешней устойчивости

Слайд 12


Хроматическое число Граф G называется h- хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные (различные) вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.
Описание слайда:
Хроматическое число Граф G называется h- хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные (различные) вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.

Слайд 13


Хроматическое число
Описание слайда:
Хроматическое число

Слайд 14


Хроматическое индекс Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежные ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.
Описание слайда:
Хроматическое индекс Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежные ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.

Слайд 15


Хроматическое индекс Согласно теореме Визинга, если максимальная локальная степень вершины графа равна k, то хроматический индекс подчиняется условию:
Описание слайда:
Хроматическое индекс Согласно теореме Визинга, если максимальная локальная степень вершины графа равна k, то хроматический индекс подчиняется условию:

Слайд 16


Хроматическое число
Описание слайда:
Хроматическое число

Слайд 17


Пример 1 В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть источники излучения. Если источники расположены в пунктах Xi и Xj влияют друг на друга (поражают друг друга), то на графе они соединены ребром (Xi, Xj). Можно ли расположить в каких-либо из данных пунктов 4 или 3 источника, не поражающих друг друга?
Описание слайда:
Пример 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 расположены так, как показано на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.
Описание слайда:
Пример 2 Объекты Х1, Х2, … , Х9 расположены так, как показано на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.

Слайд 20


Характеристические числа графов, слайд №20
Описание слайда:

Слайд 21


Пример 3. Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту. Пример 3. Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту.
Описание слайда:
Пример 3. Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту. Пример 3. Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту.

Слайд 22


Заменим страны на вершины, а границы между ними на ребра. Найдем хроматическое число графа. Заменим страны на вершины, а границы между ними на ребра. Найдем хроматическое число графа. χ(G) = 3.
Описание слайда:
Заменим страны на вершины, а границы между ними на ребра. Найдем хроматическое число графа. Заменим страны на вершины, а границы между ними на ребра. Найдем хроматическое число графа. χ(G) = 3.

Слайд 23


Раскраска карты в три цвета Раскраска карты в три цвета
Описание слайда:
Раскраска карты в три цвета Раскраска карты в три цвета

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию