Неориентированный граф

Ориентированные и неориентированные графы.

Граф, в котором направление линий не выделя­ется (все линии являются ребрами), называется неориентирован­ным ;

Граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным .

Из ориентированного графа сделать неориентированный граф – убрать стрелки

12. Способы задания графов: аналитический, геометрический, матричный. Матрицы смежности и инцидентности графа. Маршруты, циклы и цепи графа.

1. Геометрический способ задания графа – ну, просто нарисовать его таким, какой он есть.

2. Матрицей смежности – берем две вершины. Если между ними есть дуга или ребро – то пишем 1. нет – 0 .

3. Матрица инцидентности – берем вершину. Если из нее выходит дуга — пишем 1, входит — -1. нет – 0.

Матрицу инцидентности можно построить для ориентированных и неориентированных графов.

Вершина, соединенная с ребром – инцидентна .

Две вершины соединенные ребром – смежные .

Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1, v2 — вершины, а e = (v1, v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности .

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v0. e1. v1. e2. v2. …, ek. vk. в которой любые два соседних элемента инцидентны. Если v0 = vk. то маршрут замкнут. иначе открыт .

Маршрут, в котором ребра не повторяются – цепь (путь). Длина пути для ориентированного графа – количество дуг (ребер).

Цепи, у которых начала и концы совпадают – циклы.

Связный граф – из любой вершины есть маршрут в другую (матрица связности для такого графа состоит из единиц только)

матрица связности – в ней 0 и 1

1 – из одной вершины есть маршрут в другую

0 – нет маршрута.

Граф Эйлера – в котором существует цикл.

Эйлеров граф – в нем есть маршрут, проходящий через все дуги по одному разу.

Цикл — это путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

vikidalka.ru — 2015-2017 год. Все права принадлежат их авторам!

Неориентированные графы

Как было уже сказано выше, иногда графы рассматривают без учета ориентации дуг. В этом случае такие графы называют неориентированными графами. Для неориентированного графа понятие «дуга», «путь», «контур» заменяются соответственно понятиями «ребро», «цепь», «цикл». Ребро – отрезок, соединяющий две вершины. Цепь – последовательность ребер. Цикл – цепь, у которой начальная и конечная вершины совпадают.

Описать неориентированный граф G можно и путем задания пары множеств (X, U), где Х – множество вершин; U-множество ребер. Однако более удобным является описание неориентированного графа матрицей смежности или матрицей инциденций, которые строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между заходящей и исходящей из нее дугами. При этом вершины х и y называются смежными, если существует ребро их соединяющее, а само это ребро называется инцидентным вершинам х и у.

Пример. Построить матрицу смежности и матрицу инциденций для неориентированного графа, приведенного на рис. 2.7.

Неориентированный граф

Вершины у графа рис. 2.7 обозначены цифрами, а ребра – латинскими буквами. Матрица смежности R и матрица инциденций S будут иметь вид:

Степенью вершины хi. обозначаемой deg(xi ) или . называют число ребер, инцидентных вершине xi. Так, для графа рис. 2.7 имеем: . Если =1, то вершину называют тупиковой (вершина 4 рис.2.7). Если =0, то вершину называют изолированной (вершина 5 рис. 2.7).

Теорема. Пусть G – неориентированный граф с n вершинами и m ребрами и — степень j –ой вершины. Тогда

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

Следствие. В каждом графе число вершин нечетной степени четно.

Для неориентированного графа понятия «подграф», «частичный граф» аналогичны соответствующим понятиям для ориентированного графа.

С понятием неориентированного графа связана важная характерис-тика, называемая связностью графа. Граф связен. если любые две его вершины можно соединить цепью. Если граф G не связен, то его можно разбить на такие подграфы Gi. что все вершины в каждом подграфе связны, а вершины из различных подграфов не связны. Такие подграфы Gi называют компонентами связности графа G.

Итак, если в произвольном графе G вершина а связана с вершиной b, а вершина b связана с вершиной c, то очевидно, что а связана с с. Отношение связанности вершин является отношением эквивалентности. Следовательно, существует такое разложение множества вершин на попарно непересекающиеся подмножества, что все вершины в каждом связаны, а вершины из различных не связаны. В соответствии с этим и имеем прямое разложение графа на непересекающиеся связанные подграфы — компоненты связности графа G. Т.о. получили следующее утверждение (Теорема ):

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

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

Для того, чтобы определить связность ориентированного графа, не нужно обращать внимание на ориентацию дуг. Граф, изображенный на рис. 2.1, несвязный, однако его подграф, состоящий из вершин b, c, d, e, является связным. Для ориентированного графа существует понятие сильной связности. Граф сильно связен, если для любых двух вершин (x и у, х¹у) существует путь, идущий из х в у.

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

2.2. Неориентированные графы.

Иногда граф рассматривают без учета ориентации дуг, тогда его называют неориентированным графом . Понятие “дуга”, “путь” и “контур» для неориентированного графа заменяются понятиями “ребро”, “цепь”, “цикл”. Ребро — это отрезок, соединяющий 2 вершины. Цепь — последовательность ребер. Цикл — цепь, у которой начальная и конечная вершины совпадают. Описать неориентированный граф можно путем задания пары множеств (Х,U), где Х — множество вершин; U — множество ребер. Однако более удобным является описание неориентированного графа с помощью матрицы смежности или инцидентности, которые строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между заходящей в вершину и исходящей из нее дугами. При этом вершины х и y называют смежными, если существует соединяющее их ребро, а само это ребро называется инцидентным вершинам х и у.

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

Степенью вершины х, обозначаемой deg(x) или dx, называют число ребер, инцидентных вершине х. Так для графа на рис.2.4 имеем d1 =2, d2 =2, d3 =3, d4 =1, d5 =0. Если dx =1, то вершину называют тупиковой ; если dx =0 то вершину называют изолированной.

Теорема. Пусть G — неориентированный граф с n вершинами и m ребрами и dj — степень j-й вершины тогда  n j=1 dj =2m.

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

Следствие. В каждом графе число вершин нечетной степени четно.

Для неориентированного графа понятия “подграф” и “частичный граф” аналогичны соответствующим понятиям для ориентированного графа.

СНеориентированный графпонятием неориентированного графа связана важная характеристика, называемаясвязностью графа . Говорят, что граф связен, если любые две его вершины можно соединить цепью. Если граф G не связен, то его можно разбить на такие подграфы Gi. что все вершины в каждом подграфе связны, а вершины из различных подграфов не связны. Такие подграфы Gi называют компонентами связности графа G. Если из графа (рис.2.4) исключить изолированную вершину 5, то полученный граф будет связным. Граф на рис.2.5 не связен и имеет две компоненты связности.

Неориентированный граф

Его можно превратить в связный, добавив ребро (мост), соединяющее вершины 3 и 5 (штриховая линия). Удаление моста превращает связной граф в несвязный.

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

Рис.2.5- Несвязный граф.

Неориентированный граф

Рис.2.6 — Граф в форме дерева

Однако его подграф, состоящий из вершин b,c,d,e является связным. Для ориентированного графа существует понятие сильной связности. Граф сильно связан, если для любых 2-х вершин (х и у, ху) существует путь, идущий из х в у. Важный частный случай неориентированного графа — дерево. (рис.2.6) Деревом называют конечный связный неориентированный граф, не имеющий циклов. Если дано множество вершин a,b,c. то дерево можно построить следующим образом. Одной из вершин например а, примем за начальную и назовем его корнем дерева. Из этой вершины проводим ребра в близлежащие вершины b, c, d. из них проводим рёбра в соседние с ними вершины c, f, g, h. и т.д. Т.о. дерево можно построить последовательно добавляя рёбра в его вершинах. Это даёт возможность установить связь между числом вершин и числом рёбер дерева. Простейшее дерево состоит из 2-х вершин, соединённых ребром. Каждый раз когда мы добавляем ещё одно ребро, в конце его прибавляется так же и вершина. Следовательно, дерево с n вершинами имеет n-1 рёбер.

Неориентированный граф

Неориентированным графом называется множество как угодно размещенных на плоскости, точек, некоторые из которых соединены линиями любой формы. Два неориентированных графа считаются неразличимыми, если они отличаются друг от друга только формой соединительных линий или способом размещения точек на плоскости.  [16]

Неориентированным графом пли просто графом G ( X, U) называется упорядоченная пара — ( X, U), где X есть множество вершин графа, a U есть множество неупорядоченных пар элементов из X, называемых ребрами графа.  [17]

Рассмотрим неориентированный граф О, показанный на рис. 5.3, где все веса вершин и длины ребер равны единице.  [19]

Связный неориентированный граф. не содержащий циклов, называется деревом. В частности, дерево не имеет петель и кратных ребер. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. В дереве любые две вершины связаны единственной цепью. Величина дерева равна произведению величины его ребер.  [20]

Дан неориентированный граф Г ( V, Е) без кратных ребер и петель, причем V v, E e, и натуральное число г / о. Вершины графа размещаются в целых точках интервала 10, v — 1 ] числовой прямой. Под длиной ребра ( i, ; ) Е при данном размещении понимается число х ( — х, где х и х — координаты точек, в которых размещены вершины in / графа Г соответственно.  [21]

Каждый неориентированный граф распадается единственным образом в прямую сумму ( 2.2 2) своих связных компонент.  [22]

Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево но имеет петель п ратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов.  [23]

Любой неориентированный граф без изолированных вершин имеет такое доминирующее множество D, что его дополнение D также является доминирующим множеством.  [24]

Связанный неориентированный граф называется деревом, если он не имеет циклов.  [25]

Связный неориентированный граф содержит эйлеров цикл тогда и только тогда, когда степень каждой вершины четна.  [26]

Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов.  [27]

Дан неориентированный граф F ( F, E) и натуральное число уй.  [28]

Неориентированный граф это:

Неориентированный граф

Неориентированный граф с шестью вершинами и семью рёбрами

В математической теории графов и информатике граф — это совокупность объектов со связями между ними.

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

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

Содержание

Определения

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

Неориентированный граф

Граф или неориентированный графG — это упорядоченная пара G. = (V ,E ). для которой выполнены следующие условия:

  • V это множество вершин или узлов ,
  • E это множество пар (в случае неориентированного графа — неупорядоченных) различных вершин, называемых рёбрами .

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

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

Вершины u и v называются концевыми вершинами (или просто концами ) ребра e = <u ,v >. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними .

Два ребра называются смежными. если они имеют общую концевую вершину.

Два ребра называются кратными. если множества их концевых вершин совпадают.

Ребро называется петлёй. если его концы совпадают, то есть e = <v ,v > .

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

Вершина называется изолированной. если она не является концом ни для одного ребра; висячей (или листом ), если она является концом ровно одного ребра.

Ориентированный граф

Неориентированный граф

Ориентированный граф (сокращённо орграф ) G — это упорядоченная пара G. = (V ,A ). для которой выполнены следующие условия:

  • V это множество вершин или узлов ,
  • A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами .

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

Смешанный граф

Смешанный графG — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G. = (V ,E ,A ). где V. E и A определены так же, как выше.

Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

Прочие связанные определения

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

Ориентированным путём в орграфе называют конечную последовательность вершин viНеориентированный граф, для которой все пары (vi ,vi + 1 ) Неориентированный граф являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u ,v ,u ) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

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

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

Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v », является отношением эквивалентности. и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

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

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

