Презентация Алгоритмы на графах Графы. Основные определения онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Алгоритмы на графах Графы. Основные определения абсолютно бесплатно. Урок-презентация на эту тему содержит всего 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
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![. Графы. Основные определения](/documents_5/e2fd81038c5badb901d3a353536d180b/img1.jpg)
Содержание слайда: 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
№5 слайд
![Степень вершины d v число](/documents_5/e2fd81038c5badb901d3a353536d180b/img4.jpg)
Содержание слайда: Степень вершины d(v) – число инцидентных ей ребер (дуг).
Степень вершины d(v) – число инцидентных ей ребер (дуг).
Для орграфа:
dout(v) - полустепень исхода, din(v) - полустепень захода.
d(v) = dout(v) + din(v)
Для изолированной вершины: d(v) = 0.
Для висячей вершины: d(v) = 1.
№7 слайд
![Другое определение графа](/documents_5/e2fd81038c5badb901d3a353536d180b/img6.jpg)
Содержание слайда: Другое определение графа (орграфа)
Другое определение графа (орграфа)
Отступление. Соответствие
Графы и бинарные отношения.
Бинарное отношение: 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)}
№11 слайд
![Упорядоченный граф](/documents_5/e2fd81038c5badb901d3a353536d180b/img10.jpg)
Содержание слайда: Упорядоченный граф
Упорядоченный граф
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 слайд
![Упорядоченный граф](/documents_5/e2fd81038c5badb901d3a353536d180b/img11.jpg)
Содержание слайда: Упорядоченный граф
Упорядоченный граф
Упорядоченные графы G1 = (V1, L 1) и G2 = (V2, L 2) изоморфны (эквивалентны),
если существует биекция f: V1 V2 такая,
что (списковая структура сохраняется),
если список смежных вершин в G1 есть
L(v) = (w, …, w),
то список смежных вершин в G2 есть
L(f(v)) = (f(w), …, f(w)).
№19 слайд
![Списки смежности Списки](/documents_5/e2fd81038c5badb901d3a353536d180b/img18.jpg)
Содержание слайда: Списки смежности
Списки смежности
Реализация упорядоченного графа
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 слайд
![Списки смежности Списки](/documents_5/e2fd81038c5badb901d3a353536d180b/img19.jpg)
Содержание слайда: Списки смежности
Списки смежности
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
№29 слайд
![Дерево связный граф, не](/documents_5/e2fd81038c5badb901d3a353536d180b/img28.jpg)
Содержание слайда: Дерево – связный граф, не содержащий циклов.
Дерево – связный граф, не содержащий циклов.
Граф связный, если каждая пара различных вершин графа связана маршрутом.
Для связного графа G = (V, E) остовным деревом
(остовом, каркасом, скелетом)
является дерево T = (V, F), где F E.
В графе много остовов. Например, в полном графе число остовов nn-2.
№32 слайд
![Рассмотрим простой вариант](/documents_5/e2fd81038c5badb901d3a353536d180b/img31.jpg)
Содержание слайда: Рассмотрим простой вариант задачи связности
Предъявляется последовательность ребер графа:
i1 – j1, i2 – j2, i3 – j3,…, im – jm
Если для очередного ребра i – j оказывается, что в графе нет пути из i в j,
то ребро добавляется в результат.
Если же уже есть путь из i в j,
то ребро игнорируется.
Ясно, что так будет сформировано множество ребер остовного дерева графа (или остовного леса).
№34 слайд
![Пример Идея пусть на](/documents_5/e2fd81038c5badb901d3a353536d180b/img33.jpg)
Содержание слайда: Пример
Идея: пусть на некотором шаге сформирован остовный лес (выделены подмножества вершин – деревья остовного леса – W1, W2, …, WL).
Тогда при добавлении ребра:
либо ребро соединяет вершины одного дерева (тогда образуется цикл) и такое ребро отбрасываем,
либо ребро соединяет вершины разных деревьев Ws и Wt и тогда следует объединить Ws и Wt в одно множество.
№39 слайд
![Реализация быстрый поиск](/documents_5/e2fd81038c5badb901d3a353536d180b/img38.jpg)
Содержание слайда: Реализация:
быстрый поиск – медленное объединение
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;
}
Скачать все slide презентации Алгоритмы на графах Графы. Основные определения одним архивом:
Похожие презентации
-
Алгоритмы на графах. Определение наличия циклов в графе
-
Введение. Цели и задачи. Основные понятия и определения. Требования к базам данных. - презентация
-
Минеральные ресурсы НЕФТЬ Содержание: Определение, применение; Ресурсообеспеченность; Страны-лидеры; Основные грузопотоки не
-
Архитектурный стиль совокупность основных черт и признаков архитектуры определённого времени и места, проявляющихся в особенно
-
ВВЕДЕНИЕ В ЭКОНОМИКУ. ЭКОНОМИЧЕСКАЯ ТЕОРИЯ И ЕЕ РАЗВИТИЕ Основные вопросы: 1. Предпосылки, исходные признаки и определение эконо
-
СТРАТЕГИЯ И ЕЕ ВИДЫ Стратегия есть определение основных долгосрочных целей и задач организации, принятие курса действий и размещ
-
Определение основных черт российской модели менеджмента на примере ЗАО «Гард» Выполни
-
Синтетическая теория эволюции и концепция эволюции. Основные определения. Выполнила студентка группы ю-103 Мятлик Елена.
-
ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ ЛОГИСТИКИ ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
-
Управление международными и крупными проектами основные определения типология особенности факторы успеха