Фундаментальные циклы - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 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 = 0; j--) // Ищем связь с одной из более глубоких // вершин if (isBound(C,sArr[j])) // Нашли – печатаем найденный цикл { cout

Слайд 28

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

void Show() // Вывод состояния стека void Show() // Вывод состояния стека { int i; cout

Слайд 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 > fnam; } else strcpy(fnam,argv[1]); if ((inp=fopen(fnam,"r")) == NULL) { cout

Слайд 30

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

// Ввод числа вершин графа // Ввод числа вершин графа fscanf(inp,"%d",&n); cout

Слайд 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

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

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