4433443
Beschreibung
Karteikarten von Sergei Fomin, aktualisiert more than 1 year ago
|
Erstellt von Sergei Fomin
vor fast 9 Jahre
|
|
| Frage | Antworten |
| 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. |
Möchten Sie mit GoConqr kostenlos Ihre eigenen Karteikarten erstellen? Mehr erfahren.