PP_graph (Семинары)

Семинар 12. ТЕОРИЯ ГРАФОВНеформально граф можно рассматривать как множество точек исоединяющих эти точки линий со стрелками или без.Неориентированные графыНеориентированный граф G задается двумя множествамиG = (V, E),где V — конечное множество, элементы которого называют вершинами, E — множество неупорядоченных пар на V , элементыкоторого называют ребрамиТот факт, что ребро соединяет вершины u и v, т.е.{u, v} ∈ E, обозначается u p—p v ;1СЕМИНАР 12. ТЕОРИЯ ГРАФОВ2Вершины u и v, для которых u p—p v, называют смежными, атакже концами ребра {u, v} .Если u p—p v, говорят, что вершины u и v связаны отношениемнепосредственной достижимости.Ребро e называют инцидентным вершине v , если она являетсяодним из его концов.Степенью вершины v называют число dg(v) всех инцидентных ей ребер.

Можно показать, что сумма степеней всех вершинграфа равна удвоенному числу ребер (это утверждение известно каклемма о рукопожатиях“).”Цепь в неориентированном графе G — это последовательностьвершин (конечная или бесконечная) v0, v1, . . . , vn, . . . , такая, чтодля любого i vi p—p vi+1, если vi+1 существует.Для конечной цепи v0, v1, . . . , vn число n (n ≥ 0) называютдлиной цепи. Таким образом, длина цепи есть число ее ребер,т.е. всех ребер, соединяющих вершины vi и vi+1 ( i = 0, · · · , n − 1 ).СЕМИНАР 12. ТЕОРИЯ ГРАФОВ3Цепь длины 0 — это произвольная вершина графа.Говорят, что вершина v неориентированного графа G достижима из вершины u этого графа и обозначают u |==|∗ v, еслисуществует цепь v0, v1, . .

