Тема 47. Эйлеровы графы

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

1 Определить понятие графа в виде представления некоторого бинарного отношения и связанные с графом основные понятия, а также привести простейшие примеры (/1/, с. 9 – 24; /2/, с. 6 – 16).

2Дать определение эйлерова и полуэйлерова графа, привести примеры. Установить необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Описать алгоритм построения эйлеровой цепи в эйлеровом графе (/1/, с. 43 – 48; /2/, с. 37 – 42).

3Рассмотреть примеры эйлеровых и неэйлеровых графов. Решить несколько упражнений из /1/, /2/.

4Исторические сведения о графах: решение Эйлера задачи о семи кенигсбергских мостах (/3/, §43).

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

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

2Березина Л.Ю. Графы и их применения. – М.: Просвещение, 1979.

3Емеличев В.А. Лекции по теории графов. – М.: Наука, 1990.

4Оре О. Теория графов. – М.: Наука, 1968.

5Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией. – М.:

1976.