7. Раскраска графов

Sergei Fomin
Flashcards by , created over 3 years ago

Карточки по седьмой лекции курса "Основы теории графов" на stepic.org

26
1
0
Sergei Fomin
Created by Sergei Fomin over 3 years ago
Tablica za umnovenie s 3
marsies marsies
Математически задачи с числата до 5
Светла Събева
Собирање и одземање до 1000 без премин
Vanco Petrusevski
OCR Biology AS level (f211) flashcards/revision notes
Dariush Zarrabi
Leaving Certificate Japanese Kanji
Sarah Egan
4. Связность в графах (ч. 2)
Sergei Fomin
3. Связность в графах
Sergei Fomin
2. Циклы в графах
Sergei Fomin
Доли и дроби
Татьяна Иващенко
Събиране и изваждане до 6
Светла Събева
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.