Как построить дерево возможных вариантов для комбинаторных задач?

Дерево возможных вариантов — это универсальный алгоритм построения и перебора комбинаций, в котором все варианты обозначаются в виде расходящихся «веток дерева». 1

Чтобы построить дерево возможных вариантов для комбинаторной задачи, нужно выполнить следующие шаги: 2

1. Обозначить «корень». 2 Обычно его обозначают знаком «*». 24
2. Провести «ветки» — отрезки, на концах которых подписать варианты, которые можно взять за основание. 2
3. От каждой фигуры провести такое количество «веток», которое будет соответствовать числу вариантов фигур на втором месте. 2
4. От каждой фигуры, стоящей на втором месте, провести такое число «веток», которое будет соответствовать числу вариантов фигур на третьем месте. 2

Пример построения дерева возможных вариантов — задача о составлении двузначных чисел из цифр 1, 4 и 7. 4

Решение: 4

1. Чтобы получить двузначное число, надо сначала выбрать первую цифру, для неё есть три варианта: 1, 4 или 7. 4 Поэтому из точки «*» проведены три отрезка и на концах поставлены цифры 1, 4 и 7. 4
2. Теперь надо выбрать вторую цифру, для этого также есть три варианта: 1, 4 или 7. 4 Поэтому от каждой первой цифры проведено по три отрезка, на концах которых снова записано 1, 4 или 7. 4

В результате получится, что из трёх цифр можно составить 9 различных двузначных чисел. 4