Ах, математика и графы – это как семейные посиделки: вроде бы все понятно, но без головоломок и загадок не обойтись! В прошлый раз мы уже познакомились с матрицей смежности, то есть с тем самым «картографическим Tinder», где вершины ищут свои пары – рёбра.
Теперь же пришло время перейти на следующий уровень и выяснить, как определить длину пути между двумя пунктами на графе. Звучит серьёзно?
Да ничего подобного! Это почти как искать самый короткий путь до холодильника в час ночи – задача знакомая каждому.
В общем, представьте себе район N-ский (да-да, именно так его назвали – видимо, у местных чиновников фантазия закончилась на букве N).
На рисунке у нас есть схема дорог в виде графа, а в таблице красуются километры каждой дороги. Но тут начинается веселье: нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Это примерно как если бы вы получили карту сокровищ от пирата с пометками на древнем языке – всё загадочно и непонятно. Но не беда!
Мы же не из робкого десятка.
Сначала берёмся за расстановку степеней вершин. Если вы думаете, что степень вершины – это похоже на школьный балл по математике, то нет. Здесь степень вершины — количество дорог (отрезков), которые из неё выходят.
Например, из вершины G выходит три дороги – значит её степень равна трём. Можно сказать, что G – такой тусовщик среди вершин: всегда в центре событий!
Далее мы разбираемся с необычными вершинами.
В нашем случае это E – единственная вершина, которая соединяется с двумя тройными (то есть такими же тусовщиками). Найти её на матрице — это как искать иголку в стоге сена или Wi-Fi сигнал в подвале: нужно перебирать строки и смотреть на числа.
И вот тут начинается настоящее шоу! Мы перебираем строки: строка 2 не подходит (там всего два числа), строка 4 тоже нет (в столбце 2 всего два числа вместо трёх), а вот строка 7 идеально подходит! Значит E имеет номер 7.
Кстати, эта методика напоминает мне старый анекдот про программиста: «Почему программисту сложно найти жену? Потому что он ищет совпадения по всем параметрам сразу».
Вот и мы ищем совпадение условий для номера E.
После того как нашли E (номер 7), можно предположить номера для F и C (1 или 3). Тут нам помогает анализ соседей: F соединяется с двумя тройными и одной двойной вершиной; C — наоборот. Разбираемся со строками матрицы и наконец понимаем: C — номер 1, F — номер 3.
Затем идём дальше к вершине G: она соединена с C(1), F(3) и ещё одной тройной D.
Ищем строку с этими условиями и… бац! Это строка 5.
Значит G — номер 5.
Весь этот процесс напоминает мне забавную историю про дедушку и смартфон: дедушка долго искал кнопку «выключить», пока внучка не объяснила ему алгоритм действий шаг за шагом. Так и здесь — сначала кажется сложным лабиринтом цифр и букв, а потом всё становится ясным.
Ну а чтобы закрепить успех и сделать финальный аккорд нашего путешествия по миру графов достойным концертом рок-звезды информатики, мы решим пару примеров программно – ведь ручное решение это хорошо для разминки пальцев перед клавиатурой.
Так что вооружайтесь терпением, юмором и калькулятором – впереди новые приключения в мире ЕГЭ по информатике! А если вдруг запутаетесь в степенях вершин или нумерации матриц – вспомните старую шутку про студента: «Если не понимаешь задачу — придумай свою!» Только лучше придерживайтесь нашего алгоритма решения.