Алгоритмы на графах Графы. Основные определения - презентация, доклад, проект скачать

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

Алгоритмы на графах Графы. Основные определения, слайд №1

Алгоритмы на графах Графы. Основные определения, слайд №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

Алгоритмы на графах Графы. Основные определения, слайд №32

Алгоритмы на графах Графы. Основные определения, слайд №33

Алгоритмы на графах Графы. Основные определения, слайд №34

Алгоритмы на графах Графы. Основные определения, слайд №35

Алгоритмы на графах Графы. Основные определения, слайд №36

Алгоритмы на графах Графы. Основные определения, слайд №37

Алгоритмы на графах Графы. Основные определения, слайд №38

Алгоритмы на графах Графы. Основные определения, слайд №39

Алгоритмы на графах Графы. Основные определения, слайд №40

Алгоритмы на графах Графы. Основные определения, слайд №41

Алгоритмы на графах Графы. Основные определения, слайд №42

Алгоритмы на графах Графы. Основные определения, слайд №43

Алгоритмы на графах Графы. Основные определения, слайд №44

Алгоритмы на графах Графы. Основные определения, слайд №45

Алгоритмы на графах Графы. Основные определения, слайд №46

Алгоритмы на графах Графы. Основные определения, слайд №47

Алгоритмы на графах Графы. Основные определения, слайд №48

Алгоритмы на графах Графы. Основные определения, слайд №49

Алгоритмы на графах Графы. Основные определения, слайд №50

Алгоритмы на графах Графы. Основные определения, слайд №51

Алгоритмы на графах Графы. Основные определения, слайд №52

Содержание ▲

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

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

Слайд 1

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

Лекция 5.2 Лекция 5.2 Алгоритмы на графах Графы. Основные определения Представление графов Минимальное остовное дерево. Задача связности графа.

Слайд 2

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

1. Графы. Основные определения V – множество вершин (конечное) E – множество ребер (конечное) G = (V, E) - граф V = n – число вершин графа E = m – число ребер графа e = {u, v} – ребро e инцидентно вершинам u и v u и v – смежные вершины; концы ребра e; инцидентны ребру e Висячая вершина (ребро). Например: v2 или {v2 , v3}. Полный граф: m = n (n – 1)/2

Слайд 3

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

Ориентированный граф или орграф Ориентированный граф или орграф E  V  V = V2 или E  { (u, v): u, v V} Узлы, дуги. (v, v)  петля. Простой орграф. Неориентированный граф – специальный случай орграфа, в котором ( u, v  V: ((u, v)  E)  ((v, u)  E ))

Слайд 4

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

Слайд 5

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

Степень вершины d(v) – число инцидентных ей ребер (дуг). Степень вершины d(v) – число инцидентных ей ребер (дуг). Для орграфа: dout(v) - полустепень исхода, din(v) - полустепень захода. d(v) = dout(v) + din(v) Для изолированной вершины: d(v) = 0. Для висячей вершины: d(v) = 1.

Слайд 6

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

Слайд 7

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

Другое определение графа (орграфа) Другое определение графа (орграфа) Отступление. Соответствие Графы и бинарные отношения. Бинарное отношение: R  A  B. Вместо (a, b)  R пишут aRb. При A = B , говорят, что R – отношение на A. Про бинарное отношение R  A  B часто говорят как про соответствие с областью отправления A и областью прибытия B или соответствие на A  B. Записывают, как F: A  B и b = F(a). Полный образ элемента x  A : F(x) = {y  B : y = F(x)} Полный прообраз элемента y  B : F1(y) = {x  A : y = F(x)}

Слайд 8

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

Слайд 9

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

Другое определение графа (орграфа) Другое определение графа (орграфа) G = (V, )  граф, где   соответствие : V  V. ( отображение : V  2V). (v) = {v, …, v} – полный образ элемента v. Например, для графов

Слайд 10

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

1  обратное соответствие. 1  обратное соответствие. 1 (v) = {v, …, v} – полный прообраз элемента v. Например, для тех же графов

Слайд 11

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

Упорядоченный граф Упорядоченный граф G = (V, L)  упорядоченный граф, где L – множество упорядоченных списков вершин L = {L(v1), L(v2), …, L(vn)} и L(v) = (v, …, v) – упорядоченный список вершин, смежных с v, т.е. упорядоченный полный образ v. При этом должны выполняться условия А) v  L(v) для любого v  V, Б) w  L(v)  v  L(w) Упорядоченный граф определяет единственный неупорядоченный граф. Обратное неверно, поскольку возможно много способов упорядочения графа.

Слайд 12

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

Упорядоченный граф Упорядоченный граф Упорядоченные графы G1 = (V1, L 1) и G2 = (V2, L 2) изоморфны (эквивалентны), если существует биекция f: V1  V2 такая, что (списковая структура сохраняется), если список смежных вершин в G1 есть L(v) = (w, …, w), то список смежных вершин в G2 есть L(f(v)) = (f(w), …, f(w)).

