«Я знаю короткую дорогу!»: теория графов
Что такое граф? Важный мужчина со шпагой и слугами? Или, может, производное от греческого слова grapho — «пишу»? У графа, о котором мы будем говорить, нет дворянского титула, но написать его вы сможете. Давайте поближе познакомимся с особенными математическими путями, а заодно прогуляемся по городу и найдем смысл в странных, но красивых рисунках.
Граф — абстрактная модель, которая состоит из множеств вершин и соединяющих их ребер. Он показывает, как множество элементов связаны между собой. Такая модель наглядно визуализирует задачи и помогает с их решением.
Граф можно записать в виде множества: G = {V, E} (G — граф, V — вершины, Е — ребра, скобочки обозначают множество)
Вершинами и ребрами могут быть любые объекты: города и дороги между ними, атомы и их связь в молекулах, компьютерные файлы и путь к ним из папок.
Степень вершины — показывает, сколько ребер входит в нее. В зависимости от количества ребер вершины бывают четные и нечетные.
Цикл — цепь, в котором последняя вершина совпадает с первой.
В граф могут входить разные циклы, но и цикл может быть отдельным графом.
Теория графов — раздел дискретной математики, который изучает графы.
Графы — это инструмент. Они не могут сами решить задачу, но с их помощью получится упростить и обобщить решение, выдвинуть гипотезы, подвердить теории. Проследив путь из одной вершины в другую, можно понять, как вещи связаны между собой. А еще графы геометрически наглядны.
Теория графов появилась в XVIII веке. Вначале ее использовали, чтобы решать математические головоломки. Основоположником теории графов считают математика Леонарда Эйлера. Он первым сформулировал решения сложных задач с помощью новых алгоритмов.
Задача о мостах
Представьте, что вы гуляете по городу, в котором много мостов. Получится ли у вас построить маршрут так, чтобы пройти по каждому мосту только один раз и вернуться в начало прогулки?
Впервые похожую задачу пытались решить жители Кенигсберга (сейчас — Калининграда) 300 лет назад. У них было семь мостов и огромное желание погулять. Давайте переделаем задачу под наш город. Допустим, вы решили обойти все мосты Семимостья: Красногвардейский, Ново-Никольский, Кашин, Пикалов, Могилевский, Старо-Никольский и Смежный.
Если упростить маршрут и представить мосты в виде ребер, которые соединяют острова–вершины, получится так:
Попробуйте провести линию, которая бы проходила по каждому мосту только один раз. Спойлер: у вас получится!
А теперь представьте, что вы не хотите идти до Фонтанки, и уберите Смежный мост из маршрута.
Теперь провести линию без повторений у вас не выйдет.
Есть способ сразу понять, будут ли соблюдаться условия этой задачи. Для этого используют свойства графов, которые сформулировал Эйлер в XVIII веке. Нарисовать граф, не отрывая руку от бумаги и вернувшись в исходную точку, можно, если все вершины графа четные или нечетных вершин не больше двух.
Давайте посчитаем вершины в наших графах. В первом случае есть две четных и две нечетных вершины: правило соблюдается, линия проводится. Во втором варианте изменилось количество ребер: все вершины стали нечетными. Поэтому провести линию не получится. Так вышло и с мостами Кенигсберга: все вершины графа для этой задачи были нечетными.
Зачем нужны графы?
Графы широко используют в программировании и машинном обучении. Они представляют данные в виде структуры. Это нужно, чтобы построить оптимальный короткий путь, например в файловой системе или компьютерной сети. Теория графов наглядно представляет сложные взаимосвязи в данных, которые потом используют в машинном обучении. Еще графы решают задачи информационной безопасности: с помощью них анализируют поведение пользователя и обнаруживают мошеннические действия.
Графы применяют не только в технических, но и в естественных науках. Врачи могут построить математическую модель и проанализировать, как между собой взаимодействуют гены или белки. С помощью графов можно понять, на какие «мишени» в организме стоит воздействовать лекарствами, и назначить эффективную индивидуальную терапию. Дополнительно используя машинное обучение, нейробиологи изучают, как разные части мозга связаны друг с другом.
Фото на обложке: habr.com
