Flashcards
7. Раскраска графов
Cards in this deck (8)
- 1k-раскрашиваемый графГраф, допускающий правильную раскраску в k цветов. Правильная раскраска - такая, при которой каждое ребро соединяет вершины разных цветов.
- 2Хроматическое число графаМинимальное количество цветов, в которое можно правильно раскрасить данный граф
- 3Верхняя оценка на хроматическое число графа (теорема Брукса)Пусть d - максимальная степень вершины в графе. Тогда Х(G) <= d+1 в общем случае или X(G) <= d, если граф не полный и не цикл нечётное длины
- 4Нижняя оценка на хроматическое число графаПусть w(G) - кол-во вершин в максимальной клике графа. Клика - полный подграф G. Тогда w(G) <= X(G)
- 5Теорема МицельскогоДля любого сколь угодно большого k найдётся k-хроматический граф, свободный от треугольников.
Вывод: отсутствие клики большого размера не гарантирует низкое хроматическое число. - 6Конструкция МицельскогоДобавим к множеству X вершин G множество Y, и соединим yi со всеми вершинами, смежными xi. Также добавим вершину z и соединим её со всеми yi. Такой граф свободен от треугольников (если изначальный был свободен) и имеет хроматическое число, на единицу большее, чем у исходного графа.
- 7Хроматический многочлен графаЭтот многочлен P(z) равен количеству способов раскрасить данный конкретный граф в z цветов.
- 8Лемма о хроматическом многочленеХроматический многочлен графа равен многочлену его подграфа с удалённым ребром e минус хроматический многочлен графа, полученного стягиванием ребра e.
Information
- Description
- Карточки по седьмой лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 110
- Tags
- Rating