3. Связность графа.

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

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

2) Рассмотреть деревья, эйлеровы и гамильтоновы графы, доказать теоремы об их основных свойствах (/1/, с. 43-62; /2/, с. 22-24).

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

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

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

1976.

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

1979.