Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.7. Базисные разрезающие множества

В разд. 2.4 было показано, что остов связного графа можно использовать для получения множества базисных циклов в графе. В данном разделе мы показываем, как с помощью остова можно определить множество базисных разрезающих множеств.

Рассмотрим остов Т связного графа G. Пусть b — ветвь Т. Удаление ветви b разбивает Т на две компоненты Следует отметить, что являются деревьями графа G. Пусть обозначают соответственно такие множества вершин что вместе содержат все вершины графа

Пусть будут соответственно порожденными подграфами графа G на множествах вершин . Не трудно видеть, что являются остовами Следовательно, по теореме — связные графы. В теореме 2.6 доказывается, что разрез является разрезающим множеством графа G. Это разрезающее множество называется базисным множеством графа G по отношению к ветви b остова Т графа G. Множество всех базисных разрезающих множеств по отношению к -ветви остова Т связного графа G называется базисным множеством разрезающих множеств графа G по отношению к остову Т.

Следует отметить, что разрезающее множество содержит точно одну ветвь, т. е. ветвь b остова Т. Все другие ребра являются хордами Т. Это следует из того, что не содержит ни одного ребра из остовов . Далее, ветвь b не присутствует ни в одном базисном разрезающем множестве по отношению к Т. Из этого следует, что множество ребер базисного разрезающего множества нельзя представить в виде кольцевой суммы множеств ребер нескольких или всех базисных разрезающих множеств. В гл. 4 мы покажем, что каждое разрезающее множество

Рис. 2.8. Множество Оазисных разрезающих множеств графа, с — граф G; б — остов Т графа в — базисное разрезающее множество по отношению к ветви г — базисное разрезающее множество по отношению к ветви д — базисное разрезающее множество по отношению к ветви е — базисное разрезающее множество по отношению к ветви графа G можно представить кольцевой суммой нескольких базисных разрезающих множеств по отношению к остову Т графа

Граф G и множество его базисных разрезающих множеств представлены на рис. 2.8.

<< Предыдущий параграф Следующий параграф >>
Оглавление