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