9. Ориентированные графы.

Понятие ориентированного графа (орграфа) играет важную роль в

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

работы:

1) Изучить такие основополагающие понятия теории графов, как ориентированный граф, ориентированный маршрут, орцепь, орцикл и сильная связность, доказать теорему Роббинса об ориентируемом связном графе (/1/, с. 127-130).

2) Рассмотреть понятие эйлерова орграфа и доказать основную теорему о таких графах (/1/, с. 131-133).

3) Рассмотреть понятия гамильтонова орграфа и проанализировать взаимосвязь полугамильтоновых оргафов с турнирами (/1/, с. 133-136). 4 Разобрать приложение орграфов к теории цепей Маркова (/1/, с. 138-142).

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