Изменения

=== Примеры ===

Рассмотрим двудольные графы <tex>G_1</tex> и <tex>G_2</tex>, изображенные на рисунках 1 и 2. В графе <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 \cap T_1 = \varnothing</tex>, он полунесводимый; следовательно, он совпадает со своим рёберным ядром. В графе <tex>G_2</tex> пусть <tex>S_2 = \{u_1, u_4, u_5\}</tex> и <tex>T_2 = \{u_2, u_3, u_6\}</tex>. В нём два наименьших вершинных покрытия, именно <tex>M_2 = \{u_1,u_4, u_5\}</tex> и <tex>N_2 = \{u_2, u_3, u_6\}</tex>. Так как <tex>M_2 \cap T_2 = \varnothing</tex> и <tex>N_2 \cap S_2 = \varnothing</tex>, то <tex>G_2</tex> {{---}} несводимый граф и, значит, совпадает со своим рёберным ядром.

== См. также ==