Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.


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


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


Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинарных отношений. Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать.


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


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


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


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




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


Неориентированный граф [math]G[/math] задается двумя множествами [math]G=(V,E)[/math], где [math]V[/math] — конечное множество, элементы которого называют вершинами или узлами; [math]E[/math] — множество неупорядоченных пар на [math]V[/math], т.е. подмножество множества двухэлементных подмножеств [math]V[/math], элементы которого называют ребрами. Для каждого ребра [math]\{u,v\}\in E[/math] считаем, что [math]u[/math] и [math]{v}[/math] — различные вершины.


Если ребро [math]e=\{u,v\}[/math], то говорят, что ребро [math]e[/math] соединяет вершины [math]u[/math] и [math]{v}[/math], и обозначают это мы [math]u\mapsto v[/math]; если необходимо, указывают имя графа [math]G\colon u\mapsto_{G}v[/math].


Вершины [math]u[/math] и [math]{v}[/math], соединенные ребром [math](u\mapsto v)[/math], называют смежными, а также концами ребра [math]\{u,v\}[/math]. Если [math]u\mapsto v[/math], говорят, что вершины [math]u[/math] и [math]{v}[/math] связаны отношением непосредственной достижимости.


Ребро [math]e[/math] называют инцидентным вершине [math]{v}[/math], если она является одним из его концов.


Степенью вершины [math]{v}[/math] называют число [math]\operatorname{dg}v[/math] всех инцидентных ей ребер.


Для вершины [math]{v}[/math] множество [math]\Gamma(v)=\{x\colon\,x\mapsto v\}[/math] называют множеством смежных с [math]{v}[/math] вершин. Справедливо равенство [math]\operatorname{dg}v=|\Gamma(v)|[/math].


Цепь в неориентированном графе [math]G[/math] — это последовательность вершин (конечная или бесконечная) [math]v_0,v_1,\ldots,v_n,\ldots[/math], такая, что [math]v_i\mapsto v_{i+1}[/math] для любого [math]i[/math], если [math]v_{i+1}[/math] существует. (Под конечной последовательностью понимается кортеж вершин.)


Для конечной цепи [math]v_0,v_1,\ldots,v_n[/math] число [math]n~(n\geqslant0)[/math] называют длиной цепи. Таким образом, длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины [math]v_i[/math] и [math]v_{i+1}~(i=\overline{0,n-1})[/math]. Цепь длины 0 — это произвольная вершина графа.


Говорят, что вершина [math]{v}[/math] неориентированного графа [math]G[/math] достижима из вершины [math]u[/math] этого графа и обозначают и [math]u\shortmid\!= \!\shortmid^{\ast}\!v[/math], если существует цепь [math]v_0,v_1,\ldots,v_n[/math] такая, что [math]u=v_0,[/math] [math]v_n=v[/math] (при этом говорят также, что данная цепь соединяет вершины [math]u[/math] и [math]{v}[/math], которые называют концами цепи). Таким образом, задано отношение достижимости [math]\shortmid\!=\!\shortmid^{\ast}[/math] в неориентированном графе. Оно является рефлексивно-транзитивным замыканием отношения [math]\shortmid\!\!\!-\!\!\!\shortmid[/math] непосредственной достижимости.


Отношение достижимости в неориентированном графе рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности


Если существует цепь ненулевой длины, соединяющая [math]u[/math] и [math]{v}[/math], то пишут [math]u\shortmid\!= \!\shortmid^{+}\!v[/math]. Если необходимо явно указать длину цепи, то пишут [math]u \shortmid\!=\!\shortmid^{n}\!v[/math] и говорят, что существует цепь длины [math]n[/math], соединяющая [math]u[/math] и [math]{v}[/math].


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



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


Ориентированный граф [math]G[/math] задается двумя множествами [math]G=(V,E)[/math], где [math]V[/math] — конечное множество, элементы которого называют вершинами или узлами; [math]E[/math] — множество упорядоченных пар на [math]V[/math], т.е. подмножество множества [math]V\times V[/math], элементы которого называют дугами.


