Что такое граф в компьютере
Из чего состоит граф в информатике? Он включает множество объектов, называемых вершинами или узлами, некоторые пары которых связаны т. н. ребрами. Например, граф на рисунке (а) состоит из четырех узлов, обозначенных А, В, С, и D, из которых B соединен с каждой из трех других вершин ребрами, а C и D также соединены. Два узла являются соседними, если они соединены ребром. На рисунке показан типичный способ того, как строить графы по информатике. Круги представляют вершины, а линии, соединяющие каждую их пару, являются ребрами.
Какой граф называется неориентированным в информатике? У него отношения между двумя концами ребра являются симметричными. Ребро просто соединяет их друг с другом. Во многих случаях, однако, необходимо выразить асимметричные отношения – например, то, что A указывает на B, но не наоборот. Этой цели служит определение графа в информатике, по-прежнему состоящего из набора узлов вместе с набором ориентированных ребер. Каждое ориентированное ребро представляет собой связь между вершинами, направление которой имеет значение. Направленные графы изображают так, как показано на рисунке (b), ребра их представлены стрелками. Когда требуется подчеркнуть, что граф ненаправленный, его называют неориентированным.
Алгоритм поиска в ширину
Для небольших графов расстояние между двумя узлами подсчитать легко. Но для сложных появляется необходимость в систематическом методе определения расстояний.
Самым естественным способом это сделать и, следовательно, наиболее эффективным, является следующий (на примере глобальной сети друзей):
- Все друзья объявляются находящимися на расстоянии 1.
- Все друзья друзей (не считая уже отмеченных) объявляются находящимися на расстоянии 2.
- Все их друзья (опять же, не считая помеченных людей) объявляются удаленными на расстояние 3.
Продолжая таким образом, поиск проводят в последующих слоях, каждый из которых - на единицу дальше предыдущего. Каждый новый слой составляется из узлов, которые еще не участвовали в предыдущих, и которые входят в ребро с вершиной предыдущего слоя.
Эта техника называется поиском в ширину, так как она выполняет поиск по графу наружу от начального узла, в первую очередь охватывая ближайшие. В дополнение к предоставлению способа определения расстояния, она может служить полезной концептуальной основой для организации структуры графа, а также того, как построить граф по информатике, располагая вершины на основании их расстояния от фиксированной начальной точки.
Поиск в ширину может быть применен не только к сети друзей, но и к любому графу.
Мир тесен
Если вернуться к глобальной сети друзей, можно увидеть, что аргумент, объясняющий принадлежность к максимальной компоненте, на самом деле утверждает нечто большее: не только у читателя есть маршруты к друзьям, связывающие его со значительной долей населения земного шара, но эти маршруты на удивление коротки.
Эта идея получила название «феномена тесного мира»: мир кажется маленьким, если думать о том, какой короткий маршрут связывает любых двух людей.
Теория «шести рукопожатий» впервые экспериментально исследовалась Стенли Милгрэмом и его коллегами в 1960-е годы. Не имея какого-либо набора данных социальных сетей и с бюджетом в 680 долларов он решил проверить популярную идею. С этой целью он попросил 296 случайно отобранных инициаторов попробовать отослать письмо биржевому брокеру, который жил в пригороде Бостона. Инициаторам были даны некоторые личные данные о цели (включая адрес и профессию), и они должны были переслать письмо лицу, которого они знали по имени, с теми же инструкциями, чтобы оно достигло цели как можно быстрее. Каждое письмо прошло через руки ряда друзей и образовало цепочку, замыкавшуюся на биржевом брокере за пределами Бостона.
Среди 64 цепочек, достигших цели, средняя длина равнялась шести, что подтвердило число, названное два десятилетия ранее в названии пьесы Джона Гэра.
Несмотря на все недочеты этого исследования, эксперимент продемонстрировал один из важнейших аспектов нашего понимания социальных сетей. В последующие годы из него был сделан более широкий вывод: социальные сети, как правило, имеют очень короткие маршруты между произвольными парами людей. И даже если такие опосредованные связи с руководителями предприятий и политическими лидерами не окупаются на ежедневной основе, существование таких коротких маршрутов играет большую роль в скорости распространения информации, болезней и других видов заражения в обществе, а также в возможностях доступа, которые социальная сеть предоставляет людям с совершенно противоположными качествами.
"Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста". Стивен С. Скиена
Модели сетей
Графы в информатике служат математической моделью сетевых структур. На следующем рисунке представлена структура интернета, тогда носившего название ARPANET, в декабре 1970 года, когда она имела лишь 13 точек. Узлы представляют собой вычислительные центры, а ребра соединяют две вершины с прямой связью между ними. Если не обращать внимания на наложенную карту США, остальная часть изображения является 13-узловым графом, подобным предыдущим. При этом действительное расположение вершин несущественно. Важно, какие узлы соединены друг с другом.
Что такое граф?
Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.
Ниже приведён ряд базовых понятий, относящихся к графам. Они проиллюстрированы примерами на рисунке 1.
- Порядок: число вершин в графе.
- Размер: число рёбер в графе.
- Степень вершины: число рёбер, инцидентных вершине.
- Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
- Петля: ребро, вершины которого совпадают.
- Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
- Неориентированный граф: граф с рёбрами, которые не имеют направления.
- Взвешенный граф: рёбра такого графа имеют определённый вес.
- Невзвешенный граф: рёбра такого графа не имеют никаких весов.
Обход или поиск — это одна из фундаментальных операций, выполняемых на графах. Поиск в ширину начинается с определённой вершины, затем исследуются все её соседи на данной глубине и происходит переход к вершинам следующего уровня. В графах, в отличие от деревьев, могут быть циклы — пути, в которых первая и последняя вершины совпадают. Поэтому необходимо отслеживать посещённые алгоритмом вершины. При реализации алгоритма поиска в ширину используется структура данных «очередь».
На рисунке 2 показан пример того, как выглядит поиск в ширину на графе. Жёлтым цветом помечаются обнаруженные вершины, красным — посещённые.
Циклы
Особенно важные виды графов в информатике – это циклы, которые представляют собой кольцевую структуру, такую как последовательность узлов LINC, CASE, CARN, HARV, BBN, MIT, LINC. Маршруты с, по крайней мере, тремя ребрами, у которых первый и последний узел одинаковы, а остальные различны, представляют собой циклические графы в информатике.
Примеры: цикл SRI, STAN, UCLA, SRI является самым коротким, а SRI, STAN, UCLA, RAND, BBN, UTAH, SRI значительно больше.
Фактически каждое ребро графа ARPANET принадлежит к циклу. Это было сделано намеренно: если какое-либо из них выйдет из строя, останется возможность перехода из одного узла в другой. Циклы в системах коммуникации и транспорта присутствуют для обеспечения избыточности – они предусматривают альтернативные маршруты по другому пути цикла. В социальной сети тоже часто заметны циклы. Когда вы обнаружите, например, что близкий школьный друг кузена вашей жены на самом деле работает с вашим братом, то это является циклом, который состоит из вас, вашей жены, ее двоюродного брата, его школьного друга, его сотрудника (т. е. вашего брата) и, наконец, снова вас.
Применяются:
- при планировании выполнения команд;
- при сериализации данных;
- определения порядка выполняемых при компиляции задач в Makefiles;
- для разрешения зависимостей символов в компоновщиках.
При раскраске графов элементам графа присваиваются цвета с учётом определённых условий. Раскраска вершин — наиболее часто используемый метод окраски графов. При этом вершины графа окрашиваются с использованием k цветов, а любым двум соседним вершинам должны соответствовать разные цвета. Другие методы окраски — раскраска рёбер и раскраска граней.
Хроматическое число графа — это наименьшее количество цветов, необходимых для окрашивания графа.
На рисунке 9 показан пример того, как выглядит раскраска вершин графа с использованием 4-х цветов.
Глобальная сеть друзей
Но есть еще кое-что. Например, читатель популярной книги имеет друзей, выросших в других странах, и составляет с ними одну компоненту. Если принять во внимание родителей этих друзей и их друзей, то все эти люди также находятся в той же компоненте, хотя они никогда не слышали о читателе, говорят на другом языке и рядом с ним никогда не были. Таким образом, хотя глобальная сеть дружбы - не связная, читатель будет входить в компонент очень большого размера, проникающий во все части мира, включающий в себя людей из самых разных слоев и, фактически, содержащий значительную часть населения земного шара.
То же имеет место и в сетевых наборах данных – большие, сложные сети часто имеют максимальную компоненту, которая включает значительную часть всех узлов. Более того, когда сеть содержит максимальную компоненту, она почти всегда только одна. Чтобы понять, почему, следует вернуться к примеру с глобальной сетью дружбы и попробовать вообразить наличие двух максимальных компонент, каждая из которых включает миллионы людей. Потребуется наличие единственного ребра от кого-то из первой компоненты ко второй, чтобы две максимальные компоненты слились в одну. Так как ребро единственное, то в большинстве случаев невероятно, чтобы оно не образовалось, и, следовательно, две максимальные компоненты в реальных сетях никогда не наблюдаются.
В некоторых редких случаях, когда две максимальные компоненты сосуществовали в течение длительного время в реальной сети, их объединение было неожиданным, драматическим, и, в конечном итоге, имело катастрофические последствия.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.
В математике, Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).
Неориентированный граф: Соседство (в жизни). Если (1) сосед (3), то (3) сосед (1). См рис. 1.а
Ориентированный граф: Ссылки. Сайт (1) может ссылаться на сайт (3), но совсем не обязательно (хотя возможно) что сайт (3) ссылается сайт (1). См рис. 1.б
Путь в графе это конечная последовательность вершин, в которой каждые две вершины идущие подряд соединены ребром. Путь может быть ориентированным или неориентированным в зависимости от графа. На рис 1.а, путем является например последовательность [(1), (4), (5)] на рис 1.б, [(1), (3), (4), (5)].
У графов есть ещё много разных свойств (например они могут быть связными, двудольными, полными), но я не буду описывать все эти свойства сейчас, а в следующих частях когда эти понятия понадобятся нам.
Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.
Матрица смежности
Этот способ является удобным для представления плотных графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V| 2 ).
В данном представлении мы заполняем матрицу размером |V| x |V| следущим образом:
A[i][j] = 1 (Если существует ребро из i в j)
A[i][j] = 0 (Иначе)
Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)
Понятно что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].
С другой стороны этот способ очень громоздкий, так как требует O (|V| 2 ) памяти для хранения матрицы.
На рис. 2 приведены представления графов из рис. 1 с помощью матриц смежности.
Списки смежности
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v).
На рис. 3 приведены представления графов из рис. 1 с помощью списков смежности.
Те кто дочитал до этого места, наверное задали себе вопрос, а где же собственно я смогу применить графы. Как я и обещал я буду стараться приводить примеры. Самый первый пример который приходит в голову это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)
Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)
Это небольшая часть теории которая понадобится нам чтобы для следующих частей. Надеюсь вам было понятно, а главное понравилось и заинтересовало читать дальнейшие части! Оставляйте свои отзывы и пожелания в комментариях.
BFS — Алгоритм поиска в ширину
Кормен, Лайзерсон, Риверст, Штайн — Алгоритмы. Построение и анализ. Издательство Вильямс, 2007.
Словарь терминов теории графов
Граф — статья в английской Википедии
Статья это кросс-пост из моего блога — "Programing as is — записки программиста"
Возможно, вы уже знакомы с понятием спортивного программирования и знаете, что оно помогает развить навыки решения проблем и прокачать технические знания о структурах данных и алгоритмах.
Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.
Графы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей. Графы состоят из рёбер и вершин. Вершина — это точка на графе, а ребро — это то, что соединяет две точки на графе.
В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.
Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:
- путь — последовательность рёбер, соединяющая разные (неповторяющиеся) вершины;
- маршруты — это те же пути, только они не требуют последовательности разных вершин;
- цикл — группа вершин, связанных вместе в замкнутую цепь. На рисунке выше вершины [1,2,4] составляют цикл;
- связный граф — граф, в котором между любой парой вершин имеется один путь;
- дерево — связный граф, не содержащий цикла;
- неориентированный граф — граф, в котором рёбра не имеют направления. На рисунке выше показан как раз неориентированный граф. В таком неориентированном графе можно перемещаться вдоль ребра в любом из двух направлений;
- ориентированный граф — граф, в котором рёбра имеют направления и обозначаются стрелками. В таком ориентированном графе можно перемещаться вдоль ребра только в указанном направлении.
Для того, чтобы использовать алгоритмы на графах в коде, сначала нам нужно разобраться, как осуществляется представление графов в коде. Весь следующий код будет на C++, так как для спортивного программирования я предпочитаю именно этот язык за его скорость и встроенные функции, позволяющие упростить написание решений задач.
Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.
Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.
Код:
Следующий код используется для создания матрицы смежности неориентированного графа. Чтобы код создавал матрицу смежности для ориентированного графа, измените функцию add_edge , удалив вторую строку внутри неё: matrix[v][u] = 1;
Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).
Код:
Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).
Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.
Поиск в глубину помечает каждую вершину в графе одной из двух меток: посещённая или не посещённая. Алгоритм помечает каждую вершину как посещённую, если удаётся избежать циклов. Он работает следующим образом:
- Помещаем любую из вершин графа на стек.
- Берём элемент со стека и добавляем его в список посещённых.
- Создаём список соседей этой вершины. Добавляем в стек те, что не находятся в списке посещённых.
- Повторяем 2 и 3 пункты, пока стек не опустеет.
Код:
Поиск в ширину — ещё один алгоритм обхода графов. Вместе с алгоритмом поиска вглубь он составит большую часть увлекательных соревнований по программированию, по крайней мере, тех из них, что относятся к графам.
Поиск в ширину тоже помещает каждую вершину в графе в одну из двух категорий: посещённых или непосещённых. И цель у обоих алгоритмов одна и та же: помечать каждую вершину в графе как посещённую, если удаётся избежать циклов. Вот как работает алгоритм поиска в ширину:
- Помещаем любую вершину в графе в конец очереди.
- Берём элемент в начале очереди и добавляем его в список посещённых.
- Создаём список соседей этой вершины. Добавляем в конец очереди непосещённые.
- Повторяем 2 и 3 пункты, пока очередь не опустеет.
Как видите, алгоритм поиска в ширину очень похож на алгоритм поиска в глубину. Однако вместо того, чтобы спускаться вниз по ветви графа или дерева, как это делает алгоритм поиска в глубину, алгоритм поиска в ширину проходит каждый уровень.
Код:
Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.
Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!
Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.
В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.
Начнём с того, что приведём определение графа.
Максимальная компонента
Существует метод качественной оценки компонентов связности. Например, есть всемирная социальная сеть со связями между двумя людьми, если они являются друзьями.
Связная ли она? Вероятно, нет. Связность – довольно хрупкое свойство, и поведение одного узла (или небольшого их набора) может свести ее на нет. Например, один человек без каких-либо живых друзей будет компонентом, состоящим из единственной вершины, и, следовательно, граф не будет связным. Или отдаленный тропический остров, состоящий из людей, которые не имеют никакого контакта с внешним миром, также будет небольшой компонентой сети, что подтверждает ее несвязность.
Маршруты
Хотя графы применяются во многих различных областях, они обладают общими чертами. Теория графов (информатика) включает, возможно, важнейшую из них – идею о том, что вещи часто перемещаются по ребрам, последовательно переходя от узла к узлу, будь то пассажир нескольких авиарейсов или информация, передаваемая от человека к человеку в социальной сети, либо пользователь компьютера, последовательно посещающий ряд веб-страниц, следуя по ссылкам.
Эта идея мотивирует определение маршрута как последовательности вершин, связанных между собой ребрами. Иногда возникает необходимость рассматривать маршрут, содержащий не только узлы, но и последовательность ребер, их соединяющих. Например, последовательность вершин MIT, BBN, RAND, UCLA является маршрутом в графе интернета ARPANET. Прохождение узлов и ребер может быть повторным. Например, SRI, STAN, UCLA, SRI, UTAH, MIT также является маршрутом. Путь, в котором ребра не повторяются, называется цепью. Если же не повторяются узлы, то он носит название простой цепи.
Применяются:
- для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет собой разделение вершин двудольного графа на подмножества;
- в соцсетях для поиска групп сильно связанных между собой людей и выдачи рекомендаций на основе общих интересов.
Топологическая сортировка графа — это такое линейное упорядочение его вершин, в котором для каждого направленного ребра, например (u, v), вершина u предшествует вершине v.
На рисунке 8 показан пример топологического упорядочения вершин, согласно которому вершина 5 должна следовать за вершинами 2 и 3, а вершина 6 — за вершинами 4 и 5.
Алгоритмы нахождения кратчайшего пути:
- Алгоритм Дейкстры.
- Алгоритм Беллмана-Форда.
Применяются:
- для создания деревьев для распределения данных в компьютерных сетях;
- в кластерном анализе с использованием графов;
- при сегментации изображений;
- при социально-географическом районировании, когда смежные регионы объединяются.
Граф считается сильно связным, если все вершины в графе достижимы из всех остальных вершин.
На рисунке 7 показан пример того, как выглядит граф с тремя сильно связными компонентами, вершины которых окрашены в красный, зелёный и жёлтый цвета.
Катастрофа слияния компонент
Например, после прибытия европейских исследователей в цивилизации Западного полушария примерно полтысячелетия назад произошел глобальный катаклизм. С точки зрения сети это выглядело так: пять тысяч лет глобальная социальная сеть, вероятно, состояла из двух гигантских компонент - одной в Северной и Южной Америке, а другой - в Евразии. По этой причине технологии развивалась независимо в двух компонентах, и, что еще хуже, так же развивались и болезни человека и т. д. Когда две компоненты, наконец, вошли в контакт, технологии и заболевания одной быстро и катастрофически переполнили вторую.
Алгоритмы нахождения паросочетаний:
- Алгоритм Хопкрофта-Карпа.
- Венгерский алгоритм.
- Алгоритм сжатия цветков.
Применяются:
Минимальное остовное дерево — это подмножество рёбер графа, которое соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.
На рисунке 6 показан процесс получения минимального остовного дерева.
Алгоритмы поиска минимального остовного дерева:
Применяются для:
- составления расписаний;
- назначения радиочастот мобильных сетей;
- моделирования и решения головоломок типа судоку;
- проверки того, является ли граф двудольным;
- раскрашивания географических карт стран или штатов, на которых соседние страны или штаты имеют разные цвета.
Можно смоделировать граф в виде сети потоков с весами рёбер в качестве пропускной способности этих потоков. В задаче максимального потока требуется найти такой путь потока, который может обеспечить максимально интенсивность потока.
На рисунке 10 показан пример того, как выглядит нахождение максимального потока сети и определение конечного значения потока.
Алгоритмы нахождения максимального потока:
- Алгоритм Форда-Фулкерсона.
- Алгоритм Эдмондса-Карпа.
- Алгоритм Диница.
Алгоритмы с раскраской графов:
- Алгоритмы, использующие поиск в ширину или поиск в глубину.
- Жадная раскраска.
Применяется для:
- определения кратчайших путей и минимальных остовных деревьев;
- индексации веб-страниц поисковыми ботами;
- поиска в соцсетях;
- нахождения доступных соседних узлов в одноуровневых сетях, таких как BitTorrent.
Поиск в глубину начинается с определённой вершины, затем уходит как можно дальше вдоль каждой ветви и возвращается обратно. Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того, чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в глубину используется структура данных «стек».
На рисунке 3 показан пример того, как выглядит поиск в глубину на том же графе, который использован на рисунке 2. Граф обходится на всю глубину каждой ветви с возвращением обратно.
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Граф - это совокупность пары множеств. Конечного есть и бесконечные, однако мы их пока не рассматриваем непустого множества V и множества E заданного неупорядоченными парами множества V.
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = . Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степенью вершины - является количество рёбер исходящих выходящих из вершины и входящих в нее. Данное определение верно для ориентированных графов см. классификацию графов. Для неориентированных графов исходящая степень равна входящей. Степенью вершины 1 будет является число 4. Так как вершина 1 соединена с вершиной 2, 3, 4, 5.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Самое главное в графе это вершины и проведенные между ними рёбра. В связи с этим граф является топологическим объектом, а не геометрическим . То есть объектом который не меняется при любых растяжениях и сжатиях. Нам все равно какой мы сделали отрезок. Кривой, прямой, самое главное это наличие связи между вершинами. По этой причине графы являются очень универсальными в плане практического применения. Мы можем обозначать ими дороги, компьютерную сеть, людей которые дружат друг с другом или даже влюблены друг в друга.
Расстояние и поиск в ширину
В дополнение к сведениям о том, связаны ли два узла маршрутом, теория графов в информатике позволяет узнать и о его длине – в транспорте, связи или при распространении новостей и заболеваний, а также о том, проходит ли он через несколько вершин или множество.
Для этого следует определить длину маршрута, равную числу шагов, которые он содержит от начала до конца, т. е. число ребер в последовательности, которая его составляет. Например, маршрут MIT, BBN, RAND, UCLA имеет длину 3, а MIT, UTAH – 1. Используя длину пути, можно говорить о том, расположены ли два узла в графе близко друг к другу или далеко: расстояние между двумя вершинами определяется как длина самого короткого пути между ними. Например, расстояние между LINC и SRI равно 3, хотя, чтобы убедиться в этом, следует удостовериться в отсутствии длины, равной 1 или 2, между ними.
Алгоритмы поиска топологической сортировки:
- Алгоритм Кана.
- Алгоритм на основе поиска в глубину.
Применяются:
- в подборе пары для жениха или невесты (задача о стабильных браках);
- для определения вершинного покрытия;
- в теории транспорта для решения задачи распределения ресурсов и оптимизации перевозок.
Надеюсь, статья была полезной и в простой и краткой форме познакомила вас с графовыми алгоритмами. 😇
А с реализациями графовых алгоритмов можно ознакомиться в модулях на Python networkx и igraph.
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Вторым признаком является отсутствие или наличие кратных ребер.
Кратные ребра - это ребра которые встречаются между двумя вершинами сразу несколько раз. В примере ниже мы видим, что вершина a соединена с вершиной c несколько раз. То же самое происходит и a c b. Такой граф называется мультиграфом.
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Алгоритмы обнаружения цикла:
Компоненты
Если графы в информатике не связаны, то они естественным образом распадаются на набор связанных фрагментов, групп узлов, которые являются изолированными и не пересекающимися. Например, на рисунке изображены три таких части: первая – А и В, вторая – C, D и Е, и третья состоит из оставшихся вершин.
Компоненты связности графа представляют собой подмножество узлов, у которых:
- каждая вершина подгруппы имеет маршрут к любой другой;
- подмножество не является частью некоторого большего набора, в котором каждый узел имеет маршрут к любому другому.
Когда графы в информатике разделяются на их компоненты, то это является лишь начальным способом описания их структуры. В рамках данного компонента может быть богатая внутренняя структура, важная для интерпретации сети. Например, формальным методом определения важности узла является определение того, на сколько частей разделится граф, если узел будет убран.
Применяются в:
- картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения;
- сетях для решения проблемы минимальной задержки пути;
- абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.
Цикл — это путь, в котором первая и последняя вершины графа совпадают. То есть путь, начинающийся и завершающийся в одной и той же вершине, называется циклом. Обнаружение циклов — это процесс выявления таких циклов. На рисунке 5 показано, как происходит обнаружение цикла.
Применяются:
- в авиакомпаниях для составления полётного расписания экипажей;
- при сегментации изображений для определения фона и переднего плана изображения.
Паросочетание на графе — это набор рёбер, которые не имеют общих вершин (т.е. хотя бы двух рёбер, не имеющих общей вершины). Паросочетание называется максимальным, если оно содержит максимально возможное число рёбер, сочетающихся с как можно большим количеством вершин.
На рисунке 11 показано получение полного паросочетания в двудольном графе с двумя наборами вершин, обозначенных оранжевым и синим цветами.
Американская средняя школа
Применяется:
- для нахождения пути между двумя вершинами;
- для обнаружения циклов на графе;
- в топологической сортировке;
- в головоломках с единственным решением (например, лабиринтах).
Кратчайший путь от одной вершины графа к другой — это путь, при котором сумма весов рёбер, его составляющих, должна быть минимальна.
На рисунке 4 показан кратчайший путь на графе от вершины 1 до вершины 6.
Связный граф: определение (информатика)
Естественно задаться вопросом, можно ли из каждого узла попасть в любой другой узел. Граф связный, если между каждой парой вершин существует маршрут. Например, сеть ARPANET – связный граф. То же можно сказать и о большинстве коммуникационных и транспортных сетей, так как их цель состоит в том, чтобы направлять трафик от одного узла к другому.
С другой стороны, нет никаких априорных оснований ожидать того, что данные виды графов в информатике широко распространены. Например, в социальной сети несложно представить двух людей, не связанных между собой.
Алгоритмы поиска сильных компонент связности:
- Алгоритм Косараджу.
- Алгоритм Тарьяна.
Читайте также: