Деревья.

Дерево – это простой связный граф без циклов

Лес – простой граф без циклов (множество деревьев)

Лист – любая вершина степень которой = 1

У любого дерева, построенного на n вершинах, имеется ровно n-1 ребро.(доказательство при удалении листа удаляется одно ребро)

Цикломатическое число (цикломатический порядок) графа – это наименьшее количество ребер, которые надо удалить из данного связного графа, чтобы на нем не осталось ни одного цикла.

8. Содержание

   • Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.
   • Изоморфизм графов. Примеры.
   • Пути, цепи, циклы.
   • Связность графов.
   • Эйлеров цикл. Определение, условие существования, алгоритм нахождения.
   • Гамильтонов цикл. Определение. Задача о коммивояжере.
   • Деревья.
   • ОстОвное дерево. Алгоритм Крускала.
   • Алгоритм поиска кратчайшего пути в графе.
   • Клики. Алгоритм поиска клик.
   • Раскраска графов. Алгоритмы раскраски.
   • Генерация случайных графов.