Наши Партнеры:

 


Главная > Самоучители > Теория графов > Определить число вершинного покрытия графа. Пример решения.

Определить число вершинного покрытия графа. Пример решения.

Определить число вершинного покрытия графа


Множество вершин графа G, покрывающее все рёбра, называется вершинным покрытием. Наименьшее число вершин во всех вершинных покрытиях называется числом вершинного покрытия и обозначается .
Из статьи Алгоритм Магу-Вейсмана возьмем:

минимальные наборы:

И дают нам наименьшие вершинные покрытия, т.е.
Например: