АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример.

-маршрут, но не цепь;

-цепь, но не простая цепь;

-простая цепь;

- цикл, но не простой цикл;

-простой цикл.

40. Связанность графа. Разделяющее множество, разрез, мост, точка сочленения. Лемма о точках сочленения

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

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

Рассмотрим две не смежные вершены u и v связного графа G.

Определение: Множество вершин (и/или ребер) S графа G называется разделяющим множеством, если удаление из графа G элементов множества S приводит к тому, что вершины u и v оказываются в разных компонентах связности. Разделяющее множество ребер называется разрезом.

Лемма о точках сочленения: В графе существуют по крайней мере 2 вершины, не являющиеся точками сочленения.

От противного d(v,w)=D(G) диаметр.

Рассмотрим ту компоненту связности, в которой v,w G_I. Удалим v Число компонент связности увеличилось появились G_I ^I,G_I ^II. Пусть v G_I ^I возьмем любое u G_I ^II. Путь от u к w проходит через v(в графе G).

d(u, w)=d(u, v)+d(v, w)>d(v, w)

41. Расстояние между вершинами графа. Диаметр, радиус, центр графа.

Длиной маршрута – число ребер в маршруте (с повторениями).

Расстояние между вершинами d(u, v) – длина самой короткой простой цепи соединяющей эти вершины. Если цепи соединяющей u и v нет, то d(u, v) = ∞.

Диаметр графа – наибольшее из расстояний между двумя его вершин. D(G) = max (d(u, v)), где u, v € V.

Максимальным удалением от вершины v (r(v)) называется наибольшее из расстояний от вершины v до всех вершин графа, r(v) = max (d(v, u)), где v € V.

Радиус – минимальное из максимальных удалений R(G) = min r(v), v € V.

Центр графа – любая его вершина такая, что r(v) = R(G).

42. Теорема об оценке числа ребер в графе и следствие о связанном графе Теорема: Число вершин р, ребер q и компонент связности k графа G удовлетворяет неравенствам

p-k<=q<=(p-k)(p-k+1)/2

Доказательство:

1) p-k<=q. Индукция по q. База p=1, k=1,q=0. Пусть оценка верна для всех графов с числом вершин меньше p. Рассмотрим граф G с p вершинами. Удалим из G вершину v, которая не я является точкой сочленения, вместе с инцидентными ей ребрами, получим граф G’. Тогда если v – изолированная вершина, то в графе G’ число вершин p’=p-1, число ребер q’=q, число компонент связности k’=k-1. Имеем p-k=p’-k’<=q’=q. Если v – не изолированная вершина, то в графе G’ число вершин p’=p-1, число ребер q<q’, число компонент связности k’=k. Имеем

p-k=p’-k’+1<=q’+1<=q.

2) q<=(p-k)(p-k+1)/2. Метод выделения «критических» графов. Число ребер q графа с р вершинами и k компонентами связности, когда число вершин в i-ой компоненте связности равно p, не превосходит числа ребер в графе с p вершинами и k компонентами связности, в котором i-ая компонента связности представляет собой полный граф K_pi. Следовательно, достаточно рассматривать графы, в которых все компоненты связности полные. Найдем среди всех таких графов граф с максимальным числом ребер.

Пусть две компоненты связности G₁ и G₂ такие, что 1<p[1]<p[2]. Если перенести одну вершину из G₁ в G₂, то число ребер изменится на q=p₂-(p₁-1)>0, то есть число ребер возрастает. Следовательно наибольшее число ребер имеет граф

Число ребер в таком графе

Следствие. Если q>(p-1)(p-2)/2, то граф связен.

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

43. Связанность орграфов: сильная, односторонняя, слабая. Фактор – граф.

Две вершины (в орграфе) v₁ и v₂ называются сильно-связанные, если существует путь из v₁ в v₂ и из v₂ в v₁.

Далее вершины (в орграфе – узлы).

Узлы v₁ и v₂ называются односторонне-связанные, если существует путь из v₁ в v₂ или из v₂ в v₁.

Узлы v₁ и v₂ называются слабо-связанные, если они связаны в графе, полученном из исходного отменой ориентации дуг.

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

Орграф называется сильно (односторонне, слабо) связанным, если любые два узла являются сильно(односторонне, слабо) связанными.

Сильная связанность влечет одностороннюю связанность, которая влечет слабую связанность. Обратное неверно.

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

Фактор-граф - орграф, полученный из исходного орграфа следующим образом. Каждая компонента сильной связности заменяется одним узлом, получаем узлы 1, …, K. Дуга {i, j} существует в фактор - графе, если и только если в исходном графе есть хотя бы одна дуга, соединяющая узел из i-ой компоненты с узлом из j-ой компоненты. Происходит конденсация графа. Рисунок намного упрощается.

