200
правок
Изменения
→Реберное ядро в двудольном графе
==Реберное ядро в двудольном графе==
Здесь и далее будем рассматривать [[Двудольные графы|двудольный граф ]] <tex>G</tex>, в котором обозначим <tex>S</tex> {{---}} множество вершин левой доли, <tex>T</tex> {{---}} множество вершин правой доли.
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
