Пусть дан граф G = (X,E) без изолированных вершин.
• Определение №1: ( Вершинное покрытие ) [В.П.]
Подмножество Z из X вершин графа G называется вершинным покрытием графа, если любое ребро графа инцидентно по крайней мере одной вершине из Z.
• Определение №2: ( Минимальное В.П. )
Вершинное покрытие называется минимальным, если оно не содержит другого вершинного покрытия графа.
• Определение №3: ( Наименьшее В.П. )
Вершинное покрытие наименьшей мощности называется наименьшим.
• Определение №4: ( Число В.П. )
Мощность наименьшего В.П. графа называется числом вершинного покрытия графа.
Обозначается: "бетта_0"(G)
-> Пример:
Z1 = {x_2, x_4, x_5} (наименьшее)
Z2 = {x_1, x_2, x_3, x_5, x_7} (минимальное)
"бетта_0"(G) = 3
*** Теорема о соотношении "альфа_0"(G) и "бетта_0"(G) ***
-> Следующий результат показывает взаимодействие между независимыми множествами графа и вершинными покрытиями этого графа:
• Теорема :
Подмножество вершин Z графа G является (наименьшим, минимальным) вершинным покрытием графа <=> когда подмножество X\Z (наибольшее, максимальное) независимое множество графа,
=> "альфа_0"(G) + "бетта_0"(G) = n