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

Description

Карточки по седьмой лекции курса "Основы теории графов" на stepic.org
Sergei Fomin
Flashcards by Sergei Fomin, updated more than 1 year ago
Sergei Fomin
Created by Sergei Fomin about 8 years ago
55
1

Resource summary

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.
Show full summary Hide full summary

Similar

3. Связность в графах
Sergei Fomin
4. Связность в графах (ч. 2)
Sergei Fomin
2. Циклы в графах
Sergei Fomin
Деление двузначного числа на двузначное
Эльвира Шемякина
Доли и дроби
Татьяна Иващенко
Тест 1- събиране и изваждане на числата до 6
Светла Събева
Събиране и изваждане до 6
Светла Събева
Собирање и одземање до 1000 без премин
Vanco Petrusevski
Tablica za umnovenie s 3
marsies marsies
Множества - основные определения
Анна Лисицкая
Обыкновенные дроби
Анна Лисицкая