Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлены примеры для определений)
м (ё)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|id=matching_def
 
|id=matching_def
|definition= '''Паросочетание''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}
+
|definition= '''Паросочетание''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}
 
{{Определение
 
{{Определение
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}  
+
|definition= Вершины двудольного графа, инцидентные рёбрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}  
 
{{Определение
 
{{Определение
|definition= '''Числом реберного покрытия''' (англ. ''edge covering number'') называется размер минимального реберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}}
+
|definition= '''Числом рёберного покрытия''' (англ. ''edge covering number'') называется размер минимального рёберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}}
 
{{Определение
 
{{Определение
|definition= Число ребер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}
+
|definition= Число рёбер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}
 
{{Определение
 
{{Определение
|definition= '''Максимальное паросочетание''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания.}}
+
|definition= '''Максимальное паросочетание''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.}}
 
Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.
 
Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.
  
Строка 17: Строка 17:
 
|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ.''perfect matching''), если оно покрывает все вершины графа.}}
 
|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ.''perfect matching''), если оно покрывает все вершины графа.}}
 
{{Определение
 
{{Определение
|definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
+
|definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
 
{{Определение
 
{{Определение
 
|definition= '''Дополняющая цепь (или увеличивающая цепь)''' (англ. ''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}}
 
|definition= '''Дополняющая цепь (или увеличивающая цепь)''' (англ. ''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}}
Строка 33: Строка 33:
 
{|align="center"
 
{|align="center"
 
  |-valign="center"
 
  |-valign="center"
  |[[Файл: Maximal matching.jpg|thumb|210px|<font color=red>красные ребра</font> являются ребрами максимального паросочетания]]
+
  |[[Файл: Maximal matching.jpg|thumb|210px|<font color=red>красные рёбра</font> являются рёбрами максимального паросочетания]]
  |[[Файл: Perfect_matching.jpg|thumb|245px|<font color=red>красные ребра</font> являются ребрами полного паросочетания.]]
+
  |[[Файл: Perfect_matching.jpg|thumb|245px|<font color=red>красные рёбра</font> являются рёбрами полного паросочетания.]]
  |[[Файл: Alternating_path.jpg|thumb|210px|Пусть <font color=red>красные ребра</font> принадлежат паросочетанию <tex>M</tex>, а <font color=blue>синие</font> не принадлежат, тогда чередующаяся цепь: <tex>1-8-4-6-3-7</tex>]]
+
  |[[Файл: Alternating_path.jpg|thumb|210px|Пусть <font color=red>красные рёбра</font> принадлежат паросочетанию <tex>M</tex>, а <font color=blue>синие</font> не принадлежат, тогда чередующаяся цепь: <tex>1-8-4-6-3-7</tex>]]
 
  |}
 
  |}
  
Строка 47: Строка 47:
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
+
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль неё все рёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{---}} не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> {{---}} другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности {{---}} путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.
+
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{---}} не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> {{---}} другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством рёбер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум рёбрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности {{---}} путь или цикл. В каждом из этих путей и циклов чередуются рёбра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой рёбер из <tex>M'</tex> содержится больше, чем рёбер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.
 
}}
 
}}
  

Версия 22:11, 22 января 2017

Паросочетание в двудольном графе

Определение:
Паросочетание (англ. matсhing) [math]M[/math] в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.


Определение:
Вершины двудольного графа, инцидентные рёбрам паросочетания [math]M[/math], называются покрытыми (англ. matched), а неинцидентные — свободными (англ. unmatched).


Определение:
Числом рёберного покрытия (англ. edge covering number) называется размер минимального рёберного покрытии графа [math]G[/math] и обозначается через [math]\rho(G)[/math].


Определение:
Число рёбер в наибольшем паросочетании графа [math]G[/math] называется числом паросочетания (англ. matching number).


Определение:
Максимальное паросочетание (англ. maximal matching) — это такое паросочетание [math]M[/math] в графе [math]G[/math], которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.

Другими словами, паросочетание [math]M[/math] графа [math]G[/math] является максимальным, если любое ребро в [math]G[/math] имеет непустое пересечение по крайней мере с одним ребром из [math]M[/math].


Определение:
Паросочетание [math]M[/math] графа [math]G[/math] называется совершенным (или полным) (англ.perfect matching), если оно покрывает все вершины графа.


Определение:
Чередующаяся цепь (англ. alternating path) — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.


Определение:
Дополняющая цепь (или увеличивающая цепь) (англ. augmenting path) — чередующаяся цепь, у которой оба конца свободны.


Определение:
Уменьшающая цепь (англ. reduce path) — чередующаяся цепь, у которой оба конца покрыты.


Определение:
Сбалансированная цепь (англ. balanced path) — чередующаяся цепь, у которой один конец свободен, а другой покрыт.


Свойства

В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны [math]|V|/2[/math].

Пример максимального и полного паросочетания, чередующейся цепи

красные рёбра являются рёбрами максимального паросочетания
красные рёбра являются рёбрами полного паросочетания.
Пусть красные рёбра принадлежат паросочетанию [math]M[/math], а синие не принадлежат, тогда чередующаяся цепь: [math]1-8-4-6-3-7[/math]

Теорема о максимальном паросочетании и дополняющих цепях

Теорема:
Паросочетание [math]M[/math] в двудольном графе [math]G[/math] является максимальным тогда и только тогда, когда в [math]G[/math] нет дополняющей цепи.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Пусть в двудольном графе [math]G[/math] с максимальным паросочетанием [math]M[/math] существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль неё все рёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть [math]M[/math] не являлось максимальным. Противоречие.

[math]\Leftarrow[/math]

Рассмотрим паросочетание [math]M[/math] в графе [math]G[/math] и предположим, что [math]M[/math] — не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно [math]M[/math]. Пусть [math]M'[/math] — другое паросочетание и [math]|M'|\gt |M|[/math]. Рассмотрим подграф [math]H[/math] графа [math]G[/math], образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний [math]M[/math], [math]M'[/math]. Иначе говоря, множеством рёбер графа [math]H[/math] является симметрическая разность [math]M\oplus M'[/math]. В графе [math]H[/math] каждая вершина инцидентна не более чем двум рёбрам (одному из [math]M[/math] и одному из [math]M'[/math] ), т.е. имеет степень не более двух. В таком графе каждая компонента связности — путь или цикл. В каждом из этих путей и циклов чередуются рёбра из [math]M[/math] и [math]M'[/math]. Так как [math]|M'|\gt |M|[/math], имеется компонента, в которой рёбер из [math]M'[/math] содержится больше, чем рёбер из [math]M[/math]. Это может быть только путь, у которого оба концевых ребра принадлежат [math]M'[/math]. Заметим, что относительно [math]M[/math] этот путь является увеличивающей (дополняющей) цепью.
[math]\triangleleft[/math]

Источники информации