Если дуга [math]e=(u,v)[/math], то говорят, что дуга [math]e[/math] ведет из вершины [math]u[/math] в вершину [math]{v}[/math], и обозначают это [math]u\to v[/math]; если необходимо, указывают имя графа [math]G\colon u\to_{G}v[/math].


Вершины [math]u[/math] и [math]{v}[/math], такие, что из вершины [math]u[/math] в вершину [math]{v}[/math] ведет дуга [math](u\to v)[/math], называют сиежнылси, причем м называют началом, а [math]v[/math] — концом дуги [math](u,v)[/math]. Дугу, начало и конец которой есть одна и та же вершина, называют петлей. Если [math]u\to v[/math], то говорят, что вершины и и v связаны отношением непосредственной достижимости.


Дугу [math](u,v)[/math] называют заходящей в вершину [math]{v}[/math] и исходящей из вершины [math]u[/math]. Дугу называют инцидентной вершине [math]{v}[/math], если она заходит в [math]{v}[/math] или исходит из [math]{v}[/math].


Полустепенью захода вершины [math]{v}[/math] называют число [math]\operatorname{dg}^{-}(v)[/math] заходящих в нее дуг, а полустепенью исхода вершины [math]{v}[/math] — число [math]\operatorname{dg}^{+}(v)[/math] исходящих из нее дуг. Степень вершины [math]{v}[/math], обозначаемая [math]\operatorname{dg}(v)[/math], — это сумма полустепеней захода и исхода.


Для вершины [math]{v}[/math] множество [math]\Gamma(v)=\{x\colon\, v\to x\}[/math] называют множеством преемников вершины [math]{v}[/math], а множество [math]\Gamma^{-1}(v)= \{x\colon\, x\to v\}[/math] — множеством предшественников вершины [math]{v}[/math]. Справедливы равенства


[math]\operatorname{dg}^{+}(v)= |\Gamma(v)|,\qquad \operatorname{dg}^{-}(v)= |\Gamma^{-1}(v)|.[/math]

Путь в ориентированном графе [math]G[/math] — это последовательность вершин (конечная или бесконечная) [math]v_0,v_1,\ldots,v_n,\ldots[/math], такая, что [math]v_i\to v_{i+1}[/math] для любого [math]i[/math], если [math]v_{i+1}[/math] существует.


Для конечного пути [math]v_0,v_1,\ldots,v_n[/math] число [math]n[/math] называют длиной пути [math](n\geqslant0)[/math]. Тем самым длина пути есть число его дуг, т.е. всех дуг, которые ведут из вершины [math]v_i[/math] в вершину [math]v_{i+1}~(i=\overline{0,n-1})[/math]. Путь длины 0 — это произвольная вершина графа.


Говорят, что вершина [math]{v}[/math] ориентированного графа [math]G[/math] достижима из вершины [math]u[/math] этого графа и обозначают [math]u\Rightarrow^{\ast}v[/math], если существует путь [math]v_0,v_1,\ldots,v_n[/math]. такой, что [math]u=v_0,~v=v_n[/math] (при этом говорят, что данный путь ведет из вершины [math]u[/math] в вершину [math]{v}[/math], называя первую вершину началом, а вторую — концом данного пути). Таким образом, задано отношение достижимости [math]\Rightarrow^{\ast}[/math] в ориентированном графе. Оно является рефлексивно-транзитивным замыканием отношения [math]\to[/math] непосредственной достижимости.


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


Если существует путь ненулевой длины, ведущий из [math]u[/math] в [math]{v}[/math], то пишут [math]u\Rightarrow^{+}v[/math]. Если необходимо явно указать длину пути, то пишут [math]u\Rightarrow^{n}v[/math] и говорят, что существует путь длины [math]n[/math], ведущий из [math]u[/math] в [math]{v}[/math].


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



Пример замкнутой цепи в неориентированном графе

Замечание 5.1. Требование, чтобы все ребра простой цепи неориентированного графа были попарно различными, существенно. Если его снять, то цепь вида [math]u,v,u[/math], где [math]u\mapsto v[/math], будет циклом, в котором одно и то же ребро [math]\{u,v\}[/math] проходится дважды в противоположных направлениях, хотя такую цепь естественно циклом не считать. Не будет эта цепь в соответствии с принятой терминологией и замкнутой цепью.


