Решение простых комбинаторных задач с помощью графов

Понятие графа

Кроме таблиц, удобным инструментом для перебора и подсчёта различных комбинаций является граф.

Граф из 6 вершин и 7 ребёр.

Например:

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

Например:

5 школьных команд по волейболу сыграли серию игр. Каждая команда провела с другими командами по одному матчу. Сколько всего матчей было сыграно?

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

Например:

На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac{6}{2} = 3$ варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac{3\cdot 2}{2} = 3$ - ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

Каждые три овоща на полном графе образуют треугольник.

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac{5\cdot 4}{2} = 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac{4\cdot 3}{2} = 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac{3\cdot 2}{2} = 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac{2\cdot 1}{2} = 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac{6\cdot 5 \cdot 4}{1\cdot 2 \cdot 3} = 20$ - ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

Если построить полный граф с 11-ю вершинами, каждая тройка команд в нём образует треугольник.

По аналогии с примерами 1 и 2, общее количество треугольников:

$$N = \left(\frac{10\cdot 9}{2} + \frac{9\cdot 8}{2}\right) + \left(\frac{8\cdot 7}{2} + \frac{7\cdot 6}{2}\right) + \left(\frac{6\cdot 5}{2} + \frac{5\cdot 4}{2}\right) + \left(\frac{4\cdot 3}{2} + \frac{3\cdot 2}{2}\right) + \frac{2\cdot 1}{2} = $$

$$ = 9 \frac{(10+8)}{2} + 7 \frac{(8+6)}{2} + 5 \frac{(6+4)}{2} + 3 \frac{(4+2)}{2} +1 = $$

$$ = 9^2+7^2+5^2+3^2+1 = 165 $$

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ - общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^{11} = 11\cdot10\cdot9 = 990 $ - ответ правильный.

Пример 4. В столовой есть на выбор

• два первых блюда: щи (Щ) и борщ (Б)
• три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)
• два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

Построим дерево для перечисления вариантов:

Ответ: 12 вариантов