§ 4 Решение логических задач с помощью графов

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

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

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

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

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

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

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

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

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

Направление ребра нужно, когда смысл связи меняется при перестановке объектов. Например, фраза «Маша выше Саши» не равнозначна фразе «Саша выше Маши», поэтому сравнение можно записать стрелкой от более высокого участника к более низкому. Если же связь взаимная, например «города соединены дорогой», достаточно обычной линии.

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

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

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

Разбор задач

Ученики и кружки

Аня, Борис и Вера выбрали по одному кружку: шахматы, робототехнику и театр. Аня не выбрала театр, Борис не выбрал шахматы, а Вера не выбрала шахматы и робототехнику. Нужно определить выбор каждого ученика. Построим две группы вершин и будем соединять ученика только с теми кружками, которые ещё возможны.

1. Соединим каждого ученика со всеми кружками, затем уберём запрещённые варианты. У Веры останется только театр, потому что шахматы и робототехника ей не подходят.
2. Каждый кружок выбран ровно один раз, значит театр уже занят Верой. У Ани остаются шахматы и робототехника, а у Бориса — робототехника и театр, но театр занят.
3. Борису остаётся робототехника. Тогда Аня выбирает шахматы, и все трое получают разные кружки.

Ответ: Аня выбрала шахматы, Борис — робототехнику, Вера — театр. Проверка подтверждает, что никто не выбрал запрещённый кружок и каждый кружок использован один раз.

Порядок участников

Саша выше Игоря, Игорь выше Олега, а Маша выше Саши. Изобразим участников вершинами; договоримся, что стрелка идёт от более высокого к более низкому. Это превращает сравнения в цепочки, по которым удобно восстановить весь порядок.

1. Проведём стрелки Маша → Саша, Саша → Игорь и Игорь → Олег.
2. Соединим связи в одну цепочку: Маша → Саша → Игорь → Олег. Каждая стрелка означает, что участник слева выше следующего.
3. Прочитаем цепочку сверху вниз по росту. Дополнительные сравнения для определения мест не нужны, потому что связана вся четвёрка.

Ответ: от самого высокого к самому низкому: Маша, Саша, Игорь, Олег. Все три сравнения из условия соблюдены.

Маршрут по городам

Пять городов соединены дорогами; требуется выяснить, можно ли проехать из А в Д, посетив каждый указанный город ровно один раз. В условии, приведённом здесь, не перечислено, какие именно дороги соединяют города, поэтому однозначно ответить «можно» или «нельзя» нельзя. Но граф показывает, как решить задачу, когда список дорог известен.

1. Обозначим каждый город вершиной, а каждую существующую дорогу — ребром. Не проводим линий между городами, если дороги между ними нет.
2. Начнём цепочку в вершине А и будем переходить по дорогам к ещё не посещённым городам. Повторно заходить в уже пройденную вершину нельзя.
3. Проверим, можно ли таким способом включить все пять городов и закончить в Д. Если такая цепочка найдена, маршрут существует; если все допустимые продолжения исчерпаны, маршрута нет.

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

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

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

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

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

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

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

Для работы с графами нужно внимательно читать условие и выделять объекты, ограничения и слова вроде «не», «или» и «раньше». Пригодятся таблицы соответствий и перебор вариантов: граф делает возможные связи наглядными и часто сокращает число проверок. Позже такой способ поможет в комбинаторике, вероятности, задачах о маршрутах и поиске связей между объектами.

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

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