№ 2. В некотором государстве 76 городов. Каждый из них соединен авиалиниями ровно с 5 другими (международных рейсов нет). Сколько авиалиний в этом государстве?

Решение:

Дано:

Количество городов (вершин графа): \( V = 76 \).

Каждый город соединен ровно с 5 другими (степень каждой вершины): \( d = 5 \).

Найти:

Количество авиалиний (ребер графа): \( E \).

Решение:

Согласно лемме Гаккеля, сумма степеней всех вершин графа равна удвоенному числу ребер: \( ∑ d_i = 2E \).

В данном случае все вершины имеют одинаковую степень \( d = 5 \). Тогда сумма степеней равна произведению числа вершин на степень каждой вершины:

\( ∑ d_i = V × d \)

\( ∑ d_i = 76 × 5 = 380 \)

Теперь найдем количество ребер (авиалиний):

\( 2E = 380 \)

\( E = \frac{380}{2} \)

\( E = 190 \)

Ответ: В этом государстве 190 авиалиний.