Предыдущий урок.
Первый урок.
Я уже писал о теории графов в уроке
Математика для чайников. Глава 15. Теория графов. Введение. | Александр Шуравин. | Дзен (dzen.ru)
В этой главе описано математическое определение графа и рассказано о некоторых алгоритмах на графах. Кажется, что все просто. Но на самом деле, если вы решите углубиться в эту науку и откроете какой-нибудь учебник, то просто утоните в обилии различных терминов, определений и теорем. Эта глава признана быть неким гидом, позволяющим ориентироваться в терминологии теории графов и лучше понять эту важную науку.
Итак, как уже сказано в главе по ссылке, граф – это совокупность множества вершин и множества ребер. Он может быть задан как списком узлов с примыкающими к ним ребрами, так и списком ребер с примыкающими к ним узлами. Кроме того, граф можно задать матрицей смежности и инцидентности. Но мы до них еще доберемся.
Итак, поехали. В глава 15 мы определи граф как совокупность множества точек и вершин. Но есть и другой подход. Пусть у нас даны множества V1 и V2. Тогда мы можем обозначить множества всех пар:
Такое множество пар называется декартовым произведением. Нетрудно догадаться, что количество таких пар равно произведению количества элементов во множестве V1 на количество элементов множеств V2.
Если множество всех вершин графа обозначить как V, то пара (a, b), где:
есть ребро данного графа. Тогда мы можем сказать, что граф G(V) есть некоторое подмножество декартова произведения
Но тут есть важный нюанс. Если мы рассматриваем граф как множество сочетаний вершин из множества V, у нас возникает вопрос, а важен ли порядок расположения двух концов вершины. То есть, верно ли утверждение, что:
где E – множество ребер графа. Если эта утверждение имеет место быть, то такой граф называется неориентированный, то есть, ребра не имеют направления, иными словами, они не стрелки, а просто палочки, то есть вот так:
А если
То граф ориентированный (его ребро стрелка), то есть, какой-то вот такой:
Теоретически могут быть и смешанные графы, когда в одном случае
или нет стрелки, в другом случае
то есть, есть стрелка. В этом случае можно говорить об ориентированных и неориентированных ребрах. В первом случае вершина a называется начальной вершиной (откуда исходит стрелочка), а вершина b – конечной вершиной (куда направлена стрелочка). Ребро, кстати, так и называется отходящее (исходящее) от вершины a и входящее (заходящее) в вершину b.
Еще есть такое понятие, как инцидентность. Не важно, ориентированный у нас граф или нет, но в данном случае говорят, что ребро e, где
инцидентно вершинам a и b, а вершины a и b инциденты ребру e (обе вершины).
Теперь вернемся к ориентированности и не ориентированности. Как вы поняли, ориентированным или нет может быть как граф, так и конкретное ребро. С ребром все понятно. Стрелка – ориентированное ребро, «палочка» – не ориентированное. А как быть с целым графом. А с целым графом так: граф неориентированный, если все ребра в нем неориентированные. Если все ребра ориентированные, то и граф тоже ориентирован.
Как я уже говорил, бывают и смешанные графы. Пример такого графа – сеть автомобильных дорог, в которой часть дорог с двухсторонним движением (неориентированное ребро), а часть с односторонним (ориентированное ребро). Правда, такой граф можно свести к ориентированному графу, если считать, что неориентированное ребро, это просто два ориентированных ребра (a,b) и (b,a).
Один и тот же граф можно изобразить разными способами.
Например, вот у нас есть граф:
Но его можно нарисовать и так:
И так:
А можно вообще вот так:
Вот еще интересный пример:
Или даже эти графы можно изобразить вот так:
Если хорошо присмотреться, то видно, что это один и тот же граф!
Такое может создать проблему при анализе и сопоставлении графов. Приведу пример из моей магистерской работы. Я решал задачу навигации беспилотного летательного аппарата по кадрам установленной на нем видеокамеры. Одна из рассматриваемых идей состояла в том, чтобы сеть дорог, которая попала в кадр, распознать при помощи методов компьютерного зрения, превратить в граф и потом сопоставлять с реальными картами дорог, которые хранятся в памяти компьютера в виде графов. От этой идеи, правда, пришлось отказать в виду сложности реализации, и одна из проблем, как я уже сказал, в том, что один и тот же граф можно изобразить по-разному. Такие графы называют изоморфными.
И так, что такое изоморфные графы из этого простого примера, вы, наверное, поняли.
А теперь научное определение.
Графы G и G’ называют изоморфными, если существует такое взаимно однозначное соответствие между множествами вершины V и V’ соединены ребрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированные, то их направление в этих графах так же должны соответствовать друг другу.
Как это понимать? Давайте вернемся к первому примеру, и пронумеруем в графе вершины:
А теперь пронумеруем их по-другому:
Теперь введем соответствие: 1-2, 2-3, 4-3 и 4-1. Смотрим. В первом графе вершины 1 и 4 соединены. Им соответствуют вершины 2 и 1. Они тоже соединены. Вершины 1 и 2 не соединены. Им соответствуют вершины 2 и 3 второго графа. Они не соединены. Проверив так все пары соответствующих вершин во втором графе, вы убедитесь, что те вершины, которые соединены в первом графе, соединены и во втором (точнее, соответствующие им). Так же и для несоединенных вершин.
Если сказать простыми словами, мы можем в другом порядке пронумеровав вершины графа и получить изоморфный граф.
Вернемся к вышеупомянутой магистерской работе. Пусть после обработки изображений появились два графа и нам надо их сравнить. Они могут быть друг относительно друга повернуты, и не факт, что мы сможем во втором пронумеровать вершины точно так же, как и в первом. То есть, для того, чтобы сравнить графы, нам надо проверить, а не изоморфны ли они. Как? Перебрав все варианты и проверив в каждом варианте все узлы на идентичность. Но сколько же вариантов нам надо перебрать?
Давайте посчитаем. Возьмем для начала, тот граф с четырьмя вершинами. Первую вершину мы можем поставить в 4 положения. Вторую в 3. Таким образом, всего у нас 4! (четыре факториал) вариантов, то есть, 4*3*2*1=24. А если у нас будет не 4, а 10 вершин? Тогда у нас будет 10! =3 628 800 вариантов. И с увеличением количества вершин это количество растет очень быстро. При 20-ти вершинах количество вариантов исчисляется уже 19-ти злачным числом. Даже если на каждый перебор вариантов тратить всего лишь 1 так процессора (что невозможно, так как даже простая математическая операция занимает уже несколько тактов), то при тактовой частоте 10 гигагерц время обработки составит 2 432 902 008 секунд или 77 лет. А если у нас будет 30 вершин, то это время вырастет до 16-тизначного числа. Для сравнения, нашей Вселенной примерно 10 млрд. лет (11-значное число). Правда, предполагаемое время жизни Вселенной представлено 102-хзначным число. Но долго ли его догнать? Всего-то граф с сотней вершин и вот, для его полного перебора не хватит всего времени жизни Вселенной. Не говоря уже о графах с большим числом вершин. А теперь возьмите карту и попробуйте посчитать количество перекрестков в вашем городе. Уверен, вы насчитаете больше 100.
Существуют ли более оптимальные алгоритмы проверки графов на изоморфность без «тупого перебора»? Безусловно, существуют. У каждого из методов есть свои достоинства и недостатки. Но здесь я останавливаться на них не буду, этому потом будет посвящена отдельная статья. Озвучу лишь несколько идей:
· Использование хэш-функций от графов, и сравнивать эти хэш-функции.
· Поиск и сравнение специальный путей в графах.
· Специальные виды перебора с ограничением, который позволяет уменьшить количество сравнений. Часто такие алгоритмы увязаны с алгоритмов обхода графов в ширину или глубину
А мы пока изучим еще несколько понятий из теории графов. Давайте представим вот такой граф:
«Кто-то забыл ребро дорисовать», – скажите вы. Нет, не забыл. Это граф такой. Такой тоже бывает. Вершина (узел) не обязана быть инцидентной к какому либо ребру. Она может быть и сама по себе. Называется такая вершина изолированной. Научное определение изолированной вершины звучит так: вершина называется изолированной, если она не инцидента ни одному ребру. Скажу больше, граф может вообще не иметь ребер. Тогда каждая его вершина будет изолированной. И называется такой граф нуль-графом. По научному определение так и звучит: нуль-граф – это граф, который состоит только из изолированных вершин.
Еще один частный случай графа – переориентированный граф, или полный граф. В нем содержаться все возможные ребра между вершинами. Например:
В типовом определении графа ребро не может выходить из одной вершины и возвращаться в ту же вершину. Но для некоторых задач необходимо такое допущение. Для этих случаев придумали специальные ребра, называемые петлями. Петля – это ребро, обе концевые точки которого совпадают. Обычно такая петля изображается вот так:
Кроме того, можно расширить понятие графа, допуская, что пара вершин соединена не одним, а несколькими ребрами. Почему нет? Может же так быть, что две локации соединены несколькими дорогами? Может. Если эти несколько дорог соединяют два пункта назначения, и эти дороги соединяют только их, это и будут несколько ребер, соединяющих эти две вершины. Например, пусть эти две вершины графа – два города. Из одного города ведут две дороги, и по пути они не заходят в другие года. Вот наш случай.
Другой пример соединения двух вершин несколькими ребрами: команды и игры, когда они играли. Сыграли две команды несколько игр – вот и несколько ребер у вершин.
Для ориентированного графа существует такое понятие, как обратный граф, в котором каждое ребро заменено на противоположное по направлению. Кроме того, каждому ориентированному графу соответствует неориентированный граф, в котором все ориентированные ребра просто заменены на неориентированные. Иногда бывает удобно неориентированный граф превратить в ориентированный, заменив каждое ребро парой противоположно направленных ориентированных ребер.
И еще одно понятие из теории графов – плоский граф. Он называется так потому, что его можно изобразить на плоскости, так, чтобы ребра не пересекались. Например, вот этот граф плоский:
А вот этот вот – нет:
Итак, подытожим. В этой главе вы познакомились с некоторыми понятиями теории графов, такими как ориентированные и неориентированные графы, изоморфность графов, изолированные вершины, нуль-графы, петли, плоский граф, инцидентность.