Понятие графа: решение комбинаторных задач, полный, дерево, примеры

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

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

Граф — это абстрактный математический объект, который представляет собой набор вершин графа и набор ребер, то есть соединения между парами вершин.

Граф с 6 вершинами и 7 ребрами.

Граф с 6 вершинами и 7 ребрами.

Например:

Сколько разных трехзначных чисел вы можете написать, используя цифры 0 и 1?

Сколько разных трехзначных чисел вы можете написать, используя цифры 0 и 1?

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

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

Полный граф — это граф со всеми возможными ребрами.

Полный график

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

Например:

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

Рисуем полный граф с 5 вершинами и подсчитываем количество ребер.

Полный граф с 5 вершинами

N = 10. Это означает, что сыграно 10 игр.

Граф-дерево

Дерево — это граф без петель с единственной дугой между парами вершин.

Древовидный граф с 9 узлами и 8 ребрами.

Древовидный граф с 9 узлами и 8 ребрами.

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

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

дерево удобно использовать для составления упорядоченных комбинаций элементов.

Например:

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

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

Упорядоченные комбинации элементов

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

Примеры

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

Построим полную диаграмму.

Пример 1.

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

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

$ frac {3 cdot 2} {2} = 3 $ — военно-промышленный комплекс, технико-высокотехнологичный комплекс и высокотехнологичный производственный комплекс

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

Всего треугольников 3 + 1 = 4

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

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

Построим полную диаграмму.

Пример 2.

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

Например, с оставшимися 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 вершинами, каждая тройка команд внутри него образует треугольник.

Пример 3*.

Как и в примерах 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$

Давайте построим дерево, чтобы перечислить варианты:

Пример 4.

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

Оцените статью
Блог про прикладную математику