1. Эйлеровы графы .

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

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.