Лекция: Ядро графа
Множество внешней устойчивости — такое множество вершин графа, что:
1) либо вершины принадлежат этому множеству.
2) либо они имеют дуги в этом множестве.
Это определение легче усвоить и запомнить, если отдавать себе отчет, что внешне устойчивое множество, прежде всего, определяется вершинами графа, которые в это множество не входят (пункт 2).
Множество всех вершин графа внешне устойчиво (подпадает под пункт 1). Поэтому интерес представляют минимально возможные множества внешней устойчивости.
Поиск внешне устойчивого множества происходит в другой классической задаче:
Как расставить минимальное число ферзей, чтобы все поля доски были под боем.
Для решения этой задачи также используется соответствующий алгоритм Магу.
Возьмем граф из предыдущего примера:
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ||||||
| d | ||||||
| e | ||||||
| f |
Алгоритм Магу.
1. По главной диагонали проставляем 1.
2. Выписываем построчные дизъюнкции.
(a Ú c)(a Ú b Ú e)(c Ú f)(b Ú e)(c Ú e)(b Ú d Ú e Ú f)
3. Преобразуем в ДНФ, выполнив все возможные поглощения и операции идемпотентности.
Получим: acd Ú aef Ú bc Ú ce
Эти конъюнкции и дают множества внешней устойчивости.
.{a, c, d}, {a, e, f}, {b, c}, {c, e}
Минимальное из них дает число внешней устойчивости (здесь 2).
Множества, одновременно внутренне и внешне устойчивые называются ядром графа.
Для рассмотренного графа — {b, c}
В графе может быть несколько ядер (например — 2)
или не быть совсем.
Клика
Клика — максимально большой полный подграф данного графа.
a
f b
e c
d
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ||||||
| d | ||||||
| e | ||||||
| f |
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ||||||
| d | ||||||
| e | ||||||
| f |