7. Свойства эйлеровых графов.

Одной из первых задач, приведших к возникновению теории графов, является известная задача Эйлера о кенигсбергских мостах. Решение этой задачи естественно привело к определению важного класса графов, называемых эйлеровыми. Цель контрольной работы - изучить основные свойства эйлеровых графов. Рекомендуется следующий план работы:

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

2) Рассмотреть задачу Эйлера о кенигсбергских мостах, ввести определение эйлерова графа и доказать критерий эйлеровости графа (/1/, с. 43-45; /2/, с. 5-22).

3) Разобрать алгоритм Флери построения эйлеровой цепи в графе (/1/, с. 45-46).

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

1) Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

2) Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,

1976.

3) Березина Л.Ю. Графы и их применения: Пособие для учителей. – М.,

1979.