Презентация, доклад Фундаментальные циклы


Вы можете изучить и скачать доклад-презентацию на тему Фундаментальные циклы. Презентация на заданную тему содержит 52 слайдов. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
Презентации» Математика» Фундаментальные циклы
Фундаментальные циклы 
 (продолжение)Структуры данных
 Граф задаем матрицей смежности.
 Для отметки проходимых вершин используемАлгоритм обхода в глубину
 1) Берем произвольную начальную вершину, и заносимКак программно построить фундаментальные циклы?Посмотрим на состояние стека:Алгоритм генерации циклов параллельно с поиском в глубину
 Добавив в стекПросмотр стека нужно начинать с вершины, лежащей на 2 позиции нижеПрограммная реализация построения фундаментального множества цикловvoid ChkLoop()     // Проверка стека на наличиеvoid Show()  // Вывод состояния стека
 void Show()  //int main(int argc, char* argv[])
 int main(int argc, char* argv[])
 {
// Ввод числа вершин графа
   // Ввод числа вершин// Завершение...
 	  // Завершение...
 	
    Испытаем…
 Файл G.txt:
 100
 8
 1 2
 1 6
 2 3
ДвусвязностьОпределение
 Вершина A неориентированного графа называется точкой сочленения, если удаление этойЭквивалентное определение точки сочленения
 Вершина A есть точка сочленения, если вОпределение
 Неориентированный граф называется двусвязным, если он связный и не содержитДвусвязность – очень важное свойство графа. 
 Двусвязность – очень важноеИнтересное свойство блоков
 Если B1 и B2 – два разных блокаДокажем это
 Если блоки B1 и B2 имеют две или болееПолучается, что объединение блоков B1 и B2 двусвязно, что противоречит максимальностиРассмотрим случай, когда блоки B1 и B2 имеют одну общую вершинуПолучается, что блоки могут либо пересекаться по точке сочленения, либо неТеорема
 Пусть T есть стягивающее дерево графа G, построенное методом обходаДоказательство.
 Рассмотрим сначала случай V=R.
 
 Если корень имеет только одногоЭто имеет место потому, что путь между двумя различными сыновьями корняПусть теперь V<>R. Устраним V. 
 Пусть теперь V<>R. Устраним V.http://catstail.narod.ru/lec/lec-10.zip



Слайды и текст этой презентации
Слайд 1
Описание слайда:
Фундаментальные циклы (продолжение)


Слайд 2
Описание слайда:
Структуры данных Граф задаем матрицей смежности. Для отметки проходимых вершин используем массив Chk[N]. Для хранения проходимых вершин используем стек.

Слайд 3
Описание слайда:
Алгоритм обхода в глубину 1) Берем произвольную начальную вершину, и заносим ее в стек; 2) Стек пуст? Если ДА – конец; 3) Берем вершину Z из стека; 4) Если есть вершина Q, связанная с Z и не отмеченная, то возвращаем Z в стек, заносим в стек Q, печатаем ребро (Z,Q); 5) Переходим к п.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 21
Описание слайда:
Как программно построить фундаментальные циклы?

Слайд 22
Описание слайда:
Посмотрим на состояние стека:

Слайд 23
Описание слайда:
Алгоритм генерации циклов параллельно с поиском в глубину Добавив в стек очередную вершину Z, нужно пройтись по стеку от вершины к началу, проверяя (по матрице смежности) нет ли в графе ребра (Z,C). (C – вершина в стеке, расположенная ниже Z.) Если ребро есть – печатаем отрезок стека от Z до C.

Слайд 24
Описание слайда:
Просмотр стека нужно начинать с вершины, лежащей на 2 позиции ниже вершины. Просмотр стека нужно начинать с вершины, лежащей на 2 позиции ниже вершины.

Слайд 25
Описание слайда:
Программная реализация построения фундаментального множества циклов

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

Слайд 27
Описание слайда:
void ChkLoop() // Проверка стека на наличие циклов void ChkLoop() // Проверка стека на наличие циклов { int i,j,C,k; i=sPtr-1; // i указывает на верхний элемент стека if (i <= 1) return; // Если в стеке мало вершин - выход C=sArr[i]; // C – вершина, добавленная последней for (j=i-2; j >= 0; j--) // Ищем связь с одной из более глубоких // вершин if (isBound(C,sArr[j])) // Нашли – печатаем найденный цикл { cout << "Loop: "; for (k=j; k<=i; k++) cout << sArr[k] << " "; cout << endl; } }

Слайд 28
Описание слайда:
void Show() // Вывод состояния стека void Show() // Вывод состояния стека { int i; cout << "STACK: "; for (i=0; i < sPtr; i++) cout << sArr[i] << " "; cout << endl; }

