Характеристические числа графов

Сентябрь 13, 2022

Главная
Математика
Характеристические числа графов

Содержание

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

Слайд 2

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

что бы граф стал ацикличным.

Слайд 3

Цикломатическое число
Рис. 1 Рис. 2

Слайд 4

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

Слайд 5

Цикломатическое число
Замечание 1. Цикломатическое число дерева равно 0.
Замечание 2. Цикломатическое число

леса равно 0.
Замечание 3. Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.

Слайд 6

Цикломатическое число
Пример 1.

Слайд 7

Цикломатическое число
Пример 2.

Слайд 8

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

все вершины которого попарно несмежны.
Число внутренней устойчивости:

Слайд 9

Число внутренней устойчивости

Слайд 10

Число внешней устойчивости
Внешне устойчивым множеством графа G называется множество вершин Q,

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

Слайд 11

Число внешней устойчивости

Слайд 12

Хроматическое число
Граф G называется h- хроматическим, если его вершины можно раскрасить

h различными красками так, чтобы никакие две смежные (различные) вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.

Слайд 13

Хроматическое число

Слайд 14

Хроматическое индекс
Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k

различными красками так, чтобы никакие два смежные ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.

Слайд 15

Хроматическое индекс
Согласно теореме Визинга, если максимальная локальная степень вершины графа равна

k, то хроматический индекс подчиняется условию:

Слайд 16

Хроматическое число

Слайд 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 расположены так, как показано

на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.

Слайд 20

Слайд 21

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

раскрасить карту.

Слайд 22

Заменим страны на вершины, а границы между ними на ребра.

Найдем хроматическое число графа.
χ(G) = 3.

Характеристические числа графов

Содержание

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

Цикломатическое числоРис. 1 Рис. 2

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

Цикломатическое числоЗамечание 1. Цикломатическое число дерева равно 0.Замечание 2. Цикломатическое число

Цикломатическое числоПример 1.

Цикломатическое числоПример 2.

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

Число внутренней устойчивости

Число внешней устойчивостиВнешне устойчивым множеством графа G называется множество вершин Q,

Число внешней устойчивости

Хроматическое числоГраф G называется h- хроматическим, если его вершины можно раскрасить

Хроматическое число

Хроматическое индексГраф G называется k-раскрашиваемым, если его ребра можно раскрасить k

Хроматическое индексСогласно теореме Визинга, если максимальная локальная степень вершины графа равна

Хроматическое число

Пример 1В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть

Надо найти максимальное внутренне устойчивое множество.S1={X2, X5}, S2={X1,

Пример 2Объекты Х1, Х2, … , Х9 расположены так, как показано

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

Заменим страны на вершины, а границы между ними на ребра.

Похожие презентации

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

Цикломатическое число
Рис. 1 Рис. 2

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

Цикломатическое число
Замечание 1. Цикломатическое число дерева равно 0.
Замечание 2. Цикломатическое число

Цикломатическое число
Пример 1.

Цикломатическое число
Пример 2.

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

Число внешней устойчивости
Внешне устойчивым множеством графа G называется множество вершин Q,

Хроматическое число
Граф G называется h- хроматическим, если его вершины можно раскрасить

Хроматическое индекс
Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k

Хроматическое индекс
Согласно теореме Визинга, если максимальная локальная степень вершины графа равна

Пример 1
В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть

Надо найти
максимальное
внутренне
устойчивое
множество.
S1={X2, X5}, S2={X1,

Пример 2
Объекты Х1, Х2, … , Х9 расположены так, как показано