Теория Графов. Часть 1 Введение и классификация графов
«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Граф — это совокупность пары множеств. Конечного есть и бесконечные, однако мы их пока не рассматриваем непустого множества V и множества E заданного неупорядоченными парами множества V.
Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степенью вершины — является количество рёбер исходящих выходящих из вершины и входящих в нее. Данное определение верно для ориентированных графов см. классификацию графов. Для неориентированных графов исходящая степень равна входящей. Степенью вершины 1 будет является число 4. Так как вершина 1 соединена с вершиной 2, 3, 4, 5.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Самое главное в графе это вершины и проведенные между ними рёбра. В связи с этим граф является топологическим объектом, а не геометрическим . То есть объектом который не меняется при любых растяжениях и сжатиях. Нам все равно какой мы сделали отрезок. Кривой, прямой, самое главное это наличие связи между вершинами. По этой причине графы являются очень универсальными в плане практического применения. Мы можем обозначать ими дороги, компьютерную сеть, людей которые дружат друг с другом или даже влюблены друг в друга.
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Неориентированный граф
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Смешанный граф
Вторым признаком является отсутствие или наличие кратных ребер.
Кратные ребра — это ребра которые встречаются между двумя вершинами сразу несколько раз. В примере ниже мы видим, что вершина a соединена с вершиной c несколько раз. То же самое происходит и a c b. Такой граф называется мультиграфом.
Мультиграф
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Источник
Способы представления графов
До сих пор мы задавали ориентированные и неориентированные графы, изображая их с помощью рисунков. Можно задать граф как пару множеств, следуя определению, однако этот способ довольно громоздкий и представляет, скорее, теоретический интерес. Развитие алгоритмических подходов к анализу свойств графов требует иных способов описания графов, более пригодных для практических вычислений, в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представления графов.
Предположим, что все вершины и все ребра неориентированного графа или все вершины и все дуги (включая петли) ориентированного графа пронумерованы начиная с единицы. Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа , где — число вершин, а — число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом:
Для ориентированного графа элементы матрицы задаются так:
Матрицу типа , определенную указанным образом, называют матрицей инциденций.
Пример 5.5. Для ориентированного графа, представленного на рис. 5.8, нумерация вершин уже задана. Зададим нумерацию дуг следующим образом: дуге присвоим номер 1, дуге — 2, дуге — 3 и дуге — 4.
Матрицу инциденции удобно заполнять по столбцам, записывая для k-й дуги 1 в i-й и (–1) в j-й строках k-го столбца и 0 во всех остальных строках k-го столбца. В результате получим матрицу
Несмотря на то, что представление графа в виде матрицы инциденций играет весьма большую роль в теоретических исследованиях, практически этот способ весьма неэффективен. Прежде всего, в матрице в каждом столбце только два ненулевых элемента, что делает этот способ представления графа неэкономным при большом количестве вершин. Кроме того, решение практических задач с помощью матрицы инциденций весьма трудоемко.
Оценим, например, временные затраты на решение с помощью матрицы инциденций такой простой задачи в ориентированном графе: для данной вершины найти ее «окружение» — множество преемников и множество предшественников вершины , т.е. множество всех вершин, непосредственно достижимых из , и множество всех вершин, из которых она непосредственно достижима.
Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером до появления ненулевого элемента (+1 или –1). В случае если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число –1. Номер строки, в которой стоит это число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена –1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина. Для получения всего «окружения» надо проделать указанный поиск для всех ненулевых элементов k-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины . Будем в этом случае говорить, что сложность алгоритма анализа окружения вершины составляет (порядка ).
Можно увидеть, что поиск «окружения» всех вершин займет время порядка произведения числа вершин ориентированного графа на сумму степеней всех вершин, которая, как можно показать, пропорциональна числу дуг ориентированного графа. Таким образом, сложность алгоритма поиска «окружения» составляет , т.е. поиск занимает время порядка произведения числа вершин на число дуг.
Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин , или булева матрица графа. Это квадратная матрица В порядка , элементы которой определяют следующим образом:
для неориентированного графа
для ориентированного графа
Заметим, что в k-й строке матрицы ориентированного графа количество единиц равно полустепени исхода вершины , а количество единиц в k-м столбце — полустепени захода .
Рассмотрим решение задачи поиска «окружения» с использованием матрицы смежности вершин. Для определения «окружения» вершины нужно сначала идти по k-й строке матрицы и искать ненулевые элементы. Если элемент , то вершина достижима из вершины . После просмотра k-й строки надо просмотреть k-й столбец. Если элемент , то вершина достижима из вершины .
Можно показать, что с использованием матрицы смежности вершин решение задачи поиска «окружения» всех вершин ориентированного графа будет иметь сложность порядка , что эффективнее предыдущей оценки , если число дуг ориентированного графа превышает число его вершин, а это часто бывает в практических задачах.
Матрица смежности вершин является достаточно эффективным способом представления графов. Однако эту матрицу удобно строить по графу, уже заданному каким-либо способом, например рисунком. Во многих задачах граф создается динамически, т.е. в ходе решения задачи меняется множество вершин и множество ребер (или дуг). В этом случае эффективным способом машинного представления графа являются списки смежности (или списки инцидентности).
Рассмотрим ориентированный граф. Для задания множества вершин, непосредственно достижимых из вершины v, используют линейный однонаправленный список. Каждый элемент такого списка включает данные (например, некоторое число) и указатель на следующий элемент списка. Список в целом задается указателем на его первый элемент (голову списка). Последний элемент списка содержит «пустой» указатель (рис. 5.11).
Задать для вершины v ее список смежности означает в произвольном порядке поместить в данные элементов списка номера вершин и, для которых в ориентированном графе есть дуга из в . Список смежности вершины обозначают .
Отметим, что список смежности вершины может при необходимости дополняться. Для этого в последнем элементе списка «пустой» указатель заменяется указателем на добавляемый элемент, который становится последним элементом списка с «пустым» указателем.
Если количество вершин ориентированного графа известно заранее, то ориентированный граф удобно задавать в виде структуры, называемой массивом лидеров.
Под массивом мы понимаем матрицу-столбец, элементами которой могут быть некоторые объекты (например, элементы списка смежности). Их называют элементами массива. Число элементов массива лидеров равно числу вершин графа.
Элементами массива лидеров являются первые элементы списков смежности вершин ориентированного графа. Пример представления ориентированного графа списками смежности, собранными в массив лидеров, представлен на рис. 5.12.
С использованием списков смежности совсем просто решается задача поиска преемников данной вершины: для этого достаточно просмотреть список смежности вершины, затратив на это время, пропорциональное ее полустепени исхода. Тогда на решение этой задачи для всего ориентированного графа потребуется время порядка числа его дуг.
Менее эффективно решается задача поиска предшественников вершины, так как в этом случае необходимо, вообще говоря, просмотреть списки смежности всех вершин с целью поиска в них данной вершины.
Таким образом, задача поиска «окружения» с использованием списков смежности является более трудоемкой, чем в случае использования матриц. Однако удобство динамического формирования описания ориентированного графа в данном случае перевешивает. Если задача поиска предшественников возникает часто, можно использовать двусторонние списки смежности, сопоставляя каждой вершине уже два списка — преемников и предшественников.
Описанные способы представления графа списками не исчерпывают всех возможных вариантов, и в литературе по программированию можно найти разнообразные варианты организации списков. Поскольку эти особенности относятся к технологии программирования, мы не будем в них углубляться и в дальнейшем для простоты при описании различных алгоритмов будем считать, что (односторонние) списки смежности собраны в массив лидеров, так как в рассматриваемых ниже алгоритмах анализа графов именно анализ множества преемников вершины наиболее важен.
Неориентированный граф задать с помощью списков смежности можно так же, как и ориентированный. Здесь в список смежности вершины v войдут все вершины, смежные с ней, а списки смежности могут быть собраны в массив лидеров. Для неориентированного графа задача поиска «окружения» одной вершины требует однократного просмотра ее списка смежности, и затраты времени на это пропорциональны степени вершины. На решение задачи поиска «окружения» для всего неориентированного графа потребуется время, пропорциональное произведению числа вершин графа на число его ребер.
В заключение рассмотрим еще одну матрицу, характеризующую граф, — так называемую матрицу достижимости. Это квадратная матрица порядка , каждый элемент которой равен 1, если j-я вершина достижима из i-й вершины, и равен 0 если иначе. Отметим, что, согласно определению достижимости, элементы .
Метод вычисления матрицы достижимости ориентированного графа по его матрице смежности будет рассмотрен в одной из следующих лекций.
Матрица достижимости несет очень важную информацию об ориентированном графе. Её анализ позволяет, например, найти его бикомпоненты и компоненты.
По определению, в бикомпоненту входят взаимно достижимые вершины. Для двух таких вершин с номерами и должно выполняться равенство . Поэтому, чтобы найти бикомпоненту, в которую входит i-я вершина ориентированного графа, нужно просмотреть i-ю строку и i-й столбец матрицы достижимости и сформировать множество номеров вершин, порождающих искомую бикомпоненту. Из определения матрицы достижимости вытекает, что в содержатся номера всех вершин данной бикомпоненты. Поскольку две различные бикомпоненты не пересекаются, вершины с номерами из множества при поиске других бикомпонент из рассмотрения можно исключить. Процесс поиска целесообразно начать с первой вершины. Он закончится, когда для каждой вершины будет найдена содержащая ее бикомпонента. При этом может оказаться, что некоторые (а может быть, и все) бикомпоненты содержат только по одной вершине, поскольку каждая вершина, по определению, достижима сама из себя.
Поиск компонент ориентированного графа сложнее, так как в компоненту входят вершины с номерами и , для которых или . Кроме того, одна и та же вершина может входить в несколько различных компонент. Отметим, что любая бикомпонента или не пересекается с некоторой компонентой, или целиком в нее входит.
Мы не будем приводить общий алгоритм поиска компонент, а рассмотрим его на примере.
Пример 5.6. Для ориентированного графа, изображенного на рис. 5.9, имеем матрицу достижимости
Начнем с поиска бикомпонент. Для первой вершины множество включает только ее саму. Для второй вершины имеем , для четвертой — и для шестой — . Соответственно полученные множества вершин порождают бикомпоненты и изображенные на рис. 5.9.
Перейдем к поиску компонент. Используя матрицу , выпишем для каждой вершины , множество , состоящее из тех вершин, которые достижимы из i-й вершины или из которых достижима она.
В рассматриваемом ориентированном графе для вершины в множество входят вершины, для которых или , т.е. . Для вершин и множества и совпадают с множеством . Поскольку все элементы четвертого и пятого столбцов матрицы равны единице, то для вершин и имеем
Для вершин и получим .
Отметим, что множество построено так, что любая компонента, содержащая вершину , может содержать только вершины из множества .
Кроме того, если некоторая компонента содержит вершины и , то вершина будет принадлежать этой компоненте в том и только в том случае, если .
Действительно, пусть вершина принадлежит компоненте вместе с вершинами и . Тогда либо вершина достижима из вершины , либо, наоборот, достижима из , и, следовательно, . Из аналогичных рассуждений вытекает, что . Таким образом, вершина принадлежит пересечению множеств и .
Пусть теперь вершины и принадлежат компоненте и . Тогда вершина также принадлежит компоненте , поскольку либо вершина достижима из , либо достижима из , и для вершин и ситуация аналогична.
Начнем строить компоненты, содержащие вершину . Рассмотрим множество . Так как вершина принадлежит множеству , найдется по крайней мере одна компонента, в которую входят обе эти вершины. Обозначим ее через . Вершина будет принадлежать этой компоненте в том и только в том случае, если . Непосредственная проверка показывает, что последнее условие выполняется.
Можно заметить, что , поэтому компонента (см. рис. 5.9) есть подграф, порожденный множеством , и вершина не может входить в какую-либо другую компоненту, отличную от . Поскольку в компоненту вошли все вершины из множеств и , то вершины и также не входят ни в какие другие компоненты.
Перейдем к поиску компонент, отличных от , в которые входит вершина . В множестве содержится вершина . Пересечению множеств и принадлежат вершины и , не вошедшие в выделенную компоненту . Рассуждая аналогично и учитывая, что и принадлежат бикомпоненте , а и — бикомпоненте , получаем, что компонента порождается множеством вершин
и других компонент в рассматриваемом ориентированном графе нет.
Источник
