Мартинюк Ю

Много алгоритми за обработка на мрежова информация се основават на алгоритми за обхождане (итерация) на графики, в процеса на които се търси необходимата информация или се определят някои характеристики на мрежата. Теорията на графиките, като самостоятелна математическа дисциплина, се формира през тридесетте години на ХХ век и е намерила широко приложение в много клонове на науката и техниката. Методите на теорията на графовете се използват успешно в теорията на информацията, планирането на производството, генетиката и химията, транспорта, маршрутизирането на данни в Интернет и много други области на науката, технологиите и обществения живот. Теорията на графиките е основният инструмент за обработка на интересни обекти като лабиринти.

В исторически план лабиринтите първоначално са имали мистичен и алегоричен статус, след това са били използвани като елементи на културата на ландшафтно градинарство и на практика не са били разглеждани като интересен математически обект. Всичко се промени през втората половина на 20 век. Развитието на роботиката, проблемите, свързани с автоматизацията на дизайна на електрониката - всичко това накара човечеството да погледне наново лабиринтите, да види математическата им същност, да ги разглежда като математически обект и напълно да оцени практическото им значение.

По-нататък се използват следните понятия и определения:

Лабиринт е всяка структура, която се намира в двуизмерно или триизмерно пространство и се състои от сложни пътеки към изхода. Тези пътеки представляват последователност от местоположения;
Мястото е стая, включена в лабиринта и има не повече от четири съседни стаи, всяка от които може да бъде достъпна чрез проход, и само една. При липса на проход, местата са отделени едно от друго със стена;
Решението на лабиринта е търсенето на маршрут, който свързва някакво начално (начално) местоположение и различно крайно (крайно) местоположение.

По отношение на лабиринтите могат условно да се разграничат два основни проблема, чието решение позволява използването на лабиринти в гореспоменатите приложни области: проблемът за изграждането на лабиринт и проблемът за намиране на път в лабиринт. Инструментариумът за решаване на тези проблеми се предоставя от такава област на математическата наука като дискретна математика, която включва теория на графовете, въз основа на която е възможно да се формализира лабиринта с цел по-нататъшната му обработка.

Лабиринтът може да се разглежда като колекция от три комплекта. Първият набор включва много места, които съдържат лабиринт. От гледна точка на теорията на графовете, това е съвкупността от върхове на графа. Вторият набор е някакъв краен набор от ръбове - проходи между местата. Третият набор свързва двойка местоположения с определен проход, свързващ тези места, и само един. Следователно лабиринтът може да бъде представен като графика.

Въз основа на разпоредбите на теорията на графовете е възможно да се формализира лабиринтът, който ще се състои в определяне на клас графики, чийто представител е произволен лабиринт.

На първо място е необходимо да се определи дали лабиринтът трябва да е свързана графика, т.е. дали всеки два върха на дадения граф могат да бъдат свързани чрез верига от ребра. Нека приемем, че това твърдение е вярно. Следователно не може да има лабиринти, които нямат решение за някои двойки точки (местоположения). От друга страна, определението за лабиринт не изключва възможността за две произволни точки да не съществува маршрут, свързващ ги, което всъщност води до противоречие. Оттук можем да заключим: графика, която е формализация на произволен лабиринт, не е свързана.

Сега е необходимо да проверите дали графиката е диграф или насочена графика, тоест графика, за която е дадена посоката на всички ръбове (дъги). Проход, свързан с ориентиран ръб, може да бъде преминат само в избраната посока. Но определението за местоположение не съдържа изискването невъзможно да се премине един и същ ръб в различни посоки, което поражда друго противоречие. Това означава, че графиката, описваща произволен лабиринт, не е насочена - всички нейни ръбове нямат посока.

Остава да разберем дали графиката може да съдържа множество ръбове (различни ръбове, свързващи едни и същи върхове) или цикли (ръбове, които имат едно и също начало и край). Произволно разположение на лабиринта, съответстващо на даденото по-горе определение, не може да съдържа проход, водещ до същото място. По този начин графиката не може да съдържа цикли. Наличието на множество ръбове предполага наличието на два или повече прохода между местата, което също противоречи на горната дефиниция на местоположение. По този начин можем да заключим, че графиката на произволен лабиринт е проста, тоест не съдържа цикли и множество ръбове и не е насочена.