Что такое кратные ребра в графе

Краткий перечень основных понятий теории графов.

Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы не будут вводиться в рассмотрение) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы (задача коммивояжера). Например, графом, изображенным на рис. 1, в котором точки − вершины графа − города, линии, соединяющие вершины − ребра − дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города- пункта в другой).

Графом G называется совокупность двух множеств: вершин V и ребер Х, между элементами которых определено отношение инцидентности – каждое ребро хХ инцидентно двум вершинам  и V, которые оно соединяет. При этом вершина () и ребро x называются инцидентными друг другу, а вершины и , являющиеся для ребра x концевыми точками, называются смежными.

Граф, содержащий направленные ребра с началом  и концом , называется ориентированным графом (орграфом), а ненаправленные – неориентированным ( н-графом). Ребра ориентированного графа называются дугами.

Одинаковые пары ребер — параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Например, кратность ребра <v1, v2> в графе, изображенном на рис. 4, равна двум, кратность ребра <v3, v4> − трем.

Ребро, концевые вершины которого совпадают, называется петлей.

Граф называется конечным, если множество его элементов (дуг и рёбер) конечно, и пустым, если его множество вершин (а, следовательно, и рёбер) пусто.

Граф без петель и кратных рёбер называется полным графом, если каждая пара вершин соединена ребром.

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

Степенью (или валентностью) вершины V н-графа называется количество рёбер (), инцидентных вершине .

Вершина графа, имеющая степень 0, называется изолированной, а степень 1 – висячей.

Полустепенью захода (исхода) вершины v ориентированного графа D называется число +(v) ((v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в +(v), так и в (v). Рассмотрим рис. 5: +(v2)=3; (v2)=2.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Графы G1и G2 равны, если их множества вершин и ребер совпадают

Итак, используемые далее обозначения:

V – множество вершин;

Х, Е – множество ребер или дуг;

v (или vi)– вершина или номер вершины;

G, G0 — неориентированный граф;

D, D0 – ориентированный;

<v,w> − ребра неориентированного графа;

(v,w) − дуги в ориентированном графе;

v,w — вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) — количество ребер, m(D) — количество дуг.

Кратные рёбра

• Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.

В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):

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

Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра.Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов. Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей.

Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность.

Связанные понятия

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

Перечислены связные 3-регулярные (кубические) простые графы с малым числом вершин.

В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.

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

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

В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.

В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества.

В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).

В теории графов графом Халина называется некоторый вид планарного графа, который строится из дерева, имеющего по меньшей мере 4 вершины, ни одна из которых не имеет в точности двух соседей. Дерево рисуется на плоскости так, что никакие рёбра не пересекаются, затем добавляются рёбра, соединяющие все его листья в цикл. Графы Халина названы по имени немецкого математика Рудольфа Халина, изучавшего их в 1971 году, но кубические графы Халина изучались за столетие до этого английским математиком Томасом.

Кратные рёбра

Кратные рёбра, соединяющие две вершины.

Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.

В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):

• Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1] .
• Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра [2] .

Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов [3] . Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей [en] .

Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность [4] .

Диполь [en] — это граф с двумя вершинами, в котором все рёбра параллельны.

Графы — основные определения

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

Неформально это можно понимать как набор вершин (точек) и соединяющих их отрезков (рёбер).

Определение:
Смежные вершины —это вершины, соединенны ребром

Определение:
Степень вершины $d(v)$ —это количество ребер, исходящих из вершины $v$

Определение:
Инцидентность —это для ребра $(a,b)$ вершины $a$ и $b$ называются инцидентными. И наоборот, для вершины $a$ любое ребро $(a, x)$ (или $(x, a)$) называется инцидентным данной вершине $a$.

Замечание: две вершины, соединенные ребром, называются именно смежными, инцидентными их назвать нельзя.

Например, в графе на рисунке степень вершины $2$ равна $4$, вершины $4$ и $5$ смежны. Всего в графе $7$ вершин и $9$ ребер, то есть $|V| = 7$ и $|E| = 9$.

Определение:
Кратные ребра —это ребра, которые соединяют одну и ту же пару вершин. Если две вершины соединены более чем одним ребром, говорят, что граф содержит кратные ребра.

Определение:
Петля —это ребро, которое соединяет вершину саму с собой

Определение:
Простой граф —это граф, который не содержит петель и кратных ребер.

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

Определение:
Взвешенный граф —это граф, каждому ребру которого присвоено некоторое вещественное число, называемое весом ребра. Иными словами, на множестве ребер задана функция $W : E \rightarrow \mathbb$.

Определение:
Ориентированный граф —это граф, в котором каждое ребро имеет направление, то есть ребро уже не просто соединяет две вершины, а в этой паре выбрано начало и конец ребра.

На рисунке изображен неориентированный граф. Его легко сделать ориентированным, если задать направление для каждого ребра. В некоторых задачах бывает удобно рассматривать неориентированный граф как ориентированный, но в котором у каждого ориентированного ребра $(u, v)$ (ведет из $u$ в $v$) есть парное ребро $(v, u)$. Получаем, что по ребру можно перемещаться в обе стороны, то есть граф неориентированный.

Определение:
Связный граф —это граф, в котором из любой вершины можно по ребрам дойти до любой другой. Относится только к неориентированным графам.