Графы

Август 11, 2022

Содержание

2. Графы Граф – это совокупность двух конечных множеств: множества точек и множества линий, попарно соединяющих некоторые
3. Множество точек называется вершинами (узлами) графа. Множество линий, соединяющих вершины графа, называются ребрами (дугами) графа. Графы
4. Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрам которого присвоено направление. Графы
5. Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е. ребрам которого не задано направление.
6. Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра. Графы 5
7. Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются смежными, если существует соединяющее их
8. Маршрутом в графе называется конечная чередующаяся последовательность смежных вершин и ребер, соединяющих эти вершины. Маршрут называется
9. Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины
10. Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость,
11. Взвешенный граф 10
12. Задача Пять человек обменялись рукопожатиями. Сколько было рукопожатий? 1. Каждый из 5 человек пожал руки своим
14. Задача Колледж. Фойе. Началась первая пара. Обменялись рукопожатиями несколько человек. Всего рукопожатий было 36. Сколько учащихся
15. Способы представления графов Выбор структуры данных для хранения графа в памяти компьютера имеет принципиальное значение при
16. Пусть задан граф, у которого количество вершин равно n, а количество ребер – m. Каждое ребро
17. 1. Список ребер – это множество, образованное парами смежных вершин. Для его хранения обычно используют одномерный
18. Способы представления графов. Список рёбер 14
19. 2. Матрица смежности – это двумерный массив размерности n x n, значения элементов которого характеризуются смежностью
20. Способы представления графов. Матрица смежности 16
21. 3. Матрица инцидентности – это двумерный массив размерности NxM, в котором указываются связи между инцидентными элементами
22. Способы представления графов. Матрица инцидентности 18
23. У большинства людей друзей меньше, чем в среднем у их друзей. Несмотря на видимую парадоксальность утверждения,
24. Обходы в графе Обходом графов (поиском на графах) - это процесс систематического просмотра всех ребер или
25. К стандартным и наиболее распространенным методам относятся: поиск в глубину (Depth First Search, DFS); поиск в
26. Алгоритм поиска в глубину Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина
27. Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные.
28. Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная
29. Поиск кратчайших путей в графе Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и
30. Алгоритм Дейкстры Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине
32. Скачать презентацию

Слайд 2

Графы
Граф – это совокупность двух конечных множеств: множества точек и множества

линий, попарно соединяющих некоторые из этих точек.

Слайд 3

Множество точек называется вершинами (узлами) графа.
Множество линий, соединяющих вершины графа, называются

ребрами (дугами) графа.

Графы

Слайд 4

Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е.

ребрам которого присвоено направление.

Графы

Слайд 5

Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е.

ребрам которого не задано направление.

Графы

Слайд 6

Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра.
Графы
5

Слайд 7

Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются

смежными, если существует соединяющее их ребро. Ребра, соединяющие одну и ту же пару вершин, называются кратными.
Простой граф – это граф, в котором нет ни петель, ни кратных ребер.
Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

Графы

Слайд 8

Маршрутом в графе называется конечная чередующаяся последовательность смежных вершин и ребер,

соединяющих эти вершины.
Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Графы

Слайд 9

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется

путем, если все ее вершины различны.
Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.
Граф называется связным, если для любой пары вершин существует соединяющий их путь.

Графы

Слайд 10

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие

данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).
Вес (длина) ребра – число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность и т. д.
Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

Графы

Слайд 11

Взвешенный граф
10

Слайд 12

Задача
Пять человек обменялись рукопожатиями. Сколько было рукопожатий?
1. Каждый из 5

человек пожал руки своим коллегам. Однако произведение 5 * 4 = 20 дает удвоенное число рукопожатий (так как в этом расчете учтено, что первый пожал руку второму, а затем второй первому, на самом же деле было одно рукопожатие). Итак, число рукопожатий равно: (5 * 4) : 2 = 10.

Слайд 13

Слайд 14

Задача
Колледж. Фойе. Началась первая пара. Обменялись рукопожатиями несколько человек. Всего рукопожатий

было 36. Сколько учащихся опоздало на первую пару.

Слайд 15

Способы представления графов
Выбор структуры данных для хранения графа в памяти компьютера

имеет принципиальное значение при разработке эффективных алгоритмов.

Слайд 16

Пусть задан граф, у которого количество вершин равно n, а количество

ребер – m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

Способы представления графов

Слайд 17

1. Список ребер – это множество, образованное парами смежных вершин. Для

его хранения обычно используют одномерный массив размером m, содержащий список пар вершин, смежных с одним ребром графа.

Способы представления графов. Список рёбер

Слайд 18

Способы представления графов. Список рёбер
14

Слайд 19

2. Матрица смежности – это двумерный массив размерности n x n,

значения элементов которого характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество ребер, которые соединяют соответствующие вершины.

Способы представления графов. Матрица смежности

Слайд 20

Способы представления графов. Матрица смежности
16

Слайд 21

