Глава 9. ЦИКЛЫ, РАЗРЕЗЫ И ЗАДАЧА ЭЙЛЕРА

1. Введение

Целью настоящей главы является изучение циклов в графа и исследование некоторых из их свойств и связей с другими понятиями (такими, как понятие дерева), введенными ранее. Два тип» циклов в графах эйлеровы и гамильтоновы циклы, часто встречаются в практических задачах и поэтому представляют особый интерес. Первые из них рассмотрены в настоящей главе, а вторые — в следующей.

В настоящей главе мы будем заниматься циклами как в ориентированных, так и в неориентированных графах, а также в мультиграфах, являющихся слабым обобщением понятия графа. Последние являются графами, в которых может существовать несколько дуг между двумя данными вершинами и Если наибольшее число «запараллеленных» дуг равно то граф называется -графом. Так. на рисунке 9.1 представлен -граф. Очевидно, что обычный граф можно рассматривать как -граф.

-Графы очень часто возникают на практике, когда граф используется для представления физической системы в естественных науках, вопросах управления, инженерном деле и т. д. Так, например, -граф на рис. 9.1 изображает молекулярную структуру органического химического соединения акрилонитрила. В электротехнике графы, изображающие электрические цепи, почт» всегда являются -графами, так как параллельно может быть включено несколько электрических компонентов. В проблемах надежности оборудования или сетей связи наиболее важные устройства или линии связи часто дублируются, утраиваются а возникающая избыточность увеличивает надежность системы. Графы таких систем также являются -графами.