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

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

Содержание ▲

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

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

Слайд 1

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

Графы

Слайд 2

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

Основное определение Неориентированный ГРАФ – это упорядоченная пара (V,E), где: V – множество вершин (конечное); E – множество пар вершин (множество ребер). При этом природа множества V может быть любой.

Слайд 3

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

Пример графа-1

Слайд 4

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

Пример графа-2

Слайд 5

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

Будет ли ЭТО графом?

Слайд 6

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

А ЭТО?

Слайд 7

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

А ЭТО?

Слайд 8

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

Порядок и размер графа Количество вершин называется порядком графа. Количество ребер называется размером графа.

Слайд 9

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

Некоторые термины-1 Пусть R=(a,b) – одно из ребер графа. Тогда вершины a и b называются концевыми вершинами ребра; Концевые вершины одного и того же ребра называют соседними; Два ребра называют смежными, если они имеют общую концевую вершину; Два ребра называются кратными, если множества их концевых вершин совпадают; Ребро называется петлей, если его концы совпадают.

Слайд 10

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

Некоторые термины-2 Степенью вершины V обозначается deg(V) называется количество ребер, для которых эта вершина является концевой; Вершина называется изолированной, если она не является концевой ни для одного ребра; Вершина называется листом, если она является концевой ровно для одного ребра. Для листа q очевидно deg(q)=1.

Слайд 11

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

Пример: deg(C)=4 H1,…H4 - Листья

Слайд 12

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

Еще пример: Города B и Д – изолированные вершины; Города Г и Е – листья.

Слайд 13

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

Полный граф Граф называется полным, если любые две вершины соединены ребром. Сколько ребер у полного графа порядка n?

Слайд 14

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

Давайте это докажем… Полный граф с двумя вершинами содержит одно ребро – это очевидно. Подставим n=2 в формулу n*(n-1)/2 Получим: n*(n-1)/2=1 Формула верна при n=2

Слайд 15

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

Предположение индукции Предположим, что формула верна для графа c k вершинами. Докажем, что отсюда следует справедливость формулы для графа c (k+1) вершиной.

Слайд 16

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

Добавим к полному графу с K вершинами еще одну вершину.

Слайд 17

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

Получим:

Слайд 18

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

Считаем, сколько получилось ребер… K*(K-1)/2 + K = K*(K+1)/2

Слайд 19

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

Из предположения справедливости утверждения при n=k следует справедливость утверждения при n=k+1. Из предположения справедливости утверждения при n=k следует справедливость утверждения при n=k+1. Теорема доказана.

Слайд 20

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

Примеры полных графов

Слайд 21

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

Важное уточнение Пары, задающие ребра в неориенти-рованном графе, неупорядочены (т.е. пары (a,b) и (b,a) не различают-ся)

Слайд 22

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

Ориентированный граф Если ребра графа есть множество упорядоченных пар (т.е. (a,b) ≠ (b,a)), То граф называется ориентированным (или орграфом)

Слайд 23

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

Пример орграфа

Слайд 24

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

Смешанный граф Смешанный граф – это тройка (V, E, A). V – множество вершин; E – множество неориентированных ребер; A- множество ориентированных ребер.

Слайд 25

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

Изоморфизм графов Пусть имеется два графа G1 и G2 Если имеется взаимно-однозначное соответствие F между вершинами графов G1 и G2 , такое что: если в графе G1 есть ребро (a,b), то и в графе G2 есть ребро (F(a),F(b)) если в графе G2 есть ребро (p,q), то и в графе G1 есть ребро (F-1(p),F-1(q)) то графы G1 и G2 называются изоморфными, а соответствие F – изоморфизмом.

Слайд 26

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

Уточнение Для орграфов и смешанных графов соответствие F должно сохранять ориентацию дуг.

Слайд 27

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

Необходимое условия изоморфизма При каких условиях между элементами двух конечных множеств можно установить взаимно-однозначное соответствие?

Слайд 28

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

Достаточно ли это условие? Нет, поскольку вершины могут быть соединены по-разному.

Слайд 29

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

Изоморфны ли эти графы?

Слайд 30

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

Пробуем построить соответствие F… Это – не изоморфизм: в G1 есть ребро (A,Д), а образы этих ребер в G2 не соединены.

Слайд 31

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

Другая попытка… А это изоморфизм!

Слайд 32

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

А эти графы изоморфны? Увы, нет…

Слайд 33

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

С точки зрения теории два изоморфных графа – это один и тот же объект (только, может быть, по-разному изображенный…) С точки зрения теории два изоморфных графа – это один и тот же объект (только, может быть, по-разному изображенный…)

Слайд 34

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

Пути (цепи): Путь (цепь) это последовательность вершин: a1, a2, … , an в которой соседние вершины ai и ai+1 соединены ребрами. Длина пути есть число составляющих его ребер

Слайд 35

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

Примеры путей: (А, Г, В) и (А, Б, Д) – пути. (А, Б, В) – не путь.

Слайд 36

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

Понятие пути для орграфа сохраняет силу, но нуждается в дополнении – соседние вершины в последовательности Понятие пути для орграфа сохраняет силу, но нуждается в дополнении – соседние вершины в последовательности a1, a2, … , an должны соединяться дугами.

Слайд 37

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

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

Слайд 38

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

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

Слайд 39

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

Машинное представление графов.

Слайд 40

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

Матрица смежности Занумеруем вершины графа G последовательными целыми от 1 до n; Построим квадратную таблицу n×n и заполним ее нулями; Если имеется ребро, соединяющее вершины i и j, то в позициях (i,j) и (j,i) поставим единицы; Полученная таблица называется матрицей смежности графа G.

Слайд 41

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

Пример

Слайд 42

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

Некоторые очевидные свойства матрицы смежности Если вершина изолирована, то ее строка и столбец будут полностью нулевые; Количество единиц в строке (столбце) равно степени соответствующей вершины; Для неориентированного графа матрица смежности симметрична относительно главной диагонали; Петле соответствует единица, стоящая на главной диагонали.

Слайд 43

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

Обобщение для орграфа Матрицу смежности для орграфа можно строить аналогичным образом, но, чтобы учесть порядок вершин, можно поступить так: Если дуга исходит из вершины j и входит в вершину k, то в позиции (j,k) матрицы смежности ставить 1, а в позиции (k,j) ставить -1.

Слайд 44

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

Матрица инцидентности Занумеруем вершины графа G последовательными целыми от 1 до n; Построим прямоугольную таблицу с n строками и m столбцами (столбцы соответствуют ребрам графа); Если j-е ребро имеет концевой вершиной вершину k, то в позиции (k,j) ставится единица. Во всех остальных случаях ставится нуль.

Слайд 45

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

Матрица инцидентности для орграфа Если j-я дуга исходит из вершины k, то в позиции (k,j) ставится 1; Если j-я дуга входит в вершину k, то в позиции (k,j) ставится -1. В остальных случаях в позиции (k,j) остается нуль.

Слайд 46

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

Поскольку столбцы матрицы инцидентности описывают ребра, то в каждом столбце может быть не более двух ненулевых элементов Поскольку столбцы матрицы инцидентности описывают ребра, то в каждом столбце может быть не более двух ненулевых элементов

Слайд 47

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

Пример матрицы инцидентности

Слайд 48

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

Список ребер Еще один способ представления графа – двумерный массив (список пар). Количество пар равно числу ребер (или дуг).

Слайд 49

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

Пример списка ребер

Слайд 50

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

Сравнение разных способов представления Список ребер самый компактный, а матрица инцидентности наименее компактна; Матрица инцидентности удобна при поиске циклов; Матрица смежности проще остальных в использовании.

Слайд 51

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

Обход графа Обходом графа называется перебор его вершин, такой, что каждая вершина просматривается один раз.

Слайд 52

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

