Изменения

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