Ориентированные графы и задачи с помощью графов

В российской программе (7–8 классы, «Вероятность и статистика», введение в теорию графов) граф используют как удобную модель: вершины — люди, города, команды, рёбра — связи между ними (дружба, дороги, матчи). Если связь направленная («A обогнал B», «A пишет B»), ребро рисуют со стрелкой, и граф называют ориентированным. У вершины тогда есть число выходящих стрелок и число входящих.

Классические задачи: число рукопожатий в группе из n человек (каждый с каждым по разу), число матчей в турнире (каждая команда играет с каждой). Сумма степеней равна удвоенному числу рёбер, поэтому число рёбер равно половине суммы степеней: для n вершин, соединённых каждая с каждой, получаем n·(n − 1) : 2.

Типичная ошибка — посчитать каждое ребро дважды. Другая — путать выходящие стрелки с входящими. Задачу о маршруте решают подсчётом рёбер в кратчайшей цепи.