Дополнительные характеристики графов

  • связным . если для любых вершин u. v есть путь из u в v .
  • сильно связным или ориентированно связным. если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
  • деревом . если он связный и не содержит простых циклов.
  • полным. если любые его две (различные, если не допускаются петли) вершины соединены ребром.
  • двудольным . если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2 .
  • k-дольным. если его вершины можно разбить на k непересекающихся подмножества V1. V2. …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
  • полным двудольным. если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
  • планарным . если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
  • взвешенным. если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.

Способы представления графа в информатике

Матрица смежности

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

Недостатком являются требования к памяти — очевидно, квадрат количества вершин.

Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i -ой строки с j -м столбцом матрицы записывается:

1 в случае, если связь j «выходит» из вершины i. −1, если связь «входит» в вершину, любое число, отличное от 0, 1, −1, если связь является петлей, 0 во всех остальных случаях.

Данный способ является самым ёмким (размер пропорционален | E | | V | ) и неудобным для хранения, но облегчает нахождение циклов в графе.

Список рёбер

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

Обобщение понятия графа

Более абстрактно, граф можно задать как тройку Неориентированный граф, где V и E — некоторые множества (вершин и рёбер. соотв.), а Неориентированный граффункция инцидентности (или инцидентор ), сопоставляющая каждому ребру Неориентированный граф (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов ). Частными случаями этого понятия являются:

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

