Что такое кратное ребро в графе
Перейти к содержимому

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

  • автор:

Обходы графов

Определение. Графом называется пара множеств $G = (V, E)$, где множество $V$ называется множеством вершин графа, а множество $E$, состоящее из пар вершин $(u, v)$, называется множеством ребер графа.

Если существует ребро $(u, v)$, то говорят что оно соединяет вершины $u$ и $v$. Две вершины, соединенные ребром, называют смежными. Для вершины $v$ любое ребро $(v, u)$ называется инцидентным ей. Число ребер, инцидентных вершине $v$, называют степенью вершины $v$.

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

Граф называют ориентированным, если для каждого ребра задано направление, и неориентированным в противном случае. Для ребра $(u, v)$ обратным ребром называется ребро $(v, u)$. Неориентированные графы часто рассматривают как ориентированные, добавив вместо каждого ребра два для каждого направления.

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

Циклом называется путь, начинающийся и заканчивающийся в одной и той же вершине. Если помимо первой и последней вершины все остальные вершины на этой пути уникальны, то такой цикл называется простым. Граф называют ацикличным, если в нем нет простых циклов.

Ацикличный неориентированный граф называется лесом. Связный лес называется деревом. У деревьев есть другие эквивалентные определения:

  • Граф является деревом, если в нем $n$ вершин и $(n-1)$ ребер и нет циклов.
  • Граф является деревом, если из любой вершины можно дойти в любую другую единственным образом.

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

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

Англо-русский графовый словарь

  • граф — graph
  • вершина — vertex
  • вершины — vertices
  • ребро — edge
  • смежный — adjacent
  • степень — degree
  • петля — self-loop
  • ориентированный граф — directed graph
  • неориентированный граф — undirected graph
  • цикл — cycle
  • ацикличный граф — acyclic graph
  • дерево — tree
  • планарный граф — planar graph
  • двудольный граф — bipartite graph

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.

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

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

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

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса (иногда называемого оптимальным ветвлением).

Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».

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

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

В топологической теории графов 1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.

Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.

Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа (по модулю 2) имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам.

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

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

Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.

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

Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами, рёбрами, вершинами, или рёбрам, и вершинам графа.

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

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

Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение.

Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.

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

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

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

Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).

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

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

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

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

Рисование под прямыми углами (РПУ=right angle crossing, RAC) графа — это рисование, при котором вершины представлены точками, а рёбра представлены отрезками или ломаными, не более двух рёбер пересекаются в одной точке, и если два ребра пересекаются, они должны пересекаться под прямыми углами.

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

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

Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. (По теореме Визинга хроматический индекс кубического графа равен 3 или 4.) Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.

Гипотеза Тэйта утверждает, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины. Гипотезу высказал в 1884 году П.Г. Тэйт и опровёрг в 1946 году У.Т. Татт, построив контрпример с 25 гранями, 69 рёбрами и 46 вершинами. Позднее, в 1988, Холтон и Маккей нашли меньший по размеру контрпример с 21 гранями, 57 рёбрами и 38 вершинами и показали, что этот граф минимален.

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

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

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

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

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

Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.

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

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

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

Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм.

Дистанционно-регулярный граф — регулярный граф такой, что для любых двух вершин v и w число вершин с расстоянием j от v и расстоянием k от w зависят только от j, k и i = d(v, w).

1.6. Матрицы достижимости и связности

Пусть A ( D ) – матрица смежности ориентированного псевдографа D =( V , X ) (или псевдографа G =( V , X )), где V = < v 1 ,…, v n >. Обозначим через A k =[ a ( k ) ij ] k -ю степень матрицы смежности A ( D ).

Элемент a ( k ) ij матрицы A k ориентированного псевдографа D =( V , X ) (псевдографа G =( V , X )) равен числу всех путей (маршрутов) длины k из vi в vj .

Матрица достижимости ориентированного графа D − квадратная матрица T ( D )=[ tij ] порядка n , элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S ( D )=[ sij ] порядка n , элементы которой равны

Матрица связности графа G − квадратная матрица S ( G )=[ sij ] порядка n , элементы которой равны

Утверждение 3. Пусть D =( V , X ) – ориентированный граф, V = < v 1 ,…, v n >, A( D ) – его матрица смежности. Тогда

1) T ( D)=sign[E+A+A 2 +A 3 +… A n-1 ],

2) S ( D )= T ( D ) & T T ( D ) ( T T -транспонированная матрица, & — поэлементное умножение).

Пусть G =( V , X ) – граф, V = < v 1 ,…, v n >, A(G) – его матрица смежности. Тогда

S (G)=sign[ E+A+ A 2 +A 3 +… A n-1 ] (E— единичная матрица порядка n ).

1.7. Расстояния в графе

Пусть — граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.

Расстояние в графе удовлетворяют аксиомам метрики

2) (в неориентированном графе)

4) в связном неориентированном графе.

Пусть связный граф (или псевдограф).

Диаметром графа G называется величина .

Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .

Радиусом графа G называется величина

Центром графа G называется любая вершина такая, что .

1.8. Образ и прообраз вершины и множества вершин

Пусть ориентированный граф — некоторая вершина .

Обозначим — образ вершины ;

— образ множества вершин V 1 ;

— прообраз множества вершин V 1 .

1.9. Нагруженные графы

Нагруженный граф − ориентированный граф D =( V , X ), на множестве дуг которого определена некоторая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

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

Путь в нагруженном ориентированном графе из вершины v в вершину w , где v ¹ w , называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный путь в нагруженном графе.

Введем матрицу длин дуг C ( D )=[ cij ] порядка n , причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для » дуги , то » минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для » i , j : путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w , содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).

1.10. Деревья и циклы

Граф G называется деревом если он является связным и не имеет циклов.

Граф G называется лесом если все его компоненты связности — деревья.

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

3) » две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

4) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Утверждение 4. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Утверждение 5. Пусть G связный граф, а − висячая вершина в G , граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n ( G )-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число называется цикломатическим числом графа G .

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

В графе ребро, концы которого совпадают, то есть [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, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] .

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *