Граф – это структура, состоящая из множества узлов (вершин) и дуг. Каждая дуга указывается парой узлов.
Граф не всегда является деревом. Дерево – это граф (указатель от отца к сыну – дуга).
Узел N называется инцендентным, если это 1 из 2-х узлов упоряд. Пары, составляющих дугу Х, при этом дуга Х инцендента узлу N.
Полустепень захода узла N – это число дуг, для которых узел N является головой стрелки.
Полустепень исхода узла N – это число дуг, для которых узел N является хвостом стрелки.
Взвешенный граф (сеть) – граф, у которого с каждой дугой связано какое-либо значение (вес).

Операции.

1. Добавление дуги к графу от узла i к узлу j, если такой дуги не было.
2. Удаление дуги от узла i к узлу j, если такая дуга существует.
3. Определение смежности узлов.

Путь длиной К от узла А до узла В определяется как послед-ть К+1 узлов.
Путь от узла к самому себе называется циклом.
Если есть цикл => граф циклический.