200
правок
Изменения
→Реберное ядро в двудольном графе
|statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
=== Примеры ===Рассмотрим двудольные графы <tex>G_1</tex> и <tex>G_2</tex>, изображенные на рисунке. В графе <tex>G_1</tex> пусть <tex>S_1 = \{v_3, v_6\}</tex> и <tex>T_1 = \{v_1, v_2, v_4, v_5, v_7 \}</tex>. Этот граф имеет единственное наименьшее вершинное покрытие <tex>M_1 = \{v_3, v_6\}</tex> и, поскольку <tex>M_1 об T_1 = пуст</tex>, он полунесводимый; сдеовательно, он совпадает со своим рёберным графом. В графе <tex>G_2</tex> пусть <tex>S_2 = \{u_1, u_4, u_5\}</tex>...
== См. также ==
