Приключение Твайлайт в смежной матрице

Приключение Твайлайт в смежной матрице

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

—Дискорд побери! Это та же самая вершина! V7, я сразу поняла, что-то здесь не так! Принцесса, это было не просто ребро, это была петля!

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

В покоях Принцессы пахло чем-то странным, смесью скуки, смертельной опасности и старого пергамента: вещи, довольно странно сочетаемые вместе. Неудивительно, что нос Селестии немного скривился. Они вместе с Твайлайт пытались проникнуть в тайные знания Старсвирла Бородатого. Какой бы мудрой Селестия ни была, многие его заклинания до сих пор оставались за гранью ее понимания. Вот уже третий час Твайлайт находилась внутри одного из них. Магическая вспышка переместила ее на пергамент и сделала невидимой точкой без размера и массы, перемещающейся по трехмерной модели внутри листка.

Суть заклинания состояла в раскрытии магического потенциала единорогов, но сработало оно совершенно по-другому. Твайлайт закинуло прямиком в сложные магические конструкции, которые Старсвирл чертил под старость лет: те самые знания, которые никто еще не понял. Наверное, потому что невозможно понять что это, не побывав там внутри. Твайлайт попала в математический граф.

—Я не понима… что происходит! Я пыталась бежать в обратном направлении… Ничего не выходит, меня уносит куда-то!— по ментальной связи до Селестии доходили обрывочные фразы верной ученицы. Принцесса еще раз взглянула на пергамент, лицо ее посуровело. Ну конечно, как она могла не заметить!

— Твайлайт! Твайлайт, ты слышишь меня?

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

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

Твайлайт непонятно зачем кивнула и огляделась по сторонам. Пока ее несло своим маршрутом, она успела увидеть множество странных вещей. Некоторые вершины находились далеко от основного графа, к ним не шли никакие дуги. «Наверное, те самые изолированны вершины, которыми меня пугала Селестия», — подумалось Твайлайт. Один раз ее занесло в какой-то водоворот и он забарахталась в черных завихрениях, испуганно отфыркиваясь.

— Селестия! Селестия, что это такое!

Лицо правительницы сосредоточенно изучало бумагу, на которой была изображена модель графа, в котором вращалась Твайлайт.

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

И действительно, не успела Твайлайт сделать и сто семнадцати оборотов, как ее уже несло куда-то в сторону. Впереди маячило громоздкое пятно вершины V12. Кстати, нумерация дуг и вершин была отмечена ровным счетом нигде. Цифры сами вспыхивали у Твайлайт в сознании, она даже не могла объяснить процесс. Почему та или иная вершина носит свой номер, оставалось для нее загадкой — как будто невидимая рука подписала их наобум. Единственное, что она заметила в основном нумерация вершин была последовательной, маршруты шли от меньших чисел к большим. V12 была совсем близко, как вдруг пони больно ударило носом в какую-то стенку. Мир вокруг поплыл черными пятнами.

— Селестия! Селестия! Здесь что-то очень странное! — Твайлайт в испуге шарахнулась, но грани клетки держали ее прочнее любых веревок. Она оказалась в длинном строе нулей и единиц, заняв место одной из них. — Тут куча цифр! Я не могу понять где я! — безуспешно надрывалась Твайлайт в пустоту. Граф куда-то пропал, оставляя Твайлайт в одиночестве.

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

— Я покопалась немного в теории графов и поняла, что каждый граф можно выразить с помощью матрицы. Хлюп, — Селестия бесцеремонно глотнула горячего чая. — Ты сейчас внутри матрицы. Осталось узнать внутри какой, и мы мигом тебя оттуда вытащим.

— Я… А как это определить? — Твайлайт потрогала гудящую стенку матрицы. Та согнулась словно резинка. Твайлайт попыталась пробить ее копытом, но тщетно: один раз копыта отпружинили обратно так сильно, что бедная пони упала и поцарапала бок. — И нельзя ли побыстрее это сделать? — сердито закончила пони, потирая копытом больное место.

— Очень просто, — живо отозвалась Принцесса которой путешествие Твайлайт казалось сейчас очень интересным занятием. Она даже пожалела, что сама туда не попала. — Есть матрица смежности, она будет размерностью V на V, то есть квадратной матрицей, где V – количество вершин. Значит, в твоем случае, это будет матрица двенадцать на двенадцать! — раскинула копытами Селестия перед невидимым собеседником. — Но не дай бог тебе попасть в матрицу инцидентности. Это матрица V на X, где X количество ребер или дуг. Она не квадратная. Из квадратной же матрицы я быстро тебя вытащу.

