Как называется набор вершин соединенных ребрами

Основные понятия теории графов

Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \<(u , v)\ | u, v \in V\>$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$. Ребро $(u, v)$ соединяет вершины $u$ и $v$.

Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ — количество вершин, а $M$ — ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.

Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Дерево — это связный неориентированный граф без циклов.

1) У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.

Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины — ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) — ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.

2) У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.

Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.

3) У дерева с $N$ вершинами всегда ровно $N-1$ ребро.

Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока $N > 1$. В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.

4) Между любыми двумя вершинами в дереве есть ровно один простой путь.

Действительно, если их два, то в графе есть цикл. Быть ноль их не может — ведь граф связный.

5) Дерево — это минимальный по числу рёбер связный граф на $N$ вершинах.

Действительно, если есть связный граф, в котором меньше, чем $N-1$ ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве $N-1$ ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.

Терминология и представления 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 такой, что его элемент:

A_ij = 1 , когда есть ребро из вершины i к вершине j , а также
A_ij = 0 , когда нет края.

Каждая строка в матрице представляет исходные вершины, а каждый столбец представляет вершины назначения. Все диагональные элементы матрицы равны нулю, поскольку ребра ведут из вершины в саму себя, т. е. в простых graphs не допускаются петли. Если граф неориентированный, матрица смежности будет симметричной. Кроме того, для взвешенного графа A_ij может представлять веса ребер.

Матрица смежности сохраняет значение (1/0/edge-weight) для каждой пары вершин, независимо от того, существует ребро или нет, поэтому требуется n 2 пространство. Их можно эффективно использовать только тогда, когда graph плотный.

2. Представление списка смежности:

Представление Graph списком смежности связывает каждую вершину Graph с набором соседних вершин или ребер, т. е. каждая вершина хранит список смежных вершин. Существует множество вариантов представления списка смежности в зависимости от реализации. Эта структура данных позволяет хранить дополнительные данные о вершинах, но практически очень эффективна, когда граф содержит только несколько ребер. т.е. граф разреженный.

Граф в математике

Граф (в математике), множество V V V вершин и набор E E E неупорядоченных и упорядоченных пар вершин; обозначается граф через G ( V , E ) G(V,E) G ( V , E ) . Неупорядоченная пара вершин называется ребром, упорядоченная пара – дугой. Граф, содержащий только рёбра, называется неориентированным; граф, содержащий только дуги, – ориентированным . Пара вершин может соединяться двумя или более рёбрами (дугами одного направления), такие рёбра (дуги) называются кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) называется петлёй. (Иногда под графом понимают граф без петель и кратных рёбер; тогда граф, в котором допускаются кратные рёбра, называется мультиграфом, а граф, в котором допускаются кратные рёбра и петли, называется псевдографом.)

Вершины, соединенные ребром или дугой, называются смежными. Рёбра, имеющие общую вершину, также называют смежными. Ребро (дуга) и любая из его двух вершин называются инцидентными. Говорят, что ребро ( u , v ) (u, v) ( u , v ) соединяет вершины u u u и v v v , а дуга ( u , v ) (u, v) ( u , v ) начинается в вершине u u u и кончается в вершине v v v .

Каждый граф можно представить в евклидовом пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими рёбрам (или дугам) графа. В трёхмерном пространстве любой граф можно представить таким образом, что линии, соответствующие рёбрам (дугам), не пересекаются во внутренних точках.

С помощью различных операций можно строить граф из более простых, переходить от одного графа к более простому, разбивать граф на более простые, в заданном классе графов переходить от одного графа к другому и т. д. Наиболее употребительными одноместными операциями являются: удаление ребра (вершины ребра сохраняются), добавление ребра между двумя вершинами графа, удаление вершины вместе с инцидентными ей рёбрами (граф, полученный в результате удаления вершины v v v из графа G G G , часто обозначают G − v G-v G − v ), добавление вершины (которую можно соединить рёбрами с некоторыми вершинами графа), стягивание ребра – отождествление пары смежных вершин, т. е. удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами графа, которые были смежны хотя бы с одной из удаленных вершин; подразбиение ребра – удаление ребра и добавление новой вершины, которая соединяется ребром с каждой вершиной удаленного ребра.

Употребляются и другие многоместные операции над графами.

Рис. 1. Операция в классе графов с одинаковым набором степеней. Рис. 1. Операция в классе графов с одинаковым набором степеней. Для некоторых классов графов удаётся найти простые операции, позволяющие с помощью многократного их применения перейти от любого графа изучаемого класса к любому другому графу этого класса. На рис. 1 приведена операция, с помощью которой в классе графов с одинаковым набором степеней можно перейти от одного произвольного графа к любому другому; на рис. 2 показана операция, позволяющая в классе плоских триангуляций (см. Плоский граф ) с одинаковым числом вершин перейти от произвольной триангуляции к любой другой. Для описания и изучения некоторых классов графов отыскиваются такие операции и множества графов, из которых с помощью данных операций можно получить любой граф заданного класса. Операции над графами используются также для построения графов с заданными свойствами, при вычислении числовых характеристик графов и т. д.

Рис. 2. Операция в классе плоских триангуляций с одинаковым числом вершин. Рис. 2. Операция в классе плоских триангуляций с одинаковым числом вершин. Понятие «граф» используется в определении таких математических понятий, как управляющая система, в некоторых определениях алгоритма, грамматики и других. Изложение ряда математических теорий становится более наглядным при использовании геометрического представления графа, например теории марковских цепей . Понятие «граф» широко используется при создании и описании различных математических моделей в экономике, биологии и т. д.

Козырев Виктор Петрович . Первая публикация: Математическая энциклопедия под ред. И. М. Виноградова, 1977.

Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

История возникновения теории графов

Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером .

Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).

Деревья и сети

Дерево — граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.