Лекция: Теоремы о подструктурах графа

Пусть для любого графа G=(V,E) будут

n=|V|,

a(G) – число независимости,

r(G) – число реберного покрытия,

t(G)– число вершинного покрытия,

n(G) – число паросочетания,

тогда

· a(G) + t(G) =n

· n(G) + r(G) =n, если граф G не имеет изолированных вершин.

Справедливы следующие утверждения:

1. Минимальное реберное покрытие будет минимальным тогда и только тогда, когда оно содержит наибольшее паросочетание.

2. Максимальное паросочетание является наименьшим тогда и только тогда, когда оно содержится в минимальном реберном покрытии.

Для любого графа G=(V,E) справедливо следующее неравенство

n(G) £ t(G) £ 2n(G).

Если G=(V,E) является двудольным графом, то

t(G) = n(G).