Несколько натужных скачков и фырчания, и Твайлайт уже переместилась на несколько нулей и единичек влево. Она решила идти вдоль стенки, чтобы не потеряться.

— А как вы собираетесь вытащить меня?

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

— И почему же вам нужна только квадратная матрица, Принцесса? — Твайлайт устала бежать и прыгать, и привалилась спиной к ближайшей единичке. Голос Селестии звучал уверенно, но Твайлайт заметила легко подрагивание, как в день прихода Найтмер Мун.

— Потому что… Потому что для того, чтобы сделать единичную матрицу, нужно умножить исходную матрицу на обратную… — растягивая слова, в замешательстве начала Селестия.

— И?.. — для Твайлайт это был пустой набор звуков.

— Для неквадратных матриц обратных матриц не существует. Я не смогу вытащить тебя по единичной матрице, потому что не смогу ее сделать.

От неожиданности Твайлайт прошиб холодный пот. Перед глазами быстро пронеслись картины утреннего Понивилля, облики друзей и знакомых, но стоило моргнуть и вместо них появлялись уродливые цифры. «Не желаете ли чаю?», — Флаттершай в красочном видении повернулась, но вместо лица у нее был большой жирный ноль, с глазками-единичками. Нули были везде, на подносе, на клетчатом фартучке, скакали по цветастым обоям на стене. Твайлайт с ужасом обернулась — на нее прыгал пушистый белый ноль-Энджел с подрагивающими ушками единицами.

Твайлайт вскрикнула от неожиданности и поняла, что валяется в пространстве между цифрами. Наваждение спало. Она судорожно стала сновать между нагромождением цифр, пытаясь сосчитать сколько именно их в каждом ряду.

— Одиннадцать, двенадцать… — строчка обрывалась, и Твайлайт оказалась перед обрывом. Ряд нулей и единиц уходил вниз.

— Теперь считай столбцы, — осторожно обронила совет Селестия.

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

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

— Отлично! Сейчас я быстренько приведу матрицу к единичной путем Гаусса-Жордана, и ты спасена! — карандаш быстро зачеркал по испачканной чаем бумаге.

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

— Твайлайт…

— Что-то не так? — Твайлайт вскочила на ноги, потому что голос Селестии выдавал ее с головой. Еще не слыша ответ на свой вопрос, Твайлайт уже знала — да, что-то не так.

— Твайлайт, твоя квадратная матрица… Она вырожденная…

— Что то значит?

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

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

Обессиленная Твайлайт прилегла около свободной единички.

—Почему сюда не ходит никакой транспорт! Вот бы приехала повозка… Или поезд, — Твайлайт с грустью подумала о железной дороге Понивилль-Кантерлот. Почему нельзя было построить еще одну, Понивилль-Квадратная вырожденная матрица?

Причитания стихли.

—Что-что ты там сказала? Повтори, — раздался громкий голос Селестии.

— Говорю, жаль сюда поезда не ходят…

— Не это! Что-то еще! — Селестия явно пыталась ухватиться за какую-то мысль.

— Ну, или вообще любой транспорт, — замешкавшись, продолжила Твайлайт. «Может Селестия умеет строить железные дороги до матриц? Хотя, ей лучше позвать Пинки на такой случай», — пронеслось в голове у пони.

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

Твайлайт растянулась вдоль единички, вопросительно подняв брови.

— Точно, что?

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

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

Чернота свернулась вокруг Твайлайт, когда сверху посыпался град из единиц. Она пыталась отмахиваться, но копыта увязали в их черной материи, замедляя движение. Она попыталась закричать, но ее крик тонул в общем гомоне и наставительном голосе Селестии, слова которого невозможно было разобрать.

— Я должна выбраться из матрицы! Я должна выбраться из смежной матрицы! — закричала Твайлайт и больно-больно ударилась головой об настольную лампу. Потирая затылок, она оглянула слипшимися глазами библиотеку.

— Твайлайт, с тобой все в порядке? — Спайк проснулся от громкого крика и прибежал к рабочему столу Твайлайт. За ним был жуткий беспорядок, видимо, Твайлайт заснула прямо во время работы.

— Ничего, ничего Спайк. Я просто задремала за учебой и мне приснился очень странный кошмар. Иди спать, я тоже скоро пойду, — она потрепала дракончика копытом по гребешку.

Спайк с любопытством посмотрел на открытую на столе книгу, но Твайлайт щелкнула любопытного дракона по носу и отправила книгу на полку. В последний момент, Спайк успел увидеть надпись на корешке:

«М.А. Тан. Учебник по линейной алгебре и основы теории графов».

Спайк пожал плечами и отправился спать, а Твайлайт еще долго смотрела на вычисления в лиловой тетрадке.