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

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

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

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

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

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

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

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

Подграф графа или орграфа состоит из некоторого подмножества вершин и некоторого подмножества ребер .