Под данное выше определение не подходят некоторые другие обобщения:

Литература

  • Оре О. Теория графов. М. Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
  • Уилсон Р. Введение в теорию графов. Пер с англ. М. Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
  • Харари Ф. Теория графов. М. Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
  • Кормен Т. М.и др.Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М. «Вильямс». 2006. — С. 1296. — ISBN 0-07-013151-1
  • Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М. Физико-математическая литература, 1997. — ISBN 5-02-015033-9
  • Емеличев В. А. Мельников О. И. Сарванов В. И. Тышкевич Р. И. Лекции по теории графов. М. Наука, 1990. 384с. (Изд.2, испр. М. УРСС, 2009. 392 с.)
  • Кирсанов М. Н. Графы в Maple. М. Физматлит, 2007. — 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf

Популярные программы для визуализации графов

Wikimedia Foundation. 2010 .

Смотреть что такое «Неориентированный граф» в других словарях:

неориентированный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN undirected graph … Справочник технического переводчика

неориентированный граф — neorientuotasis grafas statusas T sritis automatika atitikmenys: angl. undirected graph vok. ungerichteter Graph, m rus. неориентированный граф, m pranc. graphe non orienté, m … Automatikos terminų žodynas

Граф (теория графов) — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия

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

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

Гамильтонов граф — Граф додекаэдра с выделенным циклом Гамильтона … Википедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Двудольный граф — Биграф Двудольный граф или биграф  это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия

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

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

  • Графы в задачах анализа и синтеза структур сложных систем. Владимир Овчинников. Предложен единый подход к определению таких понятий, как ультраграф, гиперграф, ориентированный и неориентированный граф, и рассмотрено использование аппарата теории графов для разработки… Подробнее Купить за 590 руб электронная книга

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

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