"Алгебра", Алимов Ш.А.
Граф — это схема из точек и линий, которая помогает увидеть все возможные переходы при выборе. Точки обозначают объекты или этапы, а линии — допустимые переходы между ними. Один полный путь от начала до конца показывает один вариант. Чтобы найти общее число вариантов, можно перечислить такие пути, умножить числа последовательных выборов или сложить результаты в разных ветвях. Граф помогает заметить пропуски и не посчитать один вариант дважды.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Граф — схема из точек и линий, с помощью которой изображают возможные переходы между объектами или этапами выбора. Например, так можно показать, какими дорогами соединены города или какие блюда получаются из разных продуктов. Граф превращает длинное описание в наглядную схему. По ней удобнее увидеть, какие варианты вообще существуют.
Вершина графа — точка, обозначающая объект, состояние или результат выбора на определённом этапе. Вершиной может быть город, выбранный напиток или промежуточный результат. Вершины нужны, чтобы отмечать, откуда начинается переход и куда он ведёт. Их можно подписывать буквами или словами.
Ребро графа — линия, соединяющая вершины и показывающая возможный переход от одного выбора к другому. Например, ребро между двумя городами может обозначать дорогу, а между этапами — разрешённое продолжение выбора. Ребро важно отличать от самой вершины: оно показывает связь, а не объект. Если переход невозможен, соединять вершины не нужно.
Путь в графе — последовательность вершин и соединяющих их рёбер, соответствующая одному варианту. Полный путь проходит от начала задачи до её результата. Например, выбор напитка, а затем булочки образует путь из двух переходов. Понятие пути позволяет считать целые варианты, а не отдельные части схемы.
Чтобы представить последовательность выборов, сначала выдели начало задачи и отметь его вершиной. От неё проведи рёбра к результатам первого шага, а от каждой полученной вершины покажи возможные продолжения. Такая структура нужна потому, что каждый следующий выбор зависит от того, к какому результату привёл предыдущий. Если расположить шаги по порядку, схема покажет все допустимые цепочки.
Каждому полному пути соответствует ровно один вариант: путь фиксирует, что выбрали на каждом шаге. И наоборот, любой вариант из условия задаёт определённую последовательность переходов, то есть свой путь. Это соответствие позволяет считать варианты по схеме, не смешивая отдельные выборы с готовыми результатами. Если одному варианту соответствуют два пути, значит, граф построен неудачно или вариант посчитан повторно.
Когда из вершины выходят несколько рёбер, можно выписать все полные пути и посчитать их. Если путей много, удобнее разделить граф на ветви: сначала посчитать пути, проходящие по каждой ветви, а затем сложить результаты. Сложение подходит, когда ветви описывают разные случаи и один путь не попадает сразу в две ветви. Так подсчёт остаётся понятным даже у разветвлённой схемы.
Если выборы идут друг за другом и на каждом этапе число продолжений одинаково для любого предыдущего результата, применяют правило умножения. Например, при двух видах сока и трёх видах булочки каждый сок можно сочетать с каждой булочкой, поэтому получается 2 · 3 вариантов. Умножение заменяет перечисление всех путей, когда структура графа устроена одинаково на каждом шаге. При разном числе продолжений сначала проверяй ветви отдельно.
Удобный граф следует порядку действий из условия и не содержит переходов, которые там запрещены. Иногда этапы выбора показывают вершинами, а иногда каждый результат выбора делают отдельной вершиной; важно не название схемы, а соответствие условию. После построения проверь каждую ветвь: можно ли пройти по ней от начала до конца и получить допустимый вариант? Затем убедись, что все варианты представлены и ни один не повторён.
| Ситуация | Что показывает граф | Как считать варианты |
|---|---|---|
| Последовательные выборы с одинаковым числом возможностей | Каждый результат этапа ведёт к одинаковому числу продолжений. | Перемножить числа выборов на этапах. |
| Последовательные выборы с разным числом возможностей | Из разных вершин может выходить разное количество рёбер. | Посчитать полные пути по ветвям и сложить результаты. |
| Несколько ветвей, ведущих к разным результатам | Каждая ветвь соответствует отдельному случаю или маршруту. | Подсчитать пути в каждой ветви и сложить. |
| Проверка полноты подсчёта | Видны все переходы от начала до конечных результатов. | Сверить пути с условием, проверить пропуски и повторы. |
Сначала реши, описывает ли граф последовательные шаги или несколько отдельных случаев. Для одинакового числа продолжений на каждом шаге удобно умножение, а для непересекающихся ветвей — сложение. Если в ветвях устройство разное, посчитай пути отдельно, а затем сложи результаты.
Из пункта A в пункт B ведут 3 дороги. Сколькими способами можно добраться из A в B? Здесь нет промежуточных пунктов и дополнительных этапов: каждый отдельный путь сразу приводит из A в B. Поэтому достаточно изобразить A и B вершинами, а дороги — рёбрами между ними.
Ответ: добраться можно 3 способами. Перебирать дополнительные сочетания не нужно, так как маршрут состоит только из выбора одной дороги. Граф наглядно показывает, что все три пути ведут к одному и тому же пункту назначения.
Ученик выбирает один из 2 видов сока и один из 3 видов булочки. Сколько разных завтраков можно составить? Выбор состоит из двух последовательных шагов: сначала сок, затем булочка. Каждый вид сока можно сочетать с каждым видом булочки, так как ограничений на сочетания не дано.
Ответ: можно составить 6 разных завтраков. Каждый путь задаёт одну пару «сок и булочка». Например, выбор одного и того же сока с двумя разными булочками даёт два разных завтрака.
Из A в B можно попасть через C или D. Из A в C ведут 2 дороги, из C в B — 3; из A в D ведут 2 дороги, из D в B — 2. Нужно найти общее число маршрутов. Случаи с промежуточным пунктом C и промежуточным пунктом D — две отдельные ветви.
Ответ: из A в B можно проехать 10 маршрутами. Сначала умножение считает все сочетания дорог внутри каждой ветви, а затем сложение объединяет два разных случая. Такой порядок не смешивает переходы между C и D, которых условие не предлагает.
Считать вершины вместо полных путей. Вершина обозначает объект или этап, а не обязательно готовый вариант, поэтому подсчёт одних точек может дать неверное число. Эту ошибку допускают, когда схема кажется простой и хочется быстро пересчитать её элементы. Проверь себя: каждый ли посчитанный объект соответствует всей последовательности выборов от начала до конца?
Забывать продолжения на следующем этапе. Если посчитать только первые выборы, будут учтены не все сочетания. Такое случается, когда внимание сосредоточено на начальных ветвях и не прослеживает их до результата. Проследи каждую ветвь до конца и проверь, что учтены все выходящие из неё продолжения.
Складывать последовательные выборы вместо умножения. При последовательных шагах каждый результат первого шага может сочетаться с продолжениями следующего, поэтому числа выборов перемножают. Сложение здесь ошибочно объединяет числа, но не считает сочетания. Задай себе вопрос: нужно выполнить оба шага или выбрать один из нескольких отдельных случаев?
Повторять вариант или пропускать ветвь. Это происходит, если не сверить схему с условием или дважды включить один путь при подсчёте. В результате ответ оказывается завышенным либо заниженным. Проверь каждую ветвь по условию, перечисли полные пути и убедись, что ни один вариант не встречается дважды.
Для работы с графом нужно уметь выделять этапы выбора и различать последовательные действия и альтернативные случаи. Это помогает правильно решить, где умножать, а где складывать числа вариантов. Поэтому граф связывает наглядное изображение с правилами умножения и сложения при подсчёте.
Систематический подсчёт пригодится в комбинаторике — разделе математики о способах выбора и расположения объектов. Такие схемы полезны и в вероятности, когда нужно перечислить возможные исходы события. Граф также помогает составлять таблицы возможных результатов и проверять, что ни один случай не потерян.
Что именно обозначают вершины и рёбра графа в задаче?
Вершины — это точки, обозначающие объекты, состояния или этапы выбора. Рёбра — линии, которые показывают, какие переходы между вершинами разрешены условием задачи.
Как понять, что считать одним вариантом?
Один вариант — это полный путь от начальной вершины до конечной. Он содержит всю последовательность выборов, а не только один отдельный шаг или одну вершину.
Когда при подсчёте вариантов нужно складывать, а когда умножать?
Умножай, когда выборы идут один за другим: каждому выбору на первом шаге может соответствовать несколько продолжений. Складывай количества вариантов в разных, не пересекающихся ветвях, например когда маршрут проходит через C или через D.
Как проверить, что граф показывает все возможные варианты?
Сверь каждую вершину и линию с условием: все ли разрешённые переходы показаны и нет ли запрещённых. Затем проверь, что каждый полный путь означает ровно один вариант и что ни один вариант не повторяется.
Можно ли одну задачу изобразить разными графами?
Да, если каждый граф правильно передаёт выборы и переходы из условия. Можно по-разному обозначить этапы или перестроить схему, но количество полных путей должно остаться тем же.
§ 40. Подсчет вариантов с помощью графов
