Изменения

Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>.

[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]В качестве примера рассмотрим граф H изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: <tex>M_1 =\{B, E, F\}</tex> и <tex>M_2 =Ребероне \{B, E, G\}</tex>.Пусть <tex>M_1' = M_1</tex> то <tex>U(M_1') = \{A, C, D, G\}</tex>. Пусть <tex>M_1'' = \{E, F\}</tex>. Тогда <tex>U(M_1'') =\{C, D, G\}</tex>.Отсюда <tex>|M_1'| \leqslant |U(M_1')|</tex> и <tex>|M_1''| \leqslant |U(M_1'')|</tex>. И это верно для любого подмножества <tex>M_1</tex>. Значит, <tex>M_1</tex> {{---}} внешнее покрытие. Значит и <tex>M_2</tex> {{---}} внешнее покрытие.<br> ==Реберное ядро в двудольном графе==