Теория графов

Содержание

Слайд 2

Теория графов Графом называется множество узлов и связей между ними. Каждый

Теория графов

Графом называется множество узлов и связей между ними.
Каждый узел называется

вершиной, а каждая связь ребром.
Каждое ребро соединяет только две вершины.
Слайд 3

Пример графа

Пример графа

Слайд 4

Классификация графов Графы делятся на ориентированные и неориентированные. Ориентированный граф –

Классификация графов

Графы делятся на ориентированные и неориентированные.
Ориентированный граф – такой

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

Пример ориентированного графа

Пример ориентированного графа

Слайд 6

Пример неориентированного графа

Пример неориентированного графа

Слайд 7

Пример смешанного графа

Пример смешанного графа

Слайд 8

Классификация графов Графы также делятся на взвешенные и невзвешенные. Граф, в

Классификация графов

Графы также делятся на взвешенные и невзвешенные.
Граф, в котором каждому

ребру в соответствие поставлено некоторое числовое значение – вес, называется взвешенным графом.
Если никакого числового значения рёбрам не поставлено, то граф называется невзвешенным.
До этого мы рассматривали только невзвешенные графы
В названии графа указывают его ориентированность/неориентированность и взвешенность/невзвешенность
Слайд 9

Взвешенный неориентированный граф

Взвешенный неориентированный граф

Слайд 10

Классификация графов Граф, в котором между любой парой вершин существует, как

Классификация графов

Граф, в котором между любой парой вершин существует, как минимум,

один путь, называется связным
Если в графе существует хотя бы одна вершина, не связанная с другими, он называется несвязным.
- Зачастую в названии графа связность/несвязность опускается.
Слайд 11

Взвешенный связанный ориентированный граф

Взвешенный связанный ориентированный граф

Слайд 12

Невзвешенный несвязанный неориентированный граф

Невзвешенный несвязанный неориентированный граф

Слайд 13

