Что такое граф и с чем его едят?

Исходя из того, что вы сейчас читаете эти строки, можно предположить, что вы решили ознакомиться с таким понятием, как граф, и соответствующим материалом. Похвально. Несмотря на то, что данный учебник ориентирован на людей, до сих пор о графах ничего не слышавших, индивиды продвинутые в этой области смогут систематизировать свои текущие знания и понять, как мало они на самом деле знают (шутка, хотя такое вполне возможно). В данном учебнике будут представлены основы теории графов и наиболее распространённые алгоритмы, решающие различные задачи на графах.

Итак, перейдём теперь непосредственно к процессу обучения. По определению, граф - это совокупность вершин и рёбер. Иными словами, нам дан набор вершин, некоторые из которых соединены рёбрами. Вот и всё, ничего сложного. Граф - это просто некотороя математическая структура. Пусть, например, существует гипотетический архипелаг островов в океане, некоторые из которых соединены мостами. Нам нужно добраться с одного острова на другой, причём в этом случае, логично, нам не интересна ни форма островов, ни внешний вид мостов. Для исполнения задуманного нам вполне может пригодиться упрощённая карта архипелага, где острова обозначены точками, а мосты - соединяющими их отрезками. Такая карта представляет собой граф в чистом виде, глядя на неё, мы можем спланировать своё перемещение по островам. Может, не слишком практично, зато очень наглядно.

Другой пример: в некотором царстве, в некотором государстве, есть некоторое количество деревень, некоторые из которых соединениы дорогами. Король (или царь) решил заняться туризмом и, путешествуя по дорогам своей провинции в роскошной карете, посетить все свои федеративные субъекты (деревни), причём побывать в каждом федеративном субъекте (деревне) ровно один раз. Составление плана путешествия он, разумеется, переложил на головы ни в чём не повинных чиновников транспортной сети. Как раз для составления подобного плана им очень даже пригодится план дорожных связей империи; на сём плане будет очень разумно обозначить деревни точками, т.к. их форма не имеет для светлейшего государя никакого значения, и соединить отрезками те из них, которые в реале соединены дорогой. Кстати, путь в графе, проходящий по каждой его вершине ровно один раз, называется Гамильтоновым, и эффективного алгоритма по его поиску на данный момент не существует (вероятнее всего, такого алгоритма не существует вообще). Так что чиновникам придётся лихо.

Не забывайте, вершины графа могут обозначать всё, что угодно. Еще пример: всем известная игра пятнашки, в которой, двигая костяшки с числами от 1 до 15 на замкнутом поле, нужно выстроить их в правильном порядке. Закодируем все возможные состояния игрового поля числами, поставим каждому числу в соответствие вершину и соединим рёбрами вершины, если соответствующие им поля получаются друг из друга путём одного перемещения костяшки. После этого в получившемся графе найдём путь от исходной вершины, до вершины, обозначающей конечную позицию. Фишка в том, что в этом случае мы вполне можем найти кратчайший путь, то есть решить головоломку за наименьшее число ходов (в последствии вы поймёте, что в данном случае искать кратчайший путь едва ли не проще, чем любой, используя так называемый поиск в ширину). Единственный минус подобного решения задачи в том, что в графе будет 16! = 20 922 789 888 000 вершин... Но это не важно.

А вы играли в "Братьев Пилотов", там, где надо спасать кота Мышьяка? Если да, то помните, там есть холодильник с вентелями? Кто не знает, там дано поле 4х4, в каждой клетке которого расположен вентель в горизонтальном или вертикальном положении, и за один ход можно выбрать вентель и поменять положения всех вентелей в одной с ним строке и столбце (из горизонтального - на вертикальное, или наоборот). В результате все вентели должны оказаться в одном положении. Так вот, эта задача элементарно решается, если представить все состояния холодильника как вершины графа, и соединять две вершины ребром, если состояние, соответствующее одной получается из состояния, соответствующего другой, в результате одного хода. Ищем в этом графе путь от исходного состояния до одного из конечных, когда все вентели горизонтальны, или все вертикальны. В этом случае количество вершин равно всего-навсего 2¹⁶ = 65536.

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