Начало: Математика для чайников. Глава 1. Что такое математическая абстракция.
Предыдущая глава: Математика для чайников. Глава 14. Производная
Важность теории графов трудно переоценить. Казалось бы, что такое граф? Просто набор стрелочек. Просто схема. Но вокруг этой незамысловатой схемы из стрелочек построена целая теория. И эта теория нашла очень широкое применение. Но почему? Давайте разберемся. Где можно применить такой объект, как граф? Первым делом напрашивается задача построения маршрута, как это делают навигаторы. Действительно, маршрут – это граф. Схема из стрелочек. Но это не единственное применение теории графов. Где у нас еще есть схемы? В электротехнике: есть электрические схемы. Есть схемы гидравлические, кинематические. Есть всякие иерархические схемы, которые применяются в бизнес графике. И все это по своей сути графы. В виде графа мы можем, например, представить семантическую сеть (схему отношений между словами). Нейронная сеть (из искусственного интеллекта) – это тоже граф. Вообще, любую задачу, где есть объекты и отношения между ними, можно представить в виде графа. И таких задач очень и очень много.
Но довольно вступления. Перейдем непосредственно к теории. Для начала, давайте определимся, что такое граф с точки зрения математики. Начнем сразу со строгого определения:
Не пугайтесь, если формула покажется вам страшной. Сейчас мы ее разберем. Вот такое выражение:
означает граф как функцию от двух переменных V и E, где V – это множество вершин (см. так же Математика для чайников. Глава 7. Множества), а E – множество ребер. По сути, граф, с точки зрения математики – это совокупность двух множеств. Но не просто двух каких-либо любых множеств, а определенных множеств, на которые в той же формуле (15.1) наложены некоторые ограничения. Во-первых, граф должен иметь хотя бы одну вершину (не бывает графов без вершин), то есть, множество вершин не пустое:
Во-вторых, ребро графа соединяет две точки, поэтому множество ребер является подмножеством декартова произведения множества его вершин. Под декартовым произведением двух множество понимается множество паросочетаний всех их элементов. Каждый элемент первого множества сочетаем с каждым элементом второго множества. В нашем случае имеет место декартово произведение множества само на себя, то есть каждый элемент этого множества сочетается с каждым элементом этого же множества. Действительно, каждую вершину можно соединить ребром с каждой вершиной.
Так же предполагается, что ребро не может соединять вершину саму с собой:
Но это утверждение спорное. Например, представим, что у нас есть несколько мест, соединенных дрогами. Может дорога сделать петлю и привести в тоже место? Может. Но как тогда представить все это в виде графа? Для этого существует подвид графов, называемых псевдографами, где нет этого ограничения.
Как я упомянул выше, многие задачи можно свести к графам. Для решения данных задач существуют разнообразные алгоритмы на графах. Например, обход графа. При обходе графа мы просто берем определенную вершину и по определенному правилу идем по этому графу, пока не обойдем его. Как правило, мы при этом запоминаем те вершины, где уже были, чтобы «не заблудиться». Если этого не делать, то вполне можно зациклиться и зависнуть в бесконечном цикле, если в графе есть так называемые замкнутые циклы:
Здесь мы видим замкнутый цикл 2,4,3.
Теперь о конкретных алгоритмах обхода графов. Наиболее простые из них это обход графа в ширину и в глубину. При обходе в ширину мы раскрываем все ребра заданной вершины, и эту операцию делаем для каждой из вершин, куда ведут эти ребра. За исключением, конечно же, вершин, которые мы уже посетили.
Рассмотрим процесс обхода графа в ширину более наглядно. Пусть у нас есть вот такой граф:
Начинаем обход с первой вершины:
Из нее есть ребра к вершинам 2,3 и 6:
Теперь по очереди раскрываем вершины 2,3 и 6. В каком порядке их раскрывать, отдельный разговор. Допустим, мы раскрываем их в порядке возрастания номеров. Тогда сначала мы раскроем вершину 2, она ведет в вершину 4 и 6, но в вершине 6 мы уже были. Вершина 3 ведет в вершину 2, мы там тоже были. И вершина 6 ведет в вершину 5:
Раскрываем так же вершины 4 и 5. Из вершины 4 идем в вершину 7, из вершины 5 тоже в вершину 7. Но там мы уже были. Обход завершен. И теперь всю эту последовательность обхода вершин мы можем представить в виде дерева:
Теперь рассмотрим обход графа в глубину. В отличии от обхода в ширину, в этом случае алгоритм не переходит к следующей вершине, пока не раскроет полностью все ребра рассматриваемой вершины. Это справедливо и для тех ребер, которые он будет рассматривает. То есть, алгоритм будет спускаться все глубже и глубже, пока не дойдет до конечной вершины либо до той вершины, где он уже был. В этом случае он возвращается на уровень назад и начинает делать то же самое с соседней вершиной (если она еще не рассмотрена). Давайте посмотрим, как это будет выглядеть на практике.
Рассмотрим все тот же граф, начиная с первой вершины:
Раскрываем у него вторую вершину:
Из вершины 2 идут ребра в вершины 4 и 6, раскрываем сначала 4:
Теперь, по идее, нам надо раскрыть вершины 5 и 7. Начинаем с 5:
Из нее есть ребро только в 7:
И все, больше нечего раскрывать. Возвращаемся назад. В вершину 4. Из нее мы можем пойти в 3:
А дальше тоже идти некуда – вершина 2 уже раскрыта. Возвращаемся в 4, смотрим, что нераскрытых вершин больше нет, возвращаемся в 2. Из нее мы можем пойти в 6:
Из вершины 6 мы вынуждены вернуться – дальше идти некуда, в вершине 5 мы уже были. Вершина 2 полностью раскрыта, возвращаемся в 1 и видим, что обход графа закончен. Получилось вот такое вот дерево:
Замечу, что обход графа в ширину и в глубину наиболее простые алгоритмы на графах. Кроме них есть еще ряд других алгоритмов и задач на графах, например:
· Алгоритм Дейкстры. Это алгоритм нахождение кратчайшего пути из вершины А в вершину Б. Под длиной пути подразумевается сумма весов всех ребер, которые приходится обойти.
· Моделирование транспортной сети.
· Задача коммивояжера. Нужно найти кратчайший путь через заданные города, вернувшись в исходный город.
· Различные поиски подграфа внутри графа и другие.
Так же в теорию графов входят такие разделы, как классификация графов, способы представления графов и другие.