В неориентированном графе на рис. 5.1 цепь [math]a \shortmid\!\!\!-\!\!\!\shortmid b \shortmid\!\!\!-\!\!\!\shortmid \! c \shortmid\!\!\!-\!\!\!\shortmid d \shortmid\!\!\!-\!\!\!\shortmid e \shortmid\!\!\!-\!\!\!\shortmid c \shortmid\!\!\!-\!\!\!\shortmid a[/math] является примером замкнутой цепи.


Замечание 5.2. В общем случае в ориентированном графе пересечение множества преемников [math]\Gamma(v)[/math] вершины [math]{v}[/math] и множества [math]\Gamma^{-1}(v)[/math] ее предшественников будет не пусто, если есть петля [math](v,v)\colon\, \Gamma(v)\cap \Gamma^{-1}(v)\ne \varnothing[/math].


Пример 5.1. Рассмотрим неориентированный граф, изображенный на рис. 5.2. Он задается множеством вершин


Неориентированный граф, в котором последовательность вершин есть простая цепь
[math]V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}[/math]

и множеством неупорядоченных пар [math]E=\bigl\{\{v_1,v_2\}, \{v_1,v_3\}, \{v_2,v_3\}, \{v_3,v_4\}, \{v_5,v_6\}\bigr\}[/math].


В этом графе последовательность вершин [math]v_1,v_3,v_4[/math] есть простая цепь, а последовательность [math]v_1,v_3,v_2,v_1,v_3,v_4[/math] — цепь, не являющаяся простои, поскольку в ней есть совпадающие ребра. Последовательность вершин [math]v_3,v_1,v_2,v_4[/math] не является цепью, поскольку в графе нет ребра [math]\{v_2,v_4\}[/math]. Последовательность [math]v_1,v_3,v_2,v_1[/math] есть цикл, а последовательность [math]v_4,v_3,v_1,v_2,v_3,v_4[/math] — цепь с совпадающими концами, но не цикл, поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней есть повторяющееся ребро [math]\{v_3,v_4\}[/math].


Степени вершин графа следующие:


[math]\operatorname{dg}v_1= \operatorname{dg}v_2=2,\quad \operatorname{dg}v_3=3,\quad \operatorname{dg}v_4= \operatorname{dg}v_5= \operatorname{dg}v_6=1,\quad \operatorname{dg}v_7=0.[/math]

Вершины [math]v_1,v_2,v_3,v_4[/math] попарно достижимы [math](v_i \shortmid\!=\!\shortmid^{\ast}\! v_j,~ i,j\in\{1,2,3,4\})[/math] и образуют класс эквивалентности по отношению достижимости. Для вершин [math]v_5[/math] и [math]v_6[/math] имеет место [math]v_5 \shortmid\!=\!\shortmid^{\ast}\! v_6[/math], и они также образуют класс эквивалентности. Заметим, что вершина V7, по определению, образует цепь длины 0 и эквивалентна по отношению достижимости только самой себе.


Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он задается множеством вершин [math]V=\{v_1,v_2,v_3,v_4,v_5,v_6\}[/math] и множеством дуг


[math]E= \bigl\{(v_1,v_2), (v_1,v_3), (v_2,v_1), (v_2,v_3), (v_2,v_4), (v_3,v_1), (v_3,v_4), (v_5,v_6), (v_6,v_4)\bigr\}.[/math]

Ориентированный граф, в котором последовательность вершин есть простой путь

В этом ориентированном графе последовательность вершин [math]v_1,v_2,v_3,v_4[/math] есть простой путь, а последовательность вершин [math]v_1,v_2,v_3,v_1,v_3,v_4[/math] — путь, не являющийся простым, поскольку в нем, например, два раза встречается вершина, не служащая началом и концом пути.


Последовательность вершин [math]v_3,v_1,v_2,v_3[/math] есть контур, а последовательность [math]v_3,v_1,v_2,v_1,v_3[/math] — замкнутый путь, но не контур, поскольку вершина [math]v_1[/math], не являющаяся началом пути, встречается два раза. Последовательность вершин [math]v_1,v_3,v_4,v_6[/math] не задает путь, так как в рассматриваемом ориентированном графе нет дуги [math](v_4,v_6)[/math].