3. Матрица инцидентности – это двумерный массив размерности
NxM, в котором указываются

связи между инцидентными элементами графа (ребро и вершина). Столбцы матрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром. Данный способ является самым емким для хранения и облегчает нахождение циклов в графе.

Способы представления графов. Матрица инцидентности

Слайд 22

Способы представления графов. Матрица инцидентности
18

Слайд 23

У большинства людей друзей меньше, чем в среднем у их друзей.
Несмотря на видимую парадоксальность утверждения, оно

вполне математически логично и выводится из базовых принципов теории графов. В 2012 году это утверждение подтвердили исследователями Корнеллского университета, которые проанализировали721 миллион пользователей Facebook. Читать полностью: https://42.tut.by/576746
https://www.economist.com/blogs/economist-explains/2013/04/economist-explains-why-friends-more-popular-paradox

Слайд 24

Обходы в графе
Обходом графов (поиском на графах) - это процесс систематического

просмотра всех ребер или вершин графа с целью поиска ребер или вершин, удовлетворяющих некоторому условию.

Слайд 25

К стандартным и наиболее распространенным методам относятся:
поиск в глубину (Depth First

Search, DFS);
поиск в ширину (Breadth First Search, BFS).
*Эти методы чаще всего рассматриваются на ориентированных графах, но они применимы и для неориентированных, ребра которых считаются двунаправленными.

Слайд 26

Алгоритм поиска в глубину
Шаг 1. Всем вершинам графа присваивается значение не

посещенная. Выбирается первая вершина и помечается как посещенная.
Шаг 2. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина.

Слайд 27

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины

не будут помечены как посещенные.

Алгоритм поиска в глубину

Слайд 28

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая

вершина и помечается как посещенная (и заносится в очередь).
Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.
Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста

Алгоритм поиска в ширину

Слайд 29

Поиск кратчайших путей в графе
Нахождение кратчайшего пути на сегодняшний день является

жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.

Слайд 30

Алгоритм Дейкстры
Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный

бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.

Графы

Содержание

ГрафыГраф – это совокупность двух конечных множеств: множества точек и множества

Множество точек называется вершинами (узлами) графа.Множество линий, соединяющих вершины графа, называются

Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е.

Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е.

Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра.Графы5

Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются

Маршрутом в графе называется конечная чередующаяся последовательность смежных вершин и ребер,

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие

Взвешенный граф10

ЗадачаПять человек обменялись рукопожатиями. Сколько было рукопожатий? 1. Каждый из 5

ЗадачаКолледж. Фойе. Началась первая пара. Обменялись рукопожатиями несколько человек. Всего рукопожатий

Способы представления графовВыбор структуры данных для хранения графа в памяти компьютера

Пусть задан граф, у которого количество вершин равно n, а количество

1. Список ребер – это множество, образованное парами смежных вершин. Для

Способы представления графов. Список рёбер 14

2. Матрица смежности – это двумерный массив размерности n x n,

Способы представления графов. Матрица смежности16

3. Матрица инцидентности – это двумерный массив размерностиNxM, в котором указываются

Способы представления графов. Матрица инцидентности 18

У большинства людей друзей меньше, чем в среднем у их друзей.Несмотря на видимую парадоксальность утверждения, оно

Обходы в графе Обходом графов (поиском на графах) - это процесс систематического

К стандартным и наиболее распространенным методам относятся:поиск в глубину (Depth First

Алгоритм поиска в глубинуШаг 1. Всем вершинам графа присваивается значение не

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая

Поиск кратчайших путей в графе Нахождение кратчайшего пути на сегодняшний день является

Алгоритм ДейкстрыШаг 1. Всем вершинам, за исключением первой, присваивается вес равный

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

Графы
Граф – это совокупность двух конечных множеств: множества точек и множества

Множество точек называется вершинами (узлами) графа.
Множество линий, соединяющих вершины графа, называются

Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра.
Графы
5

Взвешенный граф
10

Задача
Пять человек обменялись рукопожатиями. Сколько было рукопожатий?
1. Каждый из 5

Задача
Колледж. Фойе. Началась первая пара. Обменялись рукопожатиями несколько человек. Всего рукопожатий

Способы представления графов
Выбор структуры данных для хранения графа в памяти компьютера

Способы представления графов. Список рёбер
14

Способы представления графов. Матрица смежности
16

3. Матрица инцидентности – это двумерный массив размерности
NxM, в котором указываются

Способы представления графов. Матрица инцидентности
18

У большинства людей друзей меньше, чем в среднем у их друзей.
Несмотря на видимую парадоксальность утверждения, оно

Обходы в графе
Обходом графов (поиском на графах) - это процесс систематического

К стандартным и наиболее распространенным методам относятся:
поиск в глубину (Depth First

Алгоритм поиска в глубину
Шаг 1. Всем вершинам графа присваивается значение не

Поиск кратчайших путей в графе
Нахождение кратчайшего пути на сегодняшний день является

Алгоритм Дейкстры
Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный