Определение 2.

Полный граф – это граф, в котором каждая вершина соединена со всеми остальными.

 

Число ребер в полном графе без петель с N вершинами равно .

В полном ориентированном графе разрешается переход из любой вершины в любую другую.

 

Поскольку в графе переход по ребру разрешается в обоих направлениях, а переход по ребру в орграфе – только в одном, то в полном орграфе в два раза больше ребер, то есть их число равно (Рисунок 6).

 

 

Рисунок 6 – а) Полный граф; N = 3; число рёбер равно 3;

б) Полный орграф; N = 3; число рёбер равно 6.