Паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | * Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | ||
[[Категория:Неориентированные графы]] | |||
[[Категория:Основные термины]] | |||
Текущая версия от 17:07, 20 ноября 2024
Паросочетание (Matching) — произвольное подмножество попарно несмежных ребер графа. Паросочетание называется максимальным, если оно не содержится в паросочетании с большим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа.
Другое название — Независимое множество ребер.
См. также
- Вершинно-реберное инцидентное паросочетание,
- Правильное паросочетание,
- Совершенное паросочетание,
- Частичное паросочетание,
- Взаимные паросочетания.
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.