Конденсацией орграфа D называется орграф, который получается стягиванием в одну верншину каждой компоненты сильной связанности орграфа D.

44 - 45. Обход графа. Стратегия обхода в глубину. Стратегия обхода в ширину.

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

Алгоритм: 1) Все вершины считаем не отмеченными. 2) Выбираем начальную вершину и отмечаем. 3) Обходим все не отмеченные вершины, смежные с текущей вершиной и заносим их в список вершин, которые будут текущими.

4) Если список пустой – выход.

5) Иначе выбираем первую вершину из списка и возвращаемся на шаг 3 в качестве текущей вершины.

Порядок выбора текущей вершин, это и есть порядок обхода в ширину.

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

Алгоритм:

1) Все вершины считаем не отмеченными. 2) Выбираем начальную вершину и отмечаем. 3) Переходим на смежную вершину и отмечаем

4) С текущей вершины переходим на следующую смежную вершину.

5) Если текущая вершина тупиковая, проверяем есть ли не обойденные, выходим, если нет, если есть, возвращаемся к предыдущей и проверяем есть ли смежные не обойденные.

Когда применяем обход «в ширину» найдем кратчайший путь, но дольше по времени, в глубину наоборот.

46. Поиск кратчайших путей в орграфе. Волновой алгоритм.

Кратчайший путь – это путь наименьшей длины.

Шаг 1: помечаем а символом 0, остальные верш. считаем не отмеченными. Полагаем номер волны k = 0.

Шаг 2: если k = p – 1 (p – число вершин). Идем на шаг 4. Иначе увеличиваем длину волны.

Шаг 3: выбираем очередную вершину, отмеченную индексом k-1. Помечаем индексом k все неотмеченные вершины, смежные с выбранной. Повторяем этот шаг, пока не исчерпаем вершины, помеченные индексом k-1. Затем вернемся на шаг 2.

Шаг 4: восстанавливаем кратчайшие пути. Если вершина b помечена индексом k, то кратчайший путь будет иметь вид: V₀V₁…V_iV_i+1…V_k-1V_k (V₀ = a, V_k = b). Путь восстанавливается от конечной вершины к начальной и вершина Vi (i = 1 … k-1) определяется так:

1) V_i помеченная символом i.

2) Существует ребро из Vi в Vi+1.

47. Поиск минимальных путей в нагруженном графе. Алгоритм Дейкстры.

Минимальный путь - это путь, который весит меньше. Нагруженный граф – это граф, ребрам которого приписаны некоторые числа, называемые весами.

Начало: Задан нагруженный граф с неотрицательными весами ребер. Требуется найти минимальные пути от вершины A до всех вершин.

Шаг 1: Полагаем d₀(a, a)=0, d₀(a, v)=∞ для каждой v≠a. (d₀-расстояние между вершинами на нулевом шаге итерации), номер итерации K=1. Назначаем a текущей вершиной и отмечаем ёё.

Шаг 2: Если K=p, идем на ШАГ 5. (р- количество вершин).

Шаг 3: Пусть U – текущая вершина. Пересчитываем расстояние до всех неотмеченных вершин, смежных с текущей:

Шаг 4: . Если , то идем на ШАГ 5, т.к. путей больше нет. Иначе назначаем U расстоянием до которой , текущей вершиной . Отмечаем вершину U. Полагаем K=K+1. Возвращаемся на ШАГ 2.

Шаг 5: Восстанавливаем пути. Конец.

48. Теорема о шести эквивалентных утверждениях о дереве.

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

Рассмотрим граф

Теорема о шести эквивалентных утверждениях о дереве.

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

1) граф G - дерево, т.е. связный граф без циклов;

2) любые две вершины графа G соединены единственной простой цепью;

3) граф G связный и любое его ребро есть мост;

4) граф G связный, и число его ребер на 1 меньше числа вершин q = p-1

5) граф G не содержит циклов, и число его ребер на 1 < числа вершин q = p-1

6) граф G не содержит циклов, но добавление к нему любого нового ребра приводит к образованию ровно одного простого цикла, проходящего через это ребро. Док-во:

1 => 2: от противного. Пусть вершины v,w соединены двумя простыми цепями . Тогда в графе существует цикл . Пусть не существует цепи <v,w>, тогда граф несвязный.

2 => 3: от противного. Пусть ребро x, соединяющее вершины v и w – не мост. Тогда его удаление не приведёт к увеличению числа компонент связности, то есть в графе G – x, а значит и в G, существует простая цепь, связывающая v и w, а ребро x – вторая цепь.

