Теорема Кёнига (комбинаторика)
В теории графов теорема Кёнига (теорема Кёнига-Эгервари, венгерская теорема[1]), доказанная Денешем Кёнигом в 1931[2], утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931[3], Йенё Эгервари[англ.] в несколько более общем виде для случая взвешенных графов.
Граф называется двудольным, если его вершины можно разбить на два множества так, что у каждого ребра конечные вершины принадлежат разным множествам.
Вершинное покрытие графа — это множество вершин, такое, что любое ребро графа имеет хотя бы одну конечную вершину из этого множества. Вершинное покрытие называется наименьшим, если никакое другое вершинное покрытие не имеет меньшего числа вершин.
Паросочетанием в графе называется множество рёбер, не имеющих общих конечных вершин. Паросочетание называется наибольшим, если никакое другое паросочетание не содержит большего числа рёбер.
В любом двудольном графе число рёбер в наибольшем паросочетании равно числу вершин в наименьшем вершинном покрытии.
Двудольный граф на рисунке вверху имеет по 7 вершин в каждой из долей. Паросочетание с 6 рёбрами выделено синим цветом, а вершинное покрытие выделено красным. Это покрытие является наименьшим по размеру, поскольку любая вершина в покрытии должна включать по меньшей мере одну конечную вершину ребра паросочетания. Таким же образом, нет паросочетания большего размера, поскольку любое ребро паросочетания должно содержать по меньшей мере одну конечную вершину из вершинного покрытия, так что это паросочетание является наибольшим. Теорема Кёнига как раз и утверждает равенство размеров паросочетания и покрытия (в данном примере оба числа равны шести).
