Теорема Кёнига (комбинаторика): различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
→Окружение: убрал конечную вершину, т.к. у ребра их всего две и обе конечные |
Stannic (обсуждение | вклад) отмена правки участника 94.29.24.222 (обс.) оборот "конечная вершина ребра" используется по тексту |
||
Строка 6:
Граф называется двудольным, если его вершины можно разбить на два множества так, что у каждого ребра конечные вершины принадлежат разным множествам.
[[Задача о вершинном покрытии|Вершинное покрытие]] графа – это множество вершин, такое, что любое ребро графа имеет хотя бы одну конечную вершину из этого множества. Вершинное покрытие называется ''наименьшим'', если никакое другое вершинное покрытие не имеет меньшего числа вершин.
[[Паросочетание|Паросочетанием]] в графе называется множество рёбер, не имеющих общих конечных вершин. Паросочетание называется ''наибольшим'', если никакое другое паросочетание не содержит большего числа рёбер.
| |||