§ 40. Подсчёт вариантов с помощью графов

Определения и обозначения

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

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

Ребро графа — линия между вершинами, обозначающая связь или возможный переход. Например, ребро между городами показывает, что между ними есть дорога. Оно отражает только один переход, поэтому само по себе ещё не описывает весь вариант выбора.

Дерево вариантов — граф, в котором варианты последовательно расходятся от начальной вершины и не образуют замкнутых циклов. Его ветви показывают возможные продолжения каждого выбора. Такое представление помогает перечислить все варианты и не потерять ни один из них.

Как это устроено

Чтобы изобразить задачу графом, сначала реши, что будут обозначать вершины: сами объекты или этапы выбора. Затем соедини их рёбрами только в том случае, если соответствующий переход разрешён условием. Такой порядок помогает отделить возможные действия от запрещённых и не включить в подсчёт лишние варианты.

Последовательные выборы удобно изображать ветвями дерева, потому что каждый новый выбор зависит от уже сделанных. Из начальной вершины проводят ветви для первого шага, а затем от каждой получившейся вершины — ветви для следующего. Каждая ветвь фиксирует один ход выбора, а значит, по ней можно проследить, как получился конкретный результат.

Чтобы посчитать варианты по дереву, проследи все пути от начальной вершины до конечных. Конечная вершина показывает, что выбор завершён, поэтому полный путь до неё и есть один готовый вариант. Перечисляй пути по очереди и отмечай уже учтённые: это помогает не пропустить ветвь и не посчитать один путь повторно.

Если после каждого выбора остаётся одинаковое число продолжений, можно не выписывать каждый путь. Число вариантов равно произведению возможностей на этапах: например, при трёх вариантах первого выбора и двух вариантах второго получается 3 · 2. Это правило работает потому, что каждый вариант одного этапа сочетается с одинаковым числом вариантов следующего.

Граф помогает учитывать ограничения, поскольку недопустимые переходы можно сразу исключить. Например, если цифры нельзя повторять, после выбора одной цифры ветвь с её повторным выбором не строят. Когда ограничения по-разному влияют на разные ветви, считай их отдельно: так результат учитывает только последовательности, разрешённые условием.

Элементы графа и их роль при подсчёте вариантов

Сначала прочитай, какие объекты или шаги обозначены вершинами, затем проверь, что означает каждое ребро. При подсчёте начинай с начальной вершины и учитывай только полные пути до конечных. Таблица помогает различать отдельный переход и целый вариант.

Разбор задач

Задача 1. Ученик выбирает одну из 3 рубашек и один из 2 галстуков. Построим дерево выбора: сначала от начальной вершины идут три ветви рубашек, затем от каждой — две ветви галстуков. Нужно найти число полных путей до завершения выбора.

1. Обозначим первый этап выбором рубашки, а второй — выбором галстука. Такой порядок удобен, потому что каждый комплект содержит по одному предмету каждого вида.
2. От каждой из трёх ветвей рубашек проведём две ветви для галстуков. Получится по два комплекта с каждой рубашкой, а ни один комплект не повторится.
3. Считаем пути: 2 + 2 + 2 = 6. Проверим правилом умножения: 3 · 2 = 6, поскольку число галстуков не зависит от выбранной рубашки.

Ответ: 6 комплектов. Здесь дерево показывает все варианты, а умножение позволяет быстро проверить их число.

Задача 2. Из города A в город B ведут 2 дороги, а из B в C — 3 дороги. Требуется найти число маршрутов из A в C через B. Поскольку путь обязательно проходит через B, в маршруте есть два последовательных участка.

1. Обозначим города вершинами, а дороги — рёбрами графа. На первом участке из A в B можно выбрать одну из двух дорог, на втором из B в C — одну из трёх.
2. Для каждого выбора дороги до B доступны все три дороги до C. Поэтому каждому из двух вариантов первого участка соответствуют три полных пути.
3. Перемножим числа возможностей: 2 · 3 = 6. Результат — число путей от A до C через B, а не число отдельных дорог.

Ответ: 6 маршрутов. Это правило работает, потому что выбор дороги на первом участке не убирает дороги на втором.

Задача 3. Из цифр 1, 2, 3, 4 составляют двузначные числа без повторения цифр. В дереве сначала выбирают цифру десятков, затем цифру единиц. Ограничение означает, что уже выбранную цифру нельзя использовать повторно.

1. На первое место можно поставить любую из четырёх цифр. Поэтому от начальной вершины проведём четыре ветви.
2. После каждой первой цифры остаются три неиспользованные цифры для второго места. Ветвь с повторением выбранной цифры не добавляем.
3. Полных путей будет 4 · 3 = 12. Число продолжений уменьшается после первого выбора, но в каждой ветви оно одинаково, поэтому умножение здесь применимо.

Ответ: 12 чисел. Дерево с исключёнными повторами объясняет, почему для второго места остаётся именно три возможности.

Типичные ошибки

Считать все рёбра графа вместо полных путей — значит принять отдельные переходы за готовые варианты. Так ошибаются, когда не разделяют этапы выбора и сразу складывают все линии на схеме. Проверь себя: вариант должен описывать весь путь от начальной вершины до конечной, а не один шаг.

Учитывать недопустимые ветви — значит включать результаты, запрещённые условием. Например, при составлении чисел без повторяющихся цифр нельзя оставлять ветвь, где выбранная цифра появляется снова. Перед подсчётом проверь каждое ребро и спроси себя, разрешён ли такой переход.

Пропускать или повторно считать пути легко, если обходить ветви без порядка. Тогда один вариант может затеряться среди остальных или попасть в подсчёт дважды. Двигайся от начальной вершины последовательно, отмечая каждый завершённый путь, и сверяй число отметок с итогом.

Применять одно произведение при разном числе продолжений после разных выборов — значит считать, будто все ветви одинаковы. Это бывает, когда правило умножения используют по привычке, не проверив условие задачи. Сравни продолжения в каждой ветви: если они различаются, считай ветви отдельно и складывай полученные количества.

Связь с другими темами

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

Подсчёт путей связан с правилом умножения: если на этапах одинаковое число продолжений, количества вариантов перемножают. Графы и деревья помогают увидеть, когда это правило подходит, а когда ветви нужно разбирать отдельно. Эти способы пригодятся при дальнейшем изучении комбинаторики и вероятности, где считают возможные исходы.

Что запомнить

• Вершины обозначают объекты или этапы выбора, рёбра — возможные переходы.
• Один полный путь от начальной вершины до конечной задаёт один вариант.
• Запрещённые условием переходы не включают в граф.
• Если на каждом этапе число продолжений одинаково, можно применить правило умножения.
• Если число продолжений зависит от предыдущего выбора, варианты считают по ветвям дерева.
• Каждый допустимый конечный путь нужно учесть ровно один раз.