Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями
(Отмена правки 7464 участника 192.168.0.2 (обсуждение)) |
(→Паросочетание в двудольном графе) |
||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
− | |definition= '''Паросочетание''' в двудольном графе - произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины | + | |definition= '''Паросочетание''' <tex>M</tex> в двудольном графе - произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}} |
{{Определение | {{Определение | ||
− | |definition= Вершины двудольного графа, инцидентные ребрам <tex>M</tex>, называются '''покрытыми''', а неинцидентные - '''свободными'''.}} | + | |definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные - '''свободными'''.}} |
{{Определение | {{Определение | ||
|definition= '''Чередующаяся цепь''' - путь в двудольном графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} | |definition= '''Чередующаяся цепь''' - путь в двудольном графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} |
Версия 07:43, 16 апреля 2011
Паросочетание в двудольном графе
Определение: |
Паросочетание | в двудольном графе - произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.
Определение: |
Вершины двудольного графа, инцидентные ребрам паросочетания | , называются покрытыми, а неинцидентные - свободными.
Определение: |
Чередующаяся цепь - путь в двудольном графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию | , а другое нет.
Определение: |
Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны. |
Теорема о максимальном паросочетании и дополняющих цепях
Теорема: | ||||||
Паросочетание в двудольном графе является максимальным тогда и только тогда, когда в нет дополняющей цепи. | ||||||
Доказательство: | ||||||
Пусть в двудольном графе с максимальным паросочетанием существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть не являлось максимальным. Противоречие.
В доказательстве используются несколько новых понятий:
| ||||||
Литература
- Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2