4. Циклы в графах.

Во многих прикладных задачах важную роль играют свойства графов,

связанные с существованием в графе замкнутых маршрутов, называемых

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

1) Изучить такие основополагающие понятия теории графов, как граф, маршрут и цикл (/1/, с. 9-43; /2/, с. 5-22).

2) Рассмотреть понятие цикломатического числа графа и доказать его

основные свойства (/1/, с. 59-61; /2/, с. 43-46).

3) Разобрать определение групп одномерных и нульмерных цепей графа и показать их взаимосвязь с пространством циклов графа (/2/, с. 46-55).

Литература, рекомендуемая для изучения темы