Классификация графов Граф, в котором число рёбер близко к максимальному (когда

Классификация графов
Граф, в котором число рёбер близко к максимальному (когда каждая

вершина графа связана с любой другой вершиной графа рёбрами), называется плотным графом.
Граф с противоположным свойством, имеющий малое число рёбер, называется разреженным графом.
- Любой связный граф является плотным, но не каждый плотный является связным
Слайд 14

Плотный граф

Плотный граф

Слайд 15

Петля Петлёй называется ребро, которое соединяет вершины v1 и v2, причём

Петля
Петлёй называется ребро, которое соединяет вершины v1 и v2, причём v1 и

v2 совпадают. Иными словами, петля – это ребро, которое начинается и заканчивается в одной вершине.
Слайд 16

Граф с петлей

Граф с петлей

Слайд 17

Инцидентность Инцидентность – понятие, используемое только в отношении ребра и вершины.

Инцидентность
Инцидентность – понятие, используемое только в отношении ребра и вершины. Если v1,

v2 - вершины, а R = (v1, v2) - соединяющее их ребро, тогда вершина v1 и ребро R инцидентны, вершина v2 и ребро R тоже инцидентны.
Две вершины (или два ребра) инцидентными быть не могут.
Слайд 18

Инцидентность Вершина V1 – инцидентна ребру R Вершина V2 – инцидентна ребру R

Инцидентность

Вершина V1 – инцидентна ребру R
Вершина V2 – инцидентна ребру R

Слайд 19

Смежность Смежность – понятие, используемое в отношении только двух рёбер, либо

Смежность
Смежность – понятие, используемое в отношении только двух рёбер, либо только

двух вершин: два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Слайд 20

Смежность Ребра R1 и R2 – смежные т.к инцидентны одной вершине

Смежность

Ребра R1 и R2 – смежные т.к инцидентны одной вершине

V2
Вершины V1 и V2 смежные т.к инцидентны одному ребру R1
Вершины V2 и V3 смежные т.к. инцидентны одному ребру R2
Слайд 21

Маршрут

Маршрут

 

Слайд 22

Открытый маршрут 2-4-1-2-3-4-1

Открытый маршрут

2-4-1-2-3-4-1

Слайд 23

Замкнутый маршрут 2-3-5-4-3-2

Замкнутый маршрут

2-3-5-4-3-2

Слайд 24

Цепь Цепь – маршрут, в котором любое ребро графа входит не

Цепь

Цепь – маршрут, в котором любое ребро графа входит не более одного раза.

Если все вершины такого маршрута не повторяются, то цепь называется открытой (рисунок 10).
 Циклом называется цепь в которой начальная и конечная точки маршрута являются одной вершиной. На рисунке 11 вершина 2 является началом и концом циклического маршрута.
Слайд 25

Открытая цепь 2-5-1-2-4

Открытая цепь

2-5-1-2-4

Слайд 26

Замкнутая цепь 2-4-1-2-3-5-2

Замкнутая цепь

2-4-1-2-3-5-2

Слайд 27

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

Представление графов. Матрица смежности.

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

виде квадратной матрицы, в которой каждый элемент принимает одно из двух значений: 0 или 1 для невзвешенного графа. Значения 1 и 0 отображают существование ребра между вершинами, которые характеризуются номерами строк и столбцов.
Если граф взвешенный, то элементами матрицы смежности будут числа, соответствующие весам ребер, соединяющих вершины, на пересечении которых в таблице стоит элемент.
Слайд 28

Невзвешенный неориентированный граф

Невзвешенный неориентированный граф

Слайд 29

Матрица смежности

Матрица смежности

Слайд 30

Невзвешенный ориентированный граф

Невзвешенный ориентированный граф

Слайд 31

Матрица смежности

Матрица смежности

Слайд 32

Взвешенный неориентированный граф

Взвешенный неориентированный граф

Слайд 33

Матрица смежности

Матрица смежности

Слайд 34

вектор смежности Граф может быть представлен с помощью вектора смежности. В

вектор смежности

Граф может быть представлен с помощью вектора смежности. В векторе смежности

для каждой вершины хранятся номера смежных с ней вершин.
Слайд 35

Матрица инцидентности Еще одной формой представления графа является матрица инцидентности, в

Матрица инцидентности

Еще одной формой представления графа является матрица инцидентности, в которой указываются

связи между инцидентными элементами графа. Столбцы матрицы соответствуют ребрам, строки – вершинам.
В каждом элементе матрицы инцидентности неориентированного графа стоит 0, если вершина не инцидентна ребру, или 1, если вершина инцидентна ребру.
В случае ориентированного графа в матрицу вносятся 1, если вершина инцидентна ребру и является его началом, или 0, если вершина не инцидентна ребру, или -1, если вершина инцидентна ребру и является его концом.
Слайд 36

Невзвешенный неориентированный граф

Невзвешенный неориентированный граф

Слайд 37

Матрица инцидентности

Матрица инцидентности

Слайд 38

Невзвешенный ориентированный граф

Невзвешенный ориентированный граф

Слайд 39

Матрица инцидентности

Матрица инцидентности

Слайд 40

Список смежности Список смежности – ещё один из способов представления графа

Список смежности
Список смежности – ещё один из способов представления графа в виде

коллекции списков вершин.
Каждой вершине графа соответствует список, состоящий из "соседей" этой вершины. Если граф взвешенный, то рядом с номером вершины-соседа также указывается длина ребра до этого соседа.
Слайд 41

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

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

Слайд 42

Проектирование графов на алгоритмическом языке С++ Создается класс Graph, он будет

Проектирование графов на алгоритмическом языке С++

Создается класс Graph, он будет шаблонным,

чтобы узел графа мог содержать данные разного типа (например, строки или числа).
Граф будет представлен следующим образом: все вершины графа заносятся в вектор вершин где индекс каждой вершины соответствует ее индексу в матрице смежности.
Например, если в векторе вершин у одной вершины индекс i, а у другой j, то наличие или отсутствие ребра между вершинами в матрице смежности определяется значением по индексу [i][j].
В приватном поле класса Graph хранится вектор вершин и матрица смежности.
Слайд 43

Свойства класса Вектор вершин Матрица смежности n – размер матрицы смежности

Свойства класса

 

Вектор вершин

Матрица смежности

n – размер матрицы смежности

 

Слайд 44

Создание класса. Свойства класса

Создание класса. Свойства класса

Слайд 45

Создание класса. Конструктор

Создание класса. Конструктор

Слайд 46

Методы проверки на заполненность

Методы проверки на заполненность

Слайд 47

Вставка вершины

Вставка вершины

Слайд 48

Получение индекса вершины

Получение индекса вершины

Слайд 49

Получение количества вершин

Получение количества вершин

Слайд 50

Получение веса между вершинами

Получение веса между вершинами

Слайд 51

Получение вектора соседей

Получение вектора соседей

Слайд 52

Вставка ребра для ориентированного графа

Вставка ребра для ориентированного графа

Слайд 53

Вставка ребра для неориентированного графа

Вставка ребра для неориентированного графа

Слайд 54

Печать матрицы смежности графа

Печать матрицы смежности графа

Слайд 55

Получение количества ребер для ориентированного графа

Получение количества ребер для ориентированного графа

Слайд 56

Получение количества ребер для неориентированного графа

Получение количества ребер для неориентированного графа

Слайд 57

Пример работы с графом. (Ориентированным, невзвешенным)

Пример работы с графом. (Ориентированным, невзвешенным)

Слайд 58

Слайд 59

Слайд 60

Слайд 61

Слайд 62

Слайд 63

Методы обхода графов. Обход в глубину или правило левой руки Алгоритм

Методы обхода графов. Обход в глубину или правило левой руки

Алгоритм обхода

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

Обход в глубину

Обход в глубину

Слайд 65

Обход в глубину

Обход в глубину

Слайд 66

Обход в глубину

Обход в глубину

Слайд 67

Обход в глубину

Обход в глубину

Слайд 68

Методы обхода графов. Обход в ширину Поиск начинается с начальной вершины,

Методы обхода графов. Обход в ширину

Поиск начинается с начальной вершины, которая

обрабатывается, маркируется и помещается в очередь.
Основой алгоритма является циклический процесс, в котором обработанная вершина удаляется из очереди, а в очередь помещаются соседствующие с обработанной вершины. Таким образом, тело цикла состоит из двух основных шагов:
Удалить вершину v из головы очереди
Для каждой непомеченной вершины u, соседней по отношению к вершине v, обработать вершину u, маркировать ее и поместить в очередь (вершина u может иметь соседние необработанные вершины).
Слайд 69

Слайд 70

Слайд 71

Слайд 72

Слайд 73

Слайд 74

Обход в ширину

Обход в ширину

- Предыдущая
Разделительные Ъ и Ь
Следующая -
Курение вредно и опасно! Будьте здоровы!

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

Анализ параллельных вычислений. Лекция 3
Полный курс подготовки к ЕГЭ по математике. Планиметрия. Углы, связанные с окружностью
Математические модели задач на движение или работу
Алгебра логики
Квадратичная функция. Ее свойства и график. Проверка домашнего задания
Выигрышная стратегия
Медианы, биссектрисы и высоты треугольника
Показательная и тригонометрические функции комплексного переменного
СКАЛЯРНОЕ ПРОЗВЕДЕНИЕ ВЕКТОРОВ Подготовили: Рощупкина Л.И., Воложанина Т.Н. урок математики 9 класс МБОУ СОШ №96 Г.Барнаул
Число 10
Вычитание из чисел 6 и 7. Состав 6 и 7
Сложение с переходом через десяток. Тренажёр
Аттестационная работа. Проектная и исследовательская деятельность учащихся на уроках математики
Вынужденные гармонические колебания стержней с распределенной массой при изгибе
Оптимизационные методы решения систем линейных алгебраических уравнений
Размещение из N элементов по k (k ≤ n)
Функция. График функции
Перпендикулярность плоскостей. Параллелепипед
Задача 37
Разложение многочлена на множители
Математический турнир
Координаты вектора
Системы линейных уравнений Лекция 3
Необходимый признак экстремума
Areas of Prisms
Теория вероятностей
Четырехугольники. Трапеция
Автор: Воронцова Ольга Владимировна
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть