Презентация Алгоритмы на графах Графы. Основные определения онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Алгоритмы на графах Графы. Основные определения абсолютно бесплатно. Урок-презентация на эту тему содержит всего 52 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:52 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.20 MB
- Просмотров:348
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№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 :
F1(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 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 <= n ; i++) Wi = i;
// Все деревья – изолированные вершины
while (cin >> p>> q)
{
Найти такие i и j , что pWi и qWj ;
if (i == j) ничего
else {
cout << p <<‘ ‘<< q<< endl;
Объединить Wi и Wj
}
}
№36 слайд
Содержание слайда: Пример работы алгоритма
№37 слайд
Содержание слайда: Тот же граф
При другом порядке предъявления ребер:
{1,2,4} {3,6} {5,7,8,9}
№38 слайд
Содержание слайда: Реализация:
быстрый поиск – медленное объединение
for (i = 1; i <= n; i++) w[i] = i; // w[i] – метка дерева
while (cin >> p>> q)
{
i = w[p]; j = w[q];
if (i != j)
{ cout << p <<‘ ‘<< q<< endl;
w[p] = j;
for (k = 1; k <= n; k++)
if (w[k] == i) w[k] = j;
}
}
№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 << "+ребро: " << p << " " << q << endl;
}
№40 слайд
Содержание слайда: Реализация:
быстрый поиск – медленное объединение
1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9
№41 слайд
Содержание слайда: Пример
№42 слайд
Содержание слайда: Пример (конец)
№43 слайд
Содержание слайда: 1 2
1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9
№44 слайд
Содержание слайда: Реализация:
не очень быстрый поиск – быстрое объединение
№45 слайд
Содержание слайда: Реализация:
не очень быстрый поиск – быстрое объединение
№46 слайд
Содержание слайда: Пример
№47 слайд
Содержание слайда: 1 2
1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9
№48 слайд
Содержание слайда: 1 2
1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9
№49 слайд
Содержание слайда:
№50 слайд
Содержание слайда: Граф G = (V, E). Матрица весов W[v, u].
Граф G = (V, E). Матрица весов W[v, u].
Пусть T = (V, F) – остов графа.
Вес остова определяется как
№51 слайд
Содержание слайда: Продолжение задачи «Построение МОД»
на следующей лекции
№52 слайд
Содержание слайда: КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
Скачать все slide презентации Алгоритмы на графах Графы. Основные определения одним архивом:
