Автор статьи: Андрей Роженцов
Представление информации
Для того чтобы упростить представление информации, люди активно пользуются графами и таблицами. Представим, что нам необходимо запомнить следующую информацию о городах:
- длина дороги от Москвы до Владимира — 200 км
- от Владимира до Нижнего Новгорода — 250 км
- от Нижнего Новгорода до Саранска — 310 км
- от Москвы до Воронежа — 520 км
- от Саранска до Москвы — 630 км
Других дорог нет!
Представим эту информацию в виде графа.
Граф — это математическая структура, которая используется для моделирования связей между различными объектами. Он состоит из вершин и соединяющих их рёбер. Там, где обозначены вершины, подпишем названия городов, а на рёбрах — длины дорог.
Важно: длины рёбер не отражают настоящие длины дорог, поэтому в графе ребро «от Москвы до Владимира» может быть длиннее, чем ребро «от Владимира до Нижнего Новгорода».
Представим ту же информацию, но в виде таблицы. В качестве строк и столбцов подпишем названия городов. В ячейке, которая стоит на пересечении строки и столбца (для связанных дорогой городов), запишем длину этой дороги.
Из Москвы во Владимир есть дорога протяжённостью 200 км, значит, на пересечении этих строки и столбца записываем число. Аналогично в столбике с Владимиром.
По диагонали ячейки заполнены серым цветом, т. к. мы считаем, что нет дороги, ведущей из города в этот же город. Заполняем табличку до конца.
В некоторых задачах длины дорог будут неизвестны, а информацию сообщат только об их наличии. В соответствующей ячейке находится «*».
Например, вот так:
В решении город A будем называть соседом города B при условии, что существует дорога из A в B.
Задача 1: простая асимметричная
Рядом с каждым городом на графе подпишем количество дорог, выходящих из него.
Начнём с тех вершин, из которых исходит уникальное количество дорог. Это вершины A — 1 дорога, C — 3 дороги, B — 4 дороги.
По таблице мы видим, что четыре дороги выходят из пункта № 4, одна — из пункта № 5 и три — из пункта № 6. Следовательно, A = № 5, B = № 4, C = № 6. Для наглядности перепишем названия строк и столбцов в таблице.
По графу заметим, что у городов C и B есть один общий сосед — D.
По схеме они оба имеют дороги в пункт № 3, значит, D = № 3.
В табличке осталось два неотмеченных пункта: № 1 и № 2. Они соответствуют оставшимся городам E и F.
Однозначно определить, какой номер у E, а какой — у F, нельзя, но это и не требуется: в ответе нужно записать два номера в порядке возрастания, без пробелов.
Ответ: 12
Задача 2: простая симметричная
Схема симметрична относительно проведённой линии. Однозначно найти номера пунктов не получится, но от нас требуется только найти симметричные дороги.
Отметим количество дорог, выходящих из каждого города.
Выделяются два города, A и H, у них по 1 дороге. В таблице это пункты № 5 и 6. Из-за симметрии первый выбор можем сделать любым образом, пусть A = № 5, H = № 6.
У города A только один сосед, тогда E = № 7. У города H тоже только один сосед, G = № 2.
У городов G и E есть один общий сосед — B, тогда B = № 4.
У пунктов G и E осталось по одному неотмеченному соседу, значит, C = № 3, D = № 8.
Находим длины дорог: GC = 26, ED = 12.
GC + ED = 26 + 12 = 38
Ответ: 38
В самом начале решения мы сказали, что пусть A = № 5, H = № 6. Если бы мы выбрали наоборот, то GC была бы 12, а ED — 26, но сумма дорог осталась бы той же.
Задача 3: симметричная с дополнительным условием
Поскольку расположение вершин на графе не имеет значения (важны лишь их связи между собой), перенесём для наглядности пункт Д в другое место. Обратим внимание, что граф симметричный.
Отметим количество дорог, выходящих из каждого города.
Для начала найдём город А. Из него выходит две дороги, как и из городов Г и Д. Кандидаты — № 4, 5 и 7. Только у города A есть общий сосед и с Г, и с Д.
Выпишем соседей:
№ 4 — № 2, № 6
№ 5 — № 2, № 3
№ 7 — № 1, № 6
Город A = № 4, у него есть общий сосед как с № 5, так и с № 7.
Из города А дороги идут в Б и В, по табличке — в № 2 и № 6. По условию задачи длина дороги АБ меньше дороги АВ, тогда АБ = 4, АВ = 6. Следовательно, Б = № 2, В = № 6.
Из таблицы видно, что город Б связан с № 3, у которого три дороги, и с № 5, у которого их две. Посмотрев на граф, видим, что Г = № 5, Е = № 3.
Оставшийся пункт № 7 с двумя дорогами — Д, Ж = № 1.
ДЖ + ВД = 18 + 17 = 35
Ответ: 35
В этой задаче хоть и был симметричный рисунок, но только дополнительное условие позволило однозначно определить номера городов.
Задача 4: усложнённая асимметричная
Подпишем количество дорог, выходящих из каждого города.
Все города имеют либо три дороги, либо две, и явно никто не выделяется. Рассмотрим те, что с двумя дорогами. A и B связаны между собой, а E находится отдельно от них.
У пунктов № 2, 4 и 7 по две дороги. № 2 и № 4 связаны между собой, значит, Е — № 7.
По аналогии рассмотрим вершины C, D, F, G, из которых выходит по 3 дороги. D, F, G связаны между собой, а город C — только с G. № 1, 3, 5 и 6 имеют по 3 дороги — обратим внимание на их связи.
№ 1 связан только с № 5, единственным из этой четвёрки, а № 5 — ещё и с двумя оставшимися: № 3 и № 6. Тогда G = № 5, C = № 1.
У города С остаётся один неотмеченный сосед — № 4. По рисунку видим, что это город A.
У города A остаётся один неотмеченный сосед — № 2. Значит, B = № 2. Аналогично находим D = № 6, F = № 3 — последний оставшийся.
Находим длины дорог DG = 8, AC = 30.
30 + 8 = 38
Ответ: 38
Итог
Универсального алгоритма для решения всех подобных задач не существует, однако наиболее эффективной стратегией будет следующий подход:
- Анализ степеней вершин (количество дорог, выходящих из каждого города). Часто нахождение городов с уникальным количеством дорог становится началом решения
- Изучение соседей. Если степени вершин совпадают, следует обратить внимание на то, с какими именно соседями (их количеством и особенностями) они соединены
- Действуйте от известного к неизвестному. Как только нашли хотя бы один город, его связи становятся ключом к определению номеров его соседей и дальнейшему заполнению схемы
Предлагаем решить подборку задач.