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

2) Рассмотреть определение дерева и доказать теорему о его характеристических свойствах (/1/, с. 56-59; /2/, с.45-46).

3) Ввести понятие остовного леса графа и проанализировать его взаимосвязь с фундаментальной системой циклов исходного графа (/1/, с. 59-

61).

4) Разобрать задачу о перечислении деревьев и доказать известную теорему Кэли о числе помеченных деревьев (/1/, с. 62-66).

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

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

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

1976.

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

1979.