Полустепени захода, полустепени исхода и степени у вершин следующие:


[math]\begin{array}{lll}\operatorname{dg}^{-}(v_1) = 2,&\qquad \operatorname{dg}^{+}(v_1)= 2,&\qquad \operatorname{dg}(v_1)=4;\\[4pt] \operatorname{dg}^{-}(v_2) =1,&\qquad \operatorname{dg}^{+}(v_2)=3,&\qquad \operatorname{dg}(v_2)=4;\\[4pt] \operatorname{dg}^{-}(v_3)=2,&\qquad \operatorname{dg}^{+}(v_3)=2,&\qquad \operatorname{dg}(v_3)=4;\\[4pt] \operatorname{dg}^{-}(v_4) =3,&\qquad \operatorname{dg}^{+}(v_4)=0,&\qquad \operatorname{dg} (v_4)=3;\\[4pt] \operatorname{dg}^{-}(v_5) =0,&\qquad \operatorname{dg}^{+} (v_5)=1,&\qquad \operatorname{dg}(v_5)=1;\\[4pt] \operatorname{dg}^{-}(v_6) =1,&\qquad \operatorname{dg}^{+} (v_6)=1,&\qquad \operatorname{dg}(v_6)=2. \end{array}[/math]



Свойства отношения достижимости в графах


Отношение достижимости в неориентированных и ориентированных графах обладает следующим важным свойством.


Теорема 5.1. Для любой цепи, соединяющей две вершины неориентированного графа, существует простая цепь, соединяющая те же вершины. Для любого пути, ведущего из вершины [math]u[/math] в вершину [math]{v}[/math] ориентированного графа, существует простой путь, ведущий из [math]u[/math] в [math]{v}[/math].


Проведем доказательство для неориентированного графа (для ориентированного графа доказательство проводится аналогично).


Цепи неориентированных графов

Пусть вершины [math]u[/math] и [math]{v}[/math] неориентированного графа таковы, что [math]u \shortmid\!=\!\shortmid^{\ast}\!v[/math]. Если эти вершины являются концами цепи нулевой длины, то утверждение теоремы тривиально. Пусть [math]u \shortmid\!=\!\shortmid^{+}\!v[/math], т.е. существует цепь ненулевой длины, соединяющая [math]u[/math] в [math]{v}[/math]. Рассмотрим какую-либо из таких цепей (рис. 5.4). Обозначим ее [math]C[/math]. Если цепь [math]C[/math] простая, то доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина [math]w[/math] цепи [math]C[/math], которая повторяется в этой цепи, т.е. [math]u \shortmid\!=\!\shortmid^{\ast}\! w \shortmid\!=\!\shortmid^{+}\!w \shortmid\!=\!\shortmid^{\ast}\!v[/math]. Это значит, что вершина [math]w[/math] содержится в некоторой цепи [math]C'[/math] ненулевой длины (подцепи цепи [math]C[/math]) с совпадающими концами (рис. 5.5). Удалим все вершины и ребра цепи [math]C'[/math], кроме вершины [math]w[/math] (служащей ее началом и концом одновременно). После этого получим новую цепь [math]C_1[/math], соединяющую вершины [math]u[/math] и [math]{v}[/math] (рис. 5.6), в которой число повторений вершины [math]w[/math] будет по крайней мере на единицу меньше, чем в цепи [math]C[/math]. Если цепь [math]C_1[/math] простая, то утверждение доказано. В противном случае поступаем с ней так же, как и с цепью [math]C[/math]. В силу конечности множества вершин и ребер графа после конечного числа шагов получим простую цепь, соединяющую вершины [math]u[/math] и [math]{v}[/math].


Следствие 5.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина ориентированного графа содержится в некотором замкнутом пути, то она содержится и в некотором контуре.


Замечание 5.3. Следствие 5.1 перестает быть верным для произвольной цепи с совпадающими концами. Например, для неориентированного графа, состоящего из двух вершин [math]v_1,v_2[/math] и единственного ребра [math](v_1,v_2)[/math] цепь [math]v_1,v_2,v_1[/math] с совпадающими концами не содержит цикла.




