Теорема Кёнига
Теорема Кёнига
Введение
В этой главе мы рассмотрим теорему Кёнига в теории графов и посмотрим, как она может помочь нам в решении задач.
Формулировка теоремы Кёнига
Мы все знаем, что такое паросочетание в теории графов. Рассмотрим ещё одно понятие — вершинное покрытие (в частности, минимальное вершинное покрытие).
Вершинное покрытие
Вершинное покрытие в графе — это подмножество вершин
такое, что каждое ребро инцидентно хотя бы одной вершине из
(то есть ребро покрыто).
Минимальное вершинное покрытие — вершинное покрытие минимального размера.
Формулировка теоремы Кёнига
Пусть — двудольный граф.
