200
правок
Изменения
→Примеры
=== Примеры ===
[[File:Bipartite_graph_1.png|thumb|170px|Двудольный граф <tex>G_1</tex>]]
[[File:Bipartite_graph_2.png|thumb|170px|Двудольный граф <tex>G_2</tex>]]
Рассмотрим двудольные графы <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> {{---}} несводимый граф и, значит, совпадает со своим рёберным ядром.
<br>