Подграфы неориентированных и ориентированных графов


Перейдем теперь к понятию подграфа. Формулируется это понятие одновременно для неориентированных и ориентированных графов (с учетом различий в терминологии).


Определение 5.1. Неориентированный (ориентированный) граф [math]G_1= (V_1,E_1)[/math] называют подграфом неориентированного (ориентированного) графа [math]G= (V,E)[/math], если [math]V_1\subseteq V[/math] и [math]E_1\subseteq E[/math].


Будем использовать обозначение [math]G_1\subseteq G[/math], аналогичное обозначению включения для множеств.


Замечание 5.4. Так как в определении 5.1 пара [math]G_1= (V_1,E_1)[/math] есть неориентированный (ориентированный) граф, то для любого ребра [math]\{u,v\}\in E_1[/math] (дуги [math](u,v)\in E_1[/math]) предполагается, конечно, что [math]u,v\in V_1[/math], поскольку иначе пару [math](V_1,E_1)[/math] нельзя будет считать неориентированным (ориентированным) графом.


Если хотя бы одно из указанных двух включений в определении 5.1 строгое, то [math]G_1[/math] называют собственным подграфом графа [math]G[/math]; если [math]V_1=V[/math], то [math]G_1[/math] называют остовным подграфом графа [math]G[/math].


Подграф [math]G_1[/math] неориентированного (ориентированного) графа [math]G[/math] называют подграфом, порожденным множеством вершин [math]V_1\subseteq V[/math], если каждое ребро (дуга) тогда и только тогда принадлежит [math]E_1\subseteq E[/math], когда его (ее) концы принадлежат [math]V_1[/math]. Часто в случае, если множество вершин [math]V_1[/math] подразумевается, говорят просто о порожденном подграфе.


Отметим, что подграф графа [math]G[/math], порожденный множеством вершин [math]V_1[/math], в отличие от произвольного подграфа графа [math]G[/math] с множеством вершин [math]V_1[/math], должен включать все ребра (дуги), концы которых принадлежат множеству [math]V_1[/math].


Подграф [math]G_1\subseteq G[/math] называют максимальным подграфом, обладающим данным свойством [math]P[/math], если он не является собственным подграфом никакого другого подграфа графа [math]G[/math], обладающего свойством [math]P[/math].


Например, на рис. 5.7 подграфы [math]G_1,\,G_2,\,G_3[/math] являются максимальными ациклическими подграфами графа [math]G[/math]. Отметим, что они также являются собственными и остовными подграфами указанного графа.


Максимальные ациклические подграфы графа



Связность и компонента связности графов


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


Неориентированный граф называют связным, если любые две его вершины [math]u[/math] и [math]{v}[/math] соединены цепью [math](u \shortmid\!=\!\shortmid^{\ast}\!v)[/math].


Компонента связности (или просто компонента) неориентированного графа — это его максимальный связный подграф.


Ориентированный граф называют связным, если для любых двух его вершин [math]u,v[/math] вершина [math]{v}[/math] достижима из вершины [math]u[/math] или вершина [math]u[/math] достижима из вершины [math]{v}[/math] ([math]u \Rightarrow^{\ast}v[/math] или [math]v\Rightarrow^{\ast}u[/math]).


Компонента связности (или просто компонента) ориентированного графа — это максимальный связный подграф.


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


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


Так как отношение достижимости в ориентированном графе не является эквивалентностью, то компоненты ориентированного графа могут пересекаться.


Связный ориентированный граф

Пример 5.3. Граф, изображенный на рис. 5.2, не является связным. Он состоит из трех компонент. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости, указанными в примере 5.1.


Связными являются все графы, изображенные на рис. 5.7.


Ориентированный граф на рис. 5.8 связный, а ориентированные графы на рис. 5.3 и 5.9 не являются связными. В ориентированном графе на рис. 5.3 вершины [math]v_2[/math] и [math]v_5[/math] не достижимы одна из другой, а в ориентированном графе на рис. 5.9 взаимно не достижимы, например, вершины [math]v_2[/math] и [math]v_6[/math]. В ориентированном графе, изображенном на рис. 5.9, имеются две компоненты связности: [math]C_1[/math] и [math]C_2[/math], которые пересекаются.


