Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах
Ребро u , соединяющее вершину a с вершиной b ( a ≠ b ), назовём звеном, если множеству P принадлежать две инциденции: a, u, b и b, u, a .
Пример 1. Найти звенья в графе, представленном на рис А (под примером).
Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.
Иначе говорят также, что в описанном случае порядок двух концов ребра графа не существенен. В случае, когда порядок, в котором указаны вершины в инциденции, существенен, соответствующее ребро называет дугой.
Пример 2. Найти дуги в графе, представленном на рис А.
Ответ. Дуги данного графа представлены направленными линиями (стрелками), соединяющими первую из инцидентных вершин со второй. Вершины 1, 2, 9, 10 — дуги; первая из них соединяет вершину b с вершиной a , но не наоборот. То же самое относится и к другим дугам.
О дуге говорят, что она идёт из вершины b в вершину a .
Рёбра u , для которых имеются инциденции вида (a, u, a) , то есть вершина соединена сама с собой, называются петлями.
Пример 3. Найти петли в графе, представленном на всё том же рис А.
Ответ. В данном графе петли представлены линиями, начинающимися и заканчивающимися на одной и той же вершине. Линии 4 и 5 — петли.
Голой называют вершину, которая не инцидентна ни одному ребру графа.
Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.
Ответ. В данном графе голой является вершина f .
Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.
Две вершины a и b называются смежными, если существует по крайней мере одно соединяющее их ребро. В частности, вершина смежна сама с собой в том и только в том случае, когда при ней имеется хотя бы одна петля.
Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.
Ответ. В данном графе вершина c изолированная. Вершины a и b смежные, а вершины a и d — не смежные, вершина b смежна сама с собой.
Кратными называются рёбра, соединяющие одну и ту же пару вершин.
Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.
Ответ. В данном графе рёбра 1, 2 и 3 — кратные; кратными являются также 4 и 5, рёбра 8, 9, рёбра 6, 7, а также 10 и 11.
Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.
Маршруты, цепи и циклы в графах
Маршрутом в графе называется последовательность вершин и рёбер (v 0 , e 1 , . e n , v n ) , такая, что любые две соседние вершины v i и v i+1 соединены ребром e i+1 . Если в маршруте v 0 = v n , то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута
Маршрут, в котором все рёбра различны, называется цепью.
Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.
Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.
Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).
Ответ. В данном графе:
- например, a1b2a1b7d8c9c8d — маршрут из вершины a в вершину d длины 7;
- например, b5c6b7d — цепь;
- например, цепь a1b5c8d — простая, а цепь e3e4e — не простая;
- например, b5c9c8d7b — цикл длины 4 при вершине b;
- например, b5c8d7b — простой цикл длины 1 при вершине b.
Граф называется связным, если существует цепь между любыми двумя его вершинами.
Основные определения теории графов
В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).
Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).
Если имеется ребро [math] (v, u) \in E [/math] , то говорят:
- [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
- [math] u [/math] и [math] v [/math] — смежные.
- Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
- Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .
Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,
v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.
| Определение: |
| Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname |
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).
Теория Графов. Часть 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. Такой граф называется мультиграфом.
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Терминология и представления graphs
В этом посте обсуждаются основные определения в терминологии, связанной с Graphми, и рассматриваются представления списка смежности и матрицы смежности структуры данных Graph.
Что такое Graph?
graph представляет собой упорядоченную пару G = (V, E) состоящий из набора V вершин или узлов и набор пар вершин из V , известные как ребра графа. Например, для Graphа ниже.
Типы Graphов
1. Неориентированный graph
Неориентированный graph (граф) — это graph, в котором ребра не имеют ориентации. Край (x, y) идентичен краю (y, x) , т. е. они не являются упорядоченными парами. Максимальное количество ребер, возможное в неориентированном Graph без петли, равно n×(n-1)/2 .
2. Ориентированный graph
Ориентированный graph (орграф) — это graph, в котором ребра имеют ориентации, т. е. ребро (x, y) не идентичен ребру (y, x) .
3. Направленный ациклический graph (DAG)
Направленный ациклический graph (DAG) — это ориентированный graph, не содержащий циклов.
4. Мультиграф
Мультиграф — это неориентированный graph, в котором допускается несколько ребер (а иногда и петель). Множественные ребра — это два или более ребра, соединяющие одни и те же две вершины. Петля — это ребро (направленное или ненаправленное), соединяющее вершину с самой собой; это может быть разрешено или нет.
5. Простой Graph
Простой граф — это неориентированный граф, в котором не допускаются множественные ребра и петли, в отличие от мультиграфа. На простом Graphе с n вершин, степень каждой вершины не более n-1 .
6. Взвешенный и невзвешенный Graph
Взвешенный граф связывает значение (вес) с каждым ребром в Graph. Мы также можем использовать слова стоимость или длина вместо веса.
Невзвешенный граф не имеет никакого значения (веса), связанного с каждым ребром в Graph. Другими словами, невзвешенный граф — это взвешенный граф со всеми весами ребер, равными 1. Если не указано иное, все графы по умолчанию считаются невзвешенными.
7. Полный Graph
Полный graph — это graph, в котором каждые две вершины смежны: присутствуют все ребра, которые могут существовать.
8. Связный graph
Связный graph имеет путь между каждой парой вершин. Другими словами, недостижимых вершин нет. Несвязный graph — это несвязный graph.
Наиболее часто используемые термины в graphиках
- Ан edge является (вместе с вершинами) одной из двух основных единиц, из которых строятся graphы. Каждое ребро имеет две вершины, к которым оно присоединено, называемые его endpoints .
- Две вершины называются adjacent если они являются концами одного ребра.
- Outgoing edges вершины являются направленными ребрами, исходными точками которых является вершина.
- Incoming edges вершины — это направленные ребра, к которым вершина относится.
- The degree вершины Graph — это общее количество инцидентных ей ребер.
- В ориентированном Graph out-degree вершины — общее количество исходящих ребер, а in-degree — общее количество входящих ребер.
- Вершина с нулевой степенью вхождения называется исходной вершиной, а вершина с нулевой степенью исхода называется вершиной-приемником.
- Изолированная вершина — это вершина с нулевой степенью, которая не является конечной точкой ребра.
- Path представляет собой последовательность чередующихся вершин и ребер, такую, что ребро соединяет каждую последующую вершину.
- Cycle это путь, который начинается и заканчивается в одной вершине.
- Simple path путь с различными вершинами.
- Graph Strongly Connected если он содержит направленный путь из u к v и направленный путь от v к u для каждой пары вершин u , v .
- Ориентированный graph называется Weakly Connected если замена всех его ориентированных ребер неориентированными ребрами дает связный (неориентированный) граф. Вершины в слабосвязном Graph имеют исходящую или входящую степень не менее 1.
- Connected component максимальный связный подграф несвязного Graph.
- А bridge — ребро, удаление которого разъединило бы graph.
- Forest graph без циклов.
- Tree является связным graphом без циклов. Если мы удалим все циклы из DAG (направленный ациклический graph), он станет деревом, а если мы удалим любое ребро в дереве, оно станет лесом.
- Spanning tree неориентированного Graph — это подграф, то есть дерево, включающее все вершины Graph.
Связь между количеством ребер и вершин
Для простого Graph с m края и n вершин, если graph
- направленный, то m = n×(n-1)
- ненаправленный, то m = n×(n-1)/2
- подключен, то m = n-1
- дерево, то m = n-1
- лес, то m = n-1
- завершить, то m = n×(n-1)/2
Следовательно, O(m) может варьироваться между O(1) а также O(n 2 ) , в зависимости от того, насколько плотен graph.
Graph представление
1. Матричное представление смежности:
Матрица смежности — это квадратная матрица, используемая для представления конечного Graph. Элементы матрицы указывают, являются ли пары вершин смежными или нет в Graph.
Для простого невзвешенного Graph с множеством вершин V , матрица смежности представляет собой квадрат |V| × |V| матрица A такой, что его элемент:
Aij = 1 , когда есть ребро из вершины i к вершине j , а также
Aij = 0 , когда нет края.
Каждая строка в матрице представляет исходные вершины, а каждый столбец представляет вершины назначения. Все диагональные элементы матрицы равны нулю, поскольку ребра ведут из вершины в саму себя, т. е. в простых graphs не допускаются петли. Если граф неориентированный, матрица смежности будет симметричной. Кроме того, для взвешенного графа Aij может представлять веса ребер.
Матрица смежности сохраняет значение (1/0/edge-weight) для каждой пары вершин, независимо от того, существует ребро или нет, поэтому требуется n 2 пространство. Их можно эффективно использовать только тогда, когда graph плотный.
2. Представление списка смежности:
Представление Graph списком смежности связывает каждую вершину Graph с набором соседних вершин или ребер, т. е. каждая вершина хранит список смежных вершин. Существует множество вариантов представления списка смежности в зависимости от реализации. Эта структура данных позволяет хранить дополнительные данные о вершинах, но практически очень эффективна, когда граф содержит только несколько ребер. т.е. граф разреженный.