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

2.4. Базисные циклы

Рассмотрим остов Т связного графа G. Обозначим ветви Т через а хорды Г — через — число ребер, число вершин в графе G. Поскольку Т — ациклический, то по теореме 2.1 граф содержит точно один цикл . Этот цикл состоит из хорды и тех ветвей Т, которые принадлежат

Рис. 2.4. Множество базисных циклов графа

— граф ; б — остов Т графа G; в — пять базисных циклор графа G по отношению к Т (хорды обозначены штриховыми линиями).

единственному пути между концевыми вершинами Цикл С, называется базисным циклом графа G относительно хорды с, остова Т.

Множество всех базисных циклов графа G относительно хорд остова Т называется базисным множеством циклов графа G относительно Т.

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

Граф G и множество его базисных циклов представлены на рис. 2.4.

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