6 урок. Конспект материала в тетрадь

Граф – это набор вершин и связей между ними (рёбер).

Петля – это ребро, которое начинается и заканчивается в одной и той же вершине.

Степень вершины – количество ребер, с которыми связана эта вершина.(петля считается дважды!)

Список смежности – перечисление всех узлов, скоторым связан данный узел.

Путь – последователность ребер для перехода из одного узла в другой.

Связный граф – граф,между любыми вершинами которого есть путь.

Цикл – замкнутый путь в графе.

Дерево – связный граф, в котором нет циклов.

Взвешенный граф – граф, с каждым ребром которого связано некоторое число (вес ребра).

Орграф - ориентированный граф, в котором для каждого ребра указывается направление и двигаться можно только по стрелке.