Изменения
Нет описания правки
{{Определение
|definition=
'''Дефицитом''' (англ. ''deficiency'') графа G мы будем называть величину: <br>
<tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>, <br>
где <tex>\alpha (G)</tex> - размер [[Теорема о максимальном паросочетании и дополняющих цепях|максимального поросочетания]] в <tex>G</tex>, а <br>
{{Определение
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' (англ. ''neighbors'')<tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
}}
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
# <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
# <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>(англ. ''maximum matching in G'')
}}
{{Определение
|definition=
Граф <tex>G</tex> называется '''Фактор-критическим'''(англ. ''Factor-Critical Graph''), если для любой вершины <tex>v \in G</tex> в графе <tex>G</tex> существует полное паросочетание, не покрываеющее <tex>v</tex>.
}}
