![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).
Если наибольшая из степеней вершин графа равна Р, то этот граф Р+1 -раскрашиваем.
K-раскрашиваемый граф — граф, хроматическое число которого не превосходит K. То есть его вершины можно раскрасить K разными цветами так, что у любого ребра концы будут разного цвета.
K-хроматический граф — граф, хроматическое число которого равно K. То есть вершины графа можно раскрасить K цветами так, что у любого ребра концы будут разного цвета, но так раскрасить K − 1 цветами — уже нельзя.
Билет 11
Дата публикования: 2015-02-22; Прочитано: 273 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!