Паросочетание: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) |
Tosha (обсуждение | вклад) |
||
Строка 40:
== Свойства ==
*В любом графе без изолированных вершин число паросочетания и [[Рёберное покрытие|число рёберного покрытия]] в сумме дают число вершин<ref>{{статья
|автор= Tibor Gallai
|заглавие=Über extreme Punkt- und Kantenmengen
Строка 46:
|том=2
|страницы=133–138
|год=1959}}</ref>.
**В Если ''A'' и ''B'' — два максимальных паросочетания, то |''A''| ≤ 2|''B''| и |''B''| ≤ 2|''A''|. Чтобы это увидеть, заметьте, что каждое ребро из ''B'' \ ''A'' может быть сопряжено максимум двум рёбрам из ''A'' \ ''B'' поскольку ''A'' — паросочетание. Однако каждое ребро ''A'' \ ''B'' сопряжено с ребром ''B'' \ ''A'' ввиду того, что ''B'' — максимальное. Следовательно,▼
: <math>|A \setminus B| \le 2|B \setminus A|</math>▼
Далее мы имеем▼
: <math>|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|</math>▼
▲*Если ''A'' и ''B'' — два максимальных паросочетания, то |''A''| ≤ 2|''B''| и |''B''| ≤ 2|''A''|. Чтобы это увидеть, заметьте, что каждое ребро из ''B'' \ ''A'' может быть сопряжено максимум двум рёбрам из ''A'' \ ''B'' поскольку ''A'' — паросочетание. Однако каждое ребро ''A'' \ ''B'' сопряжено с ребром ''B'' \ ''A'' ввиду того, что ''B'' — максимальное. Следовательно,
▲*: <math>|A \setminus B| \le 2|B \setminus A|</math>
▲:Далее мы имеем
▲:: <math>|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|</math>
В частности, отсюда вытекает, что любое максимальное паросочетание является 2-аппроксимацией наибольшего паросочетания, а также 2-аппроксимацией минимального максимального паросочетания. Это неравенство точное. Например, если ''G'' — путь с тремя рёбрами и 4 вершинами, минимальный размер максимального паросочетания равен 1, а размер наибольшего паросочетания равен 2.
| |||