. , vn такая, что u = v0, vn = v (приэтом говорят также, что данная цепь соединяет вершины u и v,которые называют концами цепи.Таким образом, задано отношение достижимости |==|∗ внеориентированном графе.Простая цепь — это цепь, все вершины которой, кроме, бытьможет, первой и последней, попарно различны, и все ребра попарноразличны.Простую цепь ненулевой длины с совпадающими концами называют циклом.Граф, не содержащий циклов, называют ациклическим.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ4Ориентированные графыОриентированный граф (или, коротко, орграф) G задаетсядвумя множествамиG = (V, E),где V — конечное множество, элементы которого называют вершинами, E — множество упорядоченных пар на V, т.е. подмножество множества V × V , элементы которого называют дугами.Тот факт, что дуга ведет из вершины u в вершину v, т.е.(u, v) ∈ E, обозначается u → v ; если это необходимо, под стрелкойуказывается имя графа G ( u →G v ).Вершины u и v, для которых u → v , называют смежными,причем u называют началом, а v — концом дуги (u, v) .

Дугу,начало и конец которой есть одна и та же вершина, называют петлей. Если u → v , то из вершины u непосредственно достижимавершина v . Говорят, что вершины u и v связаны отношениемнепосредственной достижимости.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ5Дугу (u, v) называют заходящей в вершину v и исходящейиз вершины u . Дугу называют инцидентной вершине v, еслиона или заходит в v или исходит из v .Полустепенью захода вершины v называют число dg−(v)заходящих в нее дуг, а полустепенью исхода вершины v —число dg+(v) исходящих из нее дуг. Степень вершины v,обозначаемая dg(v) — это сумма полустепеней захода и исхода.Путь в ориентированном графе G — это последовательностьвершин (конечная или бесконечная) v0, v1, .

. . , vn, . . . , такая, чтодля любого i vi → vi+1, если vi+1 существует.Для конечного пути v0, v1, . . . , vn число n называют длинойпути (n ≥ 0) . Тем самым длина пути есть число его дуг, т.е. всехдуг, которые ведут из вершины vi в вершину vi+1 ( i = 0, · · · , n−1 ).Путь длины 0 — это произвольная вершина графа.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ6Говорят, что вершина v ориентированного графа G достижимаиз вершины u этого графа и обозначают u ⇒∗ v, если существуетпуть v0, v1, . .

. , vn, такой, что u = v0, v = vn (при этомговорят, что данный путь ведет из вершины u в вершину v,называя первую вершину началом, а вторую — концом данногопути). Таким образом, задано отношение достижимости ⇒∗в ориентированном графе.Отношение достижимости в ориентированном графе рефлексивнои транзитивно, но в общем случае не антисимметрично, так какесли две вершины орграфа достижимы одна из другой, то из этогововсе не следует, что они совпадают. Таким образом, отношениедостижимости в орграфе есть отношение предпорядка.Простой путь — это путь, все вершины которого, кроме, бытьможет, первой и последней, попарно различны.Простой путь ненулевой длины, начало и конец которого совпадают, называют контуром.СЕМИНАР 12.

ТЕОРИЯ ГРАФОВ7Граф (неориентированный или ориентированный) G1 = (V1, E1)называют подграфом графа G = (V, E) (соответственно, неориентированного или ориентированного), если V1 ⊆ V и E1 ⊆ E.Обозначение: G1 ⊆ G .Подграф G1 графа G называют подграфом, порожденныммножеством вершин V1 ⊆ V, если каждое ребро (или дуга)тогда и только тогда принадлежит E1 ⊆ E, когда его концыпринадлежат V1.Неориентированный графКомпонента связности (компонента) неориентированногографа G — это максимальный подграф G1 ⊆ G, любые двевершины u и v которого соединены цепью ( u |==|∗ v ).Две различные компоненты неориентированного графа не пересекаются, т.е. не имеют ни общих вершин, ни общих ребер.Неориентированный граф, который сам является компонентой, называют связным.СЕМИНАР 12.

ТЕОРИЯ ГРАФОВ8Ориентированный графКомпонента связности (или, просто, компонента) ориентированного графа G — это максимальный подграф G1 ⊆ G, для любых двух вершин u, v которого вершина v достижима из вершиныu или вершина u достижима из вершины v (u ⇒∗ v или v ⇒∗ u).Компоненты орграфа могут пересекаться.Орграф, который сам является компонентой, называют связным.Для орграфа можно определить также понятия сильной и слабойсвязности.Бикомпонентой орграфа называют такой его максимальныйподграф, что для любых двух его вершин u и v вершина vдостижима из вершины u и вершина u достижима из вершины v(u ⇒∗ v и v ⇒∗ u).

Орграф, являющийся бикомпонентой, называютсильно связным.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ9Неориентированный граф G1 = (V1, E1) называют ассоциированным с орграфом G = (V, E), если V1 = V и E1 ={{u, v} | (u, v) ∈ E или (v, u) ∈ E, u 6= v}.Содержательно переход от орграфа к ассоциированному с нимнеориентированному графу состоит в стирании“ ориентации дуг”орграфа с учетом того, что все петли исчезают, а дуги (u, v) и(v, u) при u 6= v переходят в одно и то же ребро {u, v}.Орграф называют слабо связным, если ассоциированный с нимнеориентированный граф связен.

Компонентой слабой связности (слабой компонентой) орграфа называют его максимальныйслабо связный подграф.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ10Для представления графа может служить матрица смежностивершин графа. Это квадратная матрица B n -ого порядка,элементы которой определяются для неориентированного графаследующим образом:½1, если i-я и j-я вершины соед. ребром,bij =0, иначе,а для орграфа½1, если из i-й вершины в j-ю ведет дугаbij =0, иначе.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ11Задачи12.1. Сколько существует n -вершинных неориентированных графов, т.е. сколько существует различных подмножеств множествавсех неупорядоченных пар на множестве из n вершин?12.2.

Доказать, что если число ребер неориентированного графа2 , то он связен.c n вершинами при n > 2, больше Cn−112.3. Доказать , что в связном неориентированном графе любыедве простые цепи максимальной длины имеют общую вершину.12.4. Доказать, что не существует нериентированного графа,степени всех вершин которого попарно различны.12.5. Пусть Gn — неориентированный граф, вершины которогопронумерованы натуральными числами {1, 2, .

. . , n} , а множестворебер определяется следующим условием: несовпадающие вершиныvi и vj смежны тогда и только тогда, когда числа i и j взаимнопросты.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ12(а) Записать матрицу смежности графа G5. Установить, являетсяли граф связным?(б) Является ли граф Gn связным?(в) Доказать, что при m < n граф Gm является порожденнымподграфом графа Gn.12.6. Найти число всех n -вершинных орграфов, т.е. число различных подмножеств множества всех упорядоченных пар на множестве из n вершин.P +P −dg (v) ,dg (v) ,P12.7.

Установить связь между числамиdg(v) для произвольной вершины v орграфа?12.8. Установить, связен ли орграф, изображенный на рисунке?Найти все его компоненты и бикомпоненты.СЕМИНАР 12. ТЕОРИЯ ГРАФОВ2-6q6q@I@3@q¡µ@¡q¡?1135q@@Rq?4Рис. 12.112.9. Доказать, что отношение взаимной достижимости в орграфеесть эквивалентность.12.10. Доказать, что орграф связен тогда и только тогда, когдав нем есть путь, проходящий через все вершины. Останется ли этоутверждение справедливым, если потребовать, чтобы существовалпростой путь..