Слайд 13

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

Упорядоченный граф Упорядоченный граф

Слайд 14

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

Матрица инциденций (n  m) Матрица инциденций (n  m) n строк (по вершинам) m столбцов (по ребрам) Для орграфа: столбец для дуги (u, v) в строке, соответствующей вершине u, имеет 1, а в строке, соответствующей вершине v, имеет 1.

Слайд 15

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

Матрица инциденций для графов (неориентриованных) Матрица инциденций для графов (неориентриованных)

Слайд 16

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

A[u, v] = 1, если u  v или u  v, иначе A[u, v] = 0. A[u, v] = 1, если u  v или u  v, иначе A[u, v] = 0. Для неориентированного графа матрица смежности симметрична.

Слайд 17

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

Для неориентированного графа Для неориентированного графа

Слайд 18

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

Списки смежности Adj[1..n] – массив списков (adjacent – смежный, соседний) Adj[v] – список вершин, смежных с v.

Слайд 19

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

Списки смежности Списки смежности Реализация упорядоченного графа Adj[1..n] – массив списков (adjacent – смежный, соседний) Adj[v] – список вершин, смежных с v. for u Adj[v] do S(u)  begin p := Adj[v].head; while p  nil do begin u := p^.vert; S(u); p := p^.next end end Память – (n + 2m)

Слайд 20

$Списки смежности Списки смежности for u Adj [v] do S(u)  begin L := Adj [v].head; {L: L1_List **} GoBOL(L); {Встать в начало списка} while not...$

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

Списки смежности Списки смежности for u Adj [v] do S(u)  begin L := Adj [v].head; {L: L1_List **} GoBOL(L); {Встать в начало списка} while not EOList(L) do begin GetEl(L,u); {получить текущий элемент u списка L} S(u); GoNext(L) {перейти к следующему элементу списка} end {while} end ** - см. Учеб. пособие «Динамические СД», 2004

Слайд 21

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

Задание: Задание: Написать код преобразования одного представления графа (орграфа) в другое. Виды представления: матрица инциденций; матрица смежности; списки смежности.

Слайд 22

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

Различные изображения графа. Пример 1.

Слайд 23

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

Различные изображения графа. Пример 2.

Слайд 24

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

Пример 2.

Слайд 25

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

Множества вершин и ребер

Слайд 26

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

Множества смежности

Слайд 27

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

Списки смежности

Слайд 28

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

Конец вводной части

Слайд 29

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

Дерево – связный граф, не содержащий циклов. Дерево – связный граф, не содержащий циклов. Граф связный, если каждая пара различных вершин графа связана маршрутом. Для связного графа G = (V, E) остовным деревом (остовом, каркасом, скелетом) является дерево T = (V, F), где F E. В графе много остовов. Например, в полном графе число остовов nn-2.

Слайд 30

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

Остовные деревья (леса) Пример. Задача «связности» (Седжвик). Задан граф. Пусть номера вершин графа есть 1, 2, 3, …, n Дана пара {i,j}. Требуется определить, связаны ли вершины i и j путем в графе.

Слайд 31

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

Пример: решетчатый граф

Слайд 32

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

Рассмотрим простой вариант задачи связности Предъявляется последовательность ребер графа: i1 – j1, i2 – j2, i3 – j3,…, im – jm Если для очередного ребра i – j оказывается, что в графе нет пути из i в j, то ребро добавляется в результат. Если же уже есть путь из i в j, то ребро игнорируется. Ясно, что так будет сформировано множество ребер остовного дерева графа (или остовного леса).

Слайд 33

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

Пример графа (n = 9; m = 14)

Слайд 34

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

Пример Идея: пусть на некотором шаге сформирован остовный лес (выделены подмножества вершин – деревья остовного леса – W1, W2, …, WL). Тогда при добавлении ребра: либо ребро соединяет вершины одного дерева (тогда образуется цикл) и такое ребро отбрасываем, либо ребро соединяет вершины разных деревьев Ws и Wt и тогда следует объединить Ws и Wt в одно множество.

Слайд 35

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

Алгоритм for (i = 1; i > p>> q) { Найти такие i и j , что pWi и qWj ; if (i == j) ничего else { cout

Слайд 36

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

Пример работы алгоритма

Слайд 37

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

Тот же граф При другом порядке предъявления ребер: {1,2,4} {3,6} {5,7,8,9}

Слайд 38

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

Реализация: быстрый поиск – медленное объединение for (i = 1; i > p>> q) { i = w[p]; j = w[q]; if (i != j) { cout

Слайд 39

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

Реализация: быстрый поиск – медленное объединение int i, j, k, p, q, w[N]; for (i = 0; i < N; i++) w[i] = i; // w[i] – метка дерева while (fin >> p >> q){ i = w[p]; j = w[q]; if (i == j) continue; for (k = 0; k < N; k++) if (w[k] == i) w[k] = j; cout