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

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Применение поиска в глубину. Нахождение в графе компонент двусвязности абсолютно бесплатно. Урок-презентация на эту тему содержит всего 31 слайд. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

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

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

31 слайд
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

544.00 kB
Просмотров:

50
Скачиваний:

0
Автор:

неизвестен

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

№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 ))) & (<x,w>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<E> st; //стек для записи ребер

№22 слайд

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

№23 слайд

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

№24 слайд

Содержание слайда: else // w - уже посещалась else // w - уже посещалась if ((NumVert[w] < NumVert[v]) && (w!=u) ) { //<v,w>-обратное ребро (хорда), включаем в стек 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 <E> st; //стек для записи ребер for (vV) numVert[v] = 0; // - пометить все вершины как необследованные iV = 0; Empty(St); for ( vV) if (numVert[v]==0) BICON (v, v); }

№26 слайд