Слайд 29
Описание слайда:
int main(int argc, char* argv[]) int main(int argc, char* argv[]) { int i,j,n; char fnam[200]; FILE *inp; if (argc < 2) { cout << "Enter file name: "; cin >> fnam; } else strcpy(fnam,argv[1]); if ((inp=fopen(fnam,"r")) == NULL) { cout << "Error by open..." << endl; return 0; } else { fscanf(inp,"%d",&n); // Ввод размера стека и его создание cout << "Stack size=" << n << endl; InitStack(n);

Слайд 30
Описание слайда:
// Ввод числа вершин графа // Ввод числа вершин графа fscanf(inp,"%d",&n); cout << "Number of nodes=" << n << endl; // Создание матрицы смежности InitGraph(n); while (1) // Задание ребер графа { if (fscanf(inp,"%d %d", &i, &j) == EOF) break; if ((i <= n) && (j <= n) && (i > 0) && (j > 0)) SetBound(i,j); else cout << "Bad node numbers: " << i << " " << j << endl; } // Построение стягивающего дерева и генерация циклов try { DFS(); } catch (char *error_message) { cout << error_message << endl; }

Слайд 31
Описание слайда:
// Завершение... // Завершение... fclose(inp); DestroyStack(); delete Matr; delete Chk; cin >> i; } return 0; }

Слайд 32
Описание слайда:
Испытаем… Файл G.txt: 100 8 1 2 1 6 2 3 2 4 2 5 3 5 3 8 4 5 4 7 5 8 5 6 5 7 8 7

Слайд 33
Описание слайда:
Двусвязность

Слайд 34
Описание слайда:
Определение Вершина A неориентированного графа называется точкой сочленения, если удаление этой вершины и всех инцидентных ей ребер ведет к увеличению числа компонентов связности.

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

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

Слайд 37
Описание слайда:
Эквивалентное определение точки сочленения Вершина A есть точка сочленения, если в графе существуют вершины V и U (отличные от A), такие, что любой путь из V в U проходит через A.

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

Слайд 39
Описание слайда:
Определение Неориентированный граф называется двусвязным, если он связный и не содержит точек сочленения.

Слайд 40
Описание слайда:
Двусвязность – очень важное свойство графа. Двусвязность – очень важное свойство графа. Расхожий пример: Если граф компютерной сети двусвязен, то исключение любого из узлов не развалит сеть на изолированные блоки.

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

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

Слайд 43
Описание слайда:
Интересное свойство блоков Если B1 и B2 – два разных блока графа G, то возможны только два случая: Множество вершин B1 и B2 не пересекаются; Пересечение множества вершин B1 и B2 есть точка сочленения графа G.

Слайд 44
Описание слайда:
Докажем это Если блоки B1 и B2 имеют две или более общие вершины, то граф, получающийся из B1 и B2 объединением множества вершин и ребер, будет двусвязным. Все пути между вершинами блоков B1 и B2 можно провести через одну или другую общую вершину – нет точек сочленения.

Слайд 45
Описание слайда:
Получается, что объединение блоков B1 и B2 двусвязно, что противоречит максимальности блоков B1 и B2. Получается, что объединение блоков B1 и B2 двусвязно, что противоречит максимальности блоков B1 и B2.

Слайд 46
Описание слайда:
Рассмотрим случай, когда блоки B1 и B2 имеют одну общую вершину A. Рассмотрим случай, когда блоки B1 и B2 имеют одну общую вершину A. Если эта вершина A не есть точка сочленения исходного графа G, то для двух вершин v1 (из B1) и v2 (из B2) существует путь в G, не проходящий через A. Добавим к объединению B1 и B2 ребра и вершины этого пути – получим двусвязный граф (включающий B1 и B2). Значит B1 и B2 – не максимальны.

Слайд 47
Описание слайда:
Получается, что блоки могут либо пересекаться по точке сочленения, либо не иметь общих вершин. Получается, что блоки могут либо пересекаться по точке сочленения, либо не иметь общих вершин.

Слайд 48
Описание слайда:
Теорема Пусть T есть стягивающее дерево графа G, построенное методом обхода в глубину и R – корень дерева T. Вершина V есть точка сочленения графа G в одном из двух случаев:  V=R и R имеет по крайней мере двух сыновей в T.  V <>R и существует сын W вершины V, такой, что ни W ни один из его потомков не связаны ребром с предками V.

Слайд 49
Описание слайда:
Доказательство. Рассмотрим сначала случай V=R. Если корень имеет только одного сына, то устранение корня не увеличит число компонент связности. А если сыновей больше одного, то при устранении корня, они окажутся в разных компонентах связности.

Слайд 50
Описание слайда:
Это имеет место потому, что путь между двумя различными сыновьями корня проходит через корень. Это имеет место потому, что путь между двумя различными сыновьями корня проходит через корень. Если бы это было не так, то между двумя сыновьями корня существовал бы путь, содержащий хорду (U,S), где ни U не было бы потомком S, ни S не было бы потомком U

Слайд 51
Описание слайда:
Пусть теперь V<>R. Устраним V. Пусть теперь V<>R. Устраним V. Если после устранения существует путь от W (потомка V) до корня R, то этот путь должен содержать ребро, соединяющее W (или его потомка) с предком V

Слайд 52
Описание слайда:
http://catstail.narod.ru/lec/lec-10.zip


Скачать презентацию на тему Фундаментальные циклы можно ниже:

Похожие презентации