Лекция: Теоремы о подструктурах графа
Пусть для любого графа 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).