Соглашение-1 Перед выполнением поиска для графа с n вершинами заведем массив Chk из n элементов и заполним его нулями. Если Chk[i] = 0, значит i-я вершина еще не просмотрена.

Слайд 53

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

Соглашение-2 Заведем структуру данных (хранилище), в котором будем запоминать вершины в процессе обхода. Интерфейс хранилища должен обеспечивать три функции: Занести вершину; Извлечь вершину; Проверить не пусто ли хранилище;

Слайд 54

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

Соглашение-3 Когда вершина j помещается в хранилище, она отмечается как просмотренная (т.е. устанавливается Chk[j]=1)

Слайд 55

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

Алгоритм обхода-1 1) Берем произвольную начальную вершину, печатаем и заносим ее в хранилище; 2) Хранилище пусто? Если ДА – конец; 3) Берем вершину Z из хранилища; 4) Если есть вершина Q, связанная с Z и не отмеченная, то возвращаем Z в хранилище, заносим в хранилище Q, печатаем Q; 5) Переходим к п.2

Слайд 56

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

Алгоритм обхода-2 1) Берем произвольную начальную вершину и заносим ее в хранилище; 2) Хранилище пусто? Если ДА – конец; 3) Берем вершину Z из хранилища, печатаем и удаляем из хранилища; 4) Помещаем в хранилище все вершины, связанные с Z и еще не отмеченные; 5) Переходим к п.2

Слайд 57

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

Какие структуры данных подходят в качестве хранилища? Стек (PUSH – занести; POP – извлечь) Очередь (ENQUE – занести; DEQUE – извлечь) Обе структуры позволяют проверить наличие данных.

Слайд 58

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

Алгоритм-1 в сочетании со стеком называется обходом в глубину Алгоритм-1 в сочетании со стеком называется обходом в глубину Алгоритм-2 в сочетании с очередью называется обходом в ширину

Слайд 59

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

Слайд 60

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

В качестве хранилища возьмем СТЕК. Используем Алгоритм-1. В качестве хранилища возьмем СТЕК. Используем Алгоритм-1. Обход начнем с вершины 1

Слайд 61

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

Первый шаг:

Слайд 62

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

Второй шаг:

Слайд 63

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

Третий шаг:

Слайд 64

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

Четвертый шаг:

Слайд 65

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

Пятый шаг:

Слайд 66

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

Шестой шаг:

Слайд 67

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

Седьмой шаг:

Слайд 68

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

Восьмой шаг:

Слайд 69

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

Далее все вершины будут вытолкнуты из стека. Далее все вершины будут вытолкнуты из стека. Получился следующий порядок обхода: 1,2,3,5,4,7,8,6

Слайд 70

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

Теперь возьмем в качестве хранилища очередь. Будем использовать Алгоритм-2. Обход снова начнем с вершины 1. Теперь возьмем в качестве хранилища очередь. Будем использовать Алгоритм-2. Обход снова начнем с вершины 1.

Слайд 71

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

Шаг первый:

Слайд 72

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

Шаг второй:

Слайд 73

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

Шаг третий:

Слайд 74

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

Шаг четвертый:

Слайд 75

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

Шаг пятый:

Слайд 76

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

Шаг шестой:

Слайд 77

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

Шаг седьмой:

Слайд 78

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

Шаг восьмой:

Слайд 79

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

Получился следующий порядок обхода: 1,2,3,4,5,7,6,8

Слайд 80

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

Замечание Оба алгоритма потребовали одинаковое число шагов. Почему?

Слайд 81

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

Поиск в глубину Перед выполнением поиска в глубину для графа с n вершинами заведем массив Chk из n элементов и заполним его нулями. Если Chk[i] = 0, значит i-я вершина еще не просмотрена.

Слайд 82

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

Алгоритм поиска в глубину с вершины p. Если Chk[p]=1 – выходим; Устанавливаем Chk[p]=1 Берем по очереди все вершины k, смежные с p; Применяем к каждой из них указанный алгоритм.

Слайд 83

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

Пример-1

Слайд 84

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

Пример-2

Слайд 85

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

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