4433443
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| k-раскрашиваемый граф | Граф, допускающий правильную раскраску в k цветов. Правильная раскраска - такая, при которой каждое ребро соединяет вершины разных цветов. |
| Хроматическое число графа | Минимальное количество цветов, в которое можно правильно раскрасить данный граф |
| Верхняя оценка на хроматическое число графа (теорема Брукса) | Пусть d - максимальная степень вершины в графе. Тогда Х(G) <= d+1 в общем случае или X(G) <= d, если граф не полный и не цикл нечётное длины |
| Нижняя оценка на хроматическое число графа | Пусть w(G) - кол-во вершин в максимальной клике графа. Клика - полный подграф G. Тогда w(G) <= X(G) |
| Теорема Мицельского | Для любого сколь угодно большого k найдётся k-хроматический граф, свободный от треугольников. Вывод: отсутствие клики большого размера не гарантирует низкое хроматическое число. |
| Конструкция Мицельского | Добавим к множеству X вершин G множество Y, и соединим yi со всеми вершинами, смежными xi. Также добавим вершину z и соединим её со всеми yi. Такой граф свободен от треугольников (если изначальный был свободен) и имеет хроматическое число, на единицу большее, чем у исходного графа. |
| Хроматический многочлен графа | Этот многочлен P(z) равен количеству способов раскрасить данный конкретный граф в z цветов. |
| Лемма о хроматическом многочлене | Хроматический многочлен графа равен многочлену его подграфа с удалённым ребром e минус хроматический многочлен графа, полученного стягиванием ребра e. |
Want to create your own Flashcards for free with GoConqr? Learn more.