3 => 4:индукция по p. База индукции: при p = 1 q = 0, утверждение верно. Пусть для всех q(G) = p(G) – 1 для всех графов G с числом вершин p(G) < p. Рассмотрим граф G с p вершинами и q рёбрами. Удалим из него произвольное ребро x, которое является мостом. Получим граф, состоящий из двух компонент связности , , удовлетворяющих индукционному предположению. Имеем:

4 => 5: от противного. Пусть граф содержит цикл . Так как граф связный, остальные p – l вершин имеют инцидентные им рёбра, связывающие их с вершинами, входящими в цикл. Следовательно, число рёбер в графе , что противоречит условию

5 => 6: от противного. Пусть при добавлении ребра (u,v) не образует цикла, тогда в графе нет цепи <u,v>, следовательно, граф не связный. Так как он не содержит циклов, его компоненты связности являются деревьями. Пусть в графе k компонент связности с числом рёбер и числом вершин , по доказанному для них 1 => 2 => 3 => 4

Но так как q = p – 1, получаем k = 1, граф связный, без циклов, значит, является деревом и для каждой пары вершин u,v существует единственная цель <u,v> (1 => 2). Соединив эти вершины ребром (u,v), получим единственный простой цикл. 6 => 1: от противного. Пусть G – не связный, тогда есть две несвязный вершины u,v. Тогда добавление ребра (u,v) не приведёт к образованию цикла, так как другой цепи <u,v> в графе нет.

49. Задача о соединении городов. Алгоритм Краскала

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

Несвязный граф не имеет остовных деревьев. Связный граф в общем случае имеет множество остовных деревьев. Число остовных деревьев полного графа равно .

Так как число ребер в дереве с q вершинами равно q-1, то для того, чтобы получить остов графа G, нужно удалить из него p(G)-(q(G)-1) ребер.

Определение. Циклическим рангом связного графа G называется число

p(G)-q(G)+1.

Задача о соединении городов. Рассмотрим следующую задачу. Есть несколько городов. Требуется найти множество авиарейсов с минимальной суммарной длиной, соединяющих эти города, таким образом, чтобы из любого города можно было добраться до всех остальных городов.

Определение. Нагруженным графом G(V, E) называется граф, каждому ребру которого сопоставлено некоторое число, называемое весом.

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

Алгоритм Краскала. Пусть G(V, E) – связный нагруженный граф с p вершинами.

Шаг 1. Выберем в Е ребро е₁ наименьшего веса. Пусть оно образует дерево U₁. Положим n =1.

Шаг 2. Если n = p -1, то исходным минимальным остовом является дерево U_n, конец. Иначе идем на шаг 3.

Шаг 3. Строим дерево U_n+1 , добавляя к уже построенному дереву U_n ребро e_n+1 минимального веса из не включённых в U_n ребер графа G(V, E) и не образующее цикла с ребрами из U_n. n полагаем равным n+1.

50. Эйлеровы графы. Лемма о цикле. Теорема о необходимых и достаточных условиях эйлеровости графа

Определение. Если граф имеет цикл(не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а такой граф – эйлеровым графом.

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

Лемма о цикле: Если в псевдографе G(V,E) есть хотя бы одно ребро и нет висячих вершин, то в нем существует по крайней мере один простой цикл.

Доказательство (конструктивное). Пусть в G имеется хотя бы одна петля e = (v,v), тогда простой цикл vev. Пусть в G имеются кратные рёбра , , тогда простой цикл . Пусть в G нет петель и кратных рёбер, а - смежные вершины, которые найдутся, так как в G есть ребро. Рассмотрим последовательность вершин в которой смежные, а . Поскольку в G не висячих вершин, такую последовательность можно продолжать неограниченно. Так как число вершин в графе конечно, то произойдёт совпадение , тогда - простой цикл.

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

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

Достаточность. Индукция по q. При q = 1 связный граф с чётными степенями вершин выглядит следующим образом: V = v, E = (v,v), а в таком графе есть эйлеров цикл. Пусть для достаточность доказана для всякого псевдографа с числом рёбер меньшим q. Докажем её для графа G с числом рёбер q. В силу леммы о цикле, в G существует простой цикл . Если он содержит все рёбра графа G, эйлеров цикл найден. Если нет, удалим входящие в цикл рёбра из G, получим граф . Степени вершин при этом не изменятся либо уменьшатся на два, так что граф состоит из компонент связности, которые либо являются изолированными вершинами, либо графами с чётными степенями вершин. Пусть - компоненты связности , отличные от изолированных вершин. По индуктивному предположению, в каждой из них существует эйлеров цикл в силу связности G имеющий хотя бы одну общую вершину с циклом .

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

51. Эйлеровы графы. Алгоритм Флери

Определение. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а такой граф – эйлеровым графом.

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

Дата добавления: 2015-09-27 | Просмотры: 1197 | Нарушение авторских прав