Применение поиска в глубину. Нахождение в графе компонент двусвязности

Нажмите для полного просмотра!

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №2

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №3

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №4

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №5

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №6

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №7

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №8

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №9

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №10

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №11

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №12

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №13

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №14

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №15

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №16

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №17

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №18

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №19

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №20

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №21

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №22

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №23

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №24

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №25

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №26

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №27

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №28

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №29

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №30

Применение поиска в глубину. Нахождение в графе компонент двусвязности, слайд №31

Содержание ▲

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

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Построение и анализ алгоритмов Лекция 10.1 Раздел: Алгоритмы на графах Тема лекции: Применение поиска в глубину. Нахождение в графе компонент двусвязности

Слайд 2

Описание слайда:

Нахождение компонент двусвязности графа (biconnected components)

Слайд 3

Описание слайда:

Точки сочленения и двусвязные компоненты

Слайд 4

Описание слайда:

Точки сочленения и двусвязные компоненты Равнозначное утверждение: Точка сочленения – такая вершина a  V, что существуют вершины графа v и u , отличные от a, такие, что каждый путь* из v в u проходит через вершину a. * предполагаем, что хотя бы один такой путь существует, т.к. рассматривается связный граф или связная компонента

Слайд 5

Описание слайда:

Граф G – двусвязный (неразделимый), если он связный и не содержит точек сочленения. Граф G – двусвязный (неразделимый), если он связный и не содержит точек сочленения. Компонента двусвязности (или блок) графа G – максимальный* двусвязный подграф графа G. * Максимальный по включению, т.е. не входящий ни в какой другой двусвязный подграф.

Слайд 6

Описание слайда:

Тривиальный алгоритм: перебираем все вершины - идентифицируем точки сочленения, определяя количество компонент связности, и выделяем блоки. Сложность O (m*n). Тривиальный алгоритм: перебираем все вершины - идентифицируем точки сочленения, определяя количество компонент связности, и выделяем блоки. Сложность O (m*n). Алгоритм на базе поиска в глубину

Слайд 7

Описание слайда:

В основе – Свойство DFS-остова (глубинного остовного дерева) [см.лекцию 8.1, сл.25-26] Пусть (V, T) – DFS-остов графа G = (V, E) и пусть {u, v}E. Тогда либо u потомок v (в дереве), либо v потомок u.

Слайд 8

Описание слайда:

Свойство TDFS-остова (глубинного остовного дерева) Иллюстрация к доказательству: {u,v}  E v посещена раньше, чем u numVert[v] < numVert[u] r – корень TDFS

Слайд 9

Описание слайда:

Замечание По схеме AB, not B  not A.

Слайд 10

Описание слайда:

Теорема: Пусть D = (V, T) – глубинное остовное дерево связного графа G = (V, E) с корнем дерева r. Теорема: Пусть D = (V, T) – глубинное остовное дерево связного графа G = (V, E) с корнем дерева r. Вершина a V является точкой сочленения графа G ттогда, когда выполнено одно из условий: a = r и a имеет более одного сына в D (хотя бы двух); a  r и существует s = сын (a) , такой что НЕТ обратных ребер, идущих от потомков вершины s (в том числе самой s) к предкам вершины a.

Слайд 11

Описание слайда:

Примеры - 1

Слайд 12

Описание слайда:

Примеры - 2

Слайд 13

Описание слайда:

Примеры - 3

Слайд 14

Описание слайда:

Доказательство: 2) a  r и условие 2 выполнено. Доказательство: 2) a  r и условие 2 выполнено.

Слайд 15

Описание слайда:

… либо есть обратное ребро. Покажем, что это противоречит тому, что a – точка сочленения. Далее – два случая. … либо есть обратное ребро. Покажем, что это противоречит тому, что a – точка сочленения. Далее – два случая.

Слайд 16

Описание слайда:

Тогда опять либо нет обратного ребра v  w и тогда условие выполнено, либо есть v  w, но тогда существует путь между x и y , проходящий не через a (см. рисунок), что противоречит предположению, что a – точка сочленения. Тогда опять либо нет обратного ребра v  w и тогда условие выполнено, либо есть v  w, но тогда существует путь между x и y , проходящий не через a (см. рисунок), что противоречит предположению, что a – точка сочленения. Конец доказательства.

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

Для каждой вершины vV определим множество P(v) Для каждой вершины vV определим множество P(v) P(v) = {v} U { w : (w = предок(v)) & ( xV: ((x = v)  (x=потомок(v ))) & (B))}, где B - множество обратных ребер (хорд). Иными словами P (v) состоит из v и всех предков v, которых можно достичь из v , проходя сначала несколько (возможно, ни одной) дуг дерева T, а затем одно обратное ребро. Введем функцию Low(v) = Min { NumVert(x)  x  P (v) }.

Слайд 19

Описание слайда:

Low(s)  NumVert(a) Low(s)  NumVert(a) Иными словами - если обратных ребер, которые ведут от потомков некоторого сына в вершины, ранее посещенные при DFS, не существует, то это и есть точка сочленения.

Слайд 20

Описание слайда:

Опять тот же «Пример 1»

Слайд 21

Описание слайда:

Нахождение компонент двусвязности графа (BiConnection) (на основе поиска в глубину) BICON (vert v, vert u) { // посещаем вершину v и т.д.; u=Отец(v) global int numVert [n]; listVert Adj [n] ; // списки смежности int iV; /*текущий порядковый номер посещения вершины*/ int Low [n] ; stack st; //стек для записи ребер

Слайд 22

Описание слайда:

Тело процедуры BICON iV++; //посетить v: numVert[v] = iV; Low[v] = numVert[v]; for ( w  Adj[v] ) if (NumVert[w]==0) { // - ребро (ветвь) остовного дерева: …

Слайд 23

Описание слайда:

Продолжение (тело основного цикла) if (NumVert[w]==0) {// - ребро (ветвь) остовного дерева st  {v,w}; BICON ( w, v); Low[v] := min (Low[v],Low[w]); //здесь Low[w] окончательное if (Low[w] >= NumVert[v] ) { /* v - либо корень, либо точка сочленения, а в стеке сверху до включительно - ребра компоненты двувязности; выписать (зафиксировать) их */ do { e  st; cout

Слайд 24

Описание слайда:

else // w - уже посещалась else // w - уже посещалась if ((NumVert[w] < NumVert[v]) && (w!=u) ) { //-обратное ребро (хорда), включаем в стек st  {v,w}; Low[v] = min ( Low[v], numVert[w] ); }//if //od for, v - использована } //BICON

Слайд 25

Описание слайда:

{ … { … SetVert V; //множество вершин графа G=(V,E), Card(V)=n int numVert [n] ; listVert adj[n]; //списки смежности int iV; //текущий порядковый номер посещения вершины int Low[n]; stack st; //стек для записи ребер for (vV) numVert[v] = 0; // - пометить все вершины как необследованные iV = 0; Empty(St); for ( vV) if (numVert[v]==0) BICON (v, v); }