Понятие графа
Помимо таблиц, полезным инструментом для перечисления и расчета различных комбинаций является диаграмма.
Граф — это абстрактный математический объект, который представляет собой набор вершин графа и набор ребер, то есть соединения между парами вершин.
Граф с 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. Есть выбор в столовой
- два первых блюда: щи (У) и борщ (Б)
- три основных блюда: мясо (M), рыба (P), блины с рикоттой (T)
- два напитка: компот (C) и сок (C)
Сколько вариантов обеда можно иметь с этими блюдами и какие?
Согласно правилу продукта, общее количество вариантов обеда: $ 2 cdot3 cdot2 = 12$
Давайте построим дерево, чтобы перечислить варианты:
Ответ: 12 вариантов