Ориентированный граф с взаимно не достижимыми вершинами



Сильная и слабая связности графов


Для ориентированного графа можно определить также понятия сильной и слабой связности.


Определение 5.2. Ориентированный граф называют сильно связным, если для любых двух его вершин [math]u[/math] и [math]{v}[/math] вершина [math]{v}[/math] достижима из вершины [math]u[/math] и вершина [math]u[/math] достижима из вершины [math]{v}[/math] ([math]u\Rightarrow^{\ast}v[/math] и [math]v\Rightarrow^{\ast}u[/math]). Бикомпонента ориентированного графа — это его максимальный сильно связный подграф.


Если [math]u\Rightarrow^{\ast}v[/math] и [math]v\Rightarrow^{\ast}u[/math], то говорят, что [math]u[/math] и [math]{v}[/math] связаны отношением взаимной достижимости. Это бинарное отношение рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности. Следовательно, две различные бикомпоненты не пересекаются, т.е. не имеют ни общих вершин, ни общих ребер.


Пример 5.4. а. В ориентированном графе, изображенном на рис. 5.3, бикомпонентой является подграф [math]G_1[/math], порожденный множеством вершин [math]\{v_1,v_2,v_3\}[/math]. Действительно, эти вершины взаимно достижимы, поэтому ориентированный граф [math]G_1[/math] сильно связный. Так как из вершин [math]v_4,v_5,v_6[/math] ни одна из вершин [math]v_1,v_2,v_3[/math] не достижима, то выделенный сильно связный подграф [math]G_1[/math] является максимальным.


б. В ориентированном графе, представленном на рис. 5.9, имеются четыре бикомпоненты [math]B_1,\,B_2,\,B_3[/math] и [math]B_4[/math]. Это подграфы, порожденные соответственно множествами вершин [math]\{v_1\},\, \{v_2,v_3\},\, \{v_4,v_5\}[/math] и [math]\{v_6,v_7\}[/math]. Отметим, что подграф, порожденный множеством [math]\{v_1\}[/math], не содержит ни одной дуги. Тем не менее этот подграф — бикомпонента, поскольку каждая вершина достижима сама из себя (по пути длины 0).


Определение 5.3. Неориентированный граф [math]G_1=(V_1,E_1)[/math] называют ассоциированным с ориентированном графом [math]G=(V,E)[/math], если его множество вершин совпадает с множеством вершин ориентированного графа [math]G[/math], а пара [math]\{u,v\}[/math] образует ребро тогда и только тогда, когда [math]u\ne v[/math] и из [math]u[/math] в [math]{v}[/math] или из [math]{v}[/math] в [math]u[/math] ведет дуга, т.е. [math]V_1=V[/math] и


[math]E_1=\bigl\{\{u,v\}\colon\, (u,v)\in E\,\lor\, (v,u)\in E,~ u\ne v\bigr\}.[/math].

Таким образом, переход от ориентированного графа к ассоциированному с ним неориентированному графу состоит в "стирании" ориентации дуг ориентированного графа с учетом того, что все петли исчезают, а дуги [math](u,v)[/math] и [math](v,u)[/math] при [math]u\ne v[/math] переходят в одно и то же ребро [math]\{u,v\}[/math].


Для ориентированного графа, изображенного на рис. 5.10, а, ассоциированный с ним неориентированный граф приведен на рис. 5.10, б. Отметим, что дуги [math](v_1,v_2)[/math] и [math](v_2,v_1)[/math] переходят в ребро [math]\{v_1,v_2\}[/math], а петля [math](v_6,v_6)[/math] исчезает.


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

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


Ориентированные графы, представленные на рис. 5.3, 5.9 и 5.8, являются слабо связными. Ориентированный граф, изображенный на рис. 5.10, не является слабо связным, поскольку не является связным ассоциированный с ним неориентированный граф. Ориентированный граф на рис. 5.10,а имеет две компоненты слабой связности. Соответственно ассоциированный с ним неориентированный граф на рис. 5.10,б имеет две компоненты связности.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved