Вопрос 9. Парасочетание. Реберное покрытие.
Дан G=(X,E) произвольный, не пустой.
Опр.: Подмножество ребер M графа G, наз. парасочетанием если все ребра M попарно не смежные.
Опр.: Парасочетание наз. максимальным если оно не содержится не в одном другом парасочетании графа.
Опр.: Парасочетание графа G наибольшей мощности наз. набольшим.
Опр.: Мощность наибольшего парасочетания наз. числом парасочетаний и обозн. "альфа1(G)”
Опр.: Подмножество ребер P графа G наз. реберным покрытием если любая вершина графа инцидентна по крайней мере одному ребру из P.
Опр.: Реберное покрытие наз. минимальным если не содержит никакого другого реберного покрытия графа.
Опр.: Реберное покрытие наз. минимальным если имеет наименьшую мощность среди всех реберных покрытий графа.
Опр.: Мощность наименьшего реберного покрытия наз. числом реберного покрытия графа и обозн. "бета1(G)”.
Опр.: Парасочетание кот. яв-ся и реберным покрытием одновременно наз. совершенным парасочетанием.
Теор.: Для любого графа G без изолированных вершин верно равенство: "альфа1(G)”+”бета1(G)”=n