Глава 9. ЦИКЛЫ, РАЗРЕЗЫ И ЗАДАЧА ЭЙЛЕРА
1. Введение
Целью настоящей главы является изучение циклов в графа и исследование некоторых из их свойств и связей с другими понятиями (такими, как понятие дерева), введенными ранее. Два тип» циклов в графах эйлеровы и гамильтоновы циклы, часто встречаются в практических задачах и поэтому представляют особый интерес. Первые из них рассмотрены в настоящей главе, а вторые — в следующей.
В настоящей главе мы будем заниматься циклами как в ориентированных, так и в неориентированных графах, а также в мультиграфах, являющихся слабым обобщением понятия графа. Последние являются графами, в которых может существовать несколько дуг
между двумя данными вершинами
и
Если наибольшее число «запараллеленных» дуг равно
то граф называется
-графом. Так. на рисунке 9.1 представлен
-граф. Очевидно, что обычный граф можно рассматривать как
-граф.
-Графы очень часто возникают на практике, когда граф используется для представления физической системы в естественных науках, вопросах управления, инженерном деле и т. д. Так, например,
-граф на рис. 9.1 изображает молекулярную структуру органического химического соединения акрилонитрила. В электротехнике графы, изображающие электрические цепи, почт» всегда являются
-графами, так как параллельно может быть включено несколько электрических компонентов. В проблемах надежности оборудования или сетей связи наиболее важные устройства или линии связи часто дублируются, утраиваются
а возникающая избыточность увеличивает надежность системы. Графы таких систем также являются
-графами.