Рабочие листы
к вашим урокам
Скачать
1 слайд
Тема урока: «Графы (основные понятия)»
МДК 01.02 Математический аппарат для построения компьютерных сетей
Смоленск 2015
2 слайд
Что такое граф?
Как хранить графы?
3 слайд
1. Что такое граф?
Граф – набор точек (вершин, узлов), часть из которых соединена отрезками (ребрами, дугами).
4 слайд
1. Что такое граф?
Граф определяется парой множеств:
Конечное множество элементов V (вершин)
Конечное множество элементов (ребер) E, каждый элемент содержит пару вершин (например (a,b))
Если вершины соединены ребром, они называются смежными.
5 слайд
1. Что такое граф?
6 слайд
1. Что такое граф?
Ориентированный граф (орграф, диграф) – граф, ребрам которого задано направление.
7 слайд
1. Что такое граф?
Для ребра (a,c) говорят, что ребро выходит из вершины a и входит в вершину с
8 слайд
1. Что такое граф?
Петля – ребро, которое соединяет вершину саму с собой.
9 слайд
1. Что такое граф?
Полный граф – граф, в котором каждая пара вершин соединена ребрами.
10 слайд
1. Что такое граф?
Взвешенный граф – граф, в котором ребрам поставлены в соответствия какие-то числовые значения.
Числа называются весами, ценами, стоимостями и т.д.
11 слайд
1. Что такое граф?
Путь от вершины a к вершине b –последовательность смежных вершин, которая начинается от вершины a и заканчивается в вершине b.
(0→6): 0→1→2→4→6
(0→6): 0→1→3→2→4→6
Если все вершины
различны
– путь называется простым.
12 слайд
1. Что такое граф?
Направленный путь от вершины a к вершине b – последовательность смежных вершин в ориентированном графе, которая начинается от вершины a и заканчивается в вершине b.
(1→6): 1→2→4→6
(1→6): 1→2→4→5→6
(1→6): 1→2→3→6
13 слайд
1. Что такое граф?
Длина пути - количество ребер, через которые нужно пройти (количество вершин – 1).
Длина простого пути
№1 0→6: 4
№ 2 0→6: 5
14 слайд
1. Что такое граф?
Длина пути во взвешенном графе – сумма весов ребер, через которые прошел путь.
Длина простого пути
№1 0→6: 5+8+6+7=26
№2 0→6: 5+2+4+6+7=24
15 слайд
1. Что такое граф?
Кратчайший путь в графе – путь с наименьшим количеством ребер.
Кратчайший путь во взвешенном графе – путь с минимальным суммарным весом.
Кратчайший путь в графе: №1
Кратчайший путь во взвешенном графе: №2
16 слайд
1. Что такое граф?
Цикл – простой путь, который начинается и заканчивается в одной и той же вершине.
Граф, в котором нет циклов – ациклический. Если циклы есть – граф циклический.
Циклический Ациклический
17 слайд
1. Что такое граф?
Связный граф – граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет.
Несвязный граф
18 слайд
1. Что такое граф?
Связный компонент графа – максимальный связный подграф, который нельзя расширить за счет включения вершин, смежных, с какой-либо вершиной компонента.
Компонент 1: {a,b,c,d,e}
Компонент 2: {f,g,h,i}
19 слайд
1. Что такое граф?
Сильно связный граф – ориентированный граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет.
20 слайд
1. Что такое граф?
Сильно связный компонент графа – максимально связный подграф, в котором любая вершина достижима из любой другой вершины.
21 слайд
1. Что такое граф?
Плотный граф – граф, в котором количество ребер близко к максимальному ((n2-n)/2)
Разреженный граф – граф, в котором количество ребер далеко от максимального.
Плотный Разреженный
22 слайд
2. Как хранить графы?
Граф хранится в виде:
Матрицы смежности Списков смежности
23 слайд
2. Как хранить графы?
Матрица смежности для графа с n вершинами состоит из n*n элементов.
Строка – исходная вершина, столбец – входящая.
Если существует ребро, которое соединяет вершины a и b, тогда на пересечении строки a и столбца b ставится 1, если ребра нет – ставится 0.
Для неориентированного графа матрица смежности симметрична главной диагонали.
24 слайд
2. Как хранить графы?
Списки смежности – массив связанных списков. Для n вершин массив будет состоять из n элементов.
Каждый элемент массива – вершина, откуда выходит ребро.
Каждый элемент списка – вершина, в которую входит ребро.
Связный список формируется в произвольном порядке
25 слайд
2. Как хранить графы?
Для взвешенного графа
Матрица смежности представляет собой матрицу весов. На пересечении a и b ставится вес ребра, или ∞, если ребра нет.
В связном списке появляется поле для обозначения веса ребра.
26 слайд
2. Как хранить графы?
Выбор способа хранения графа зависит, как правило, от используемых алгоритмов.
В остальных случаях, если граф плотный – лучше использовать матрицу смежности. Если граф разреженный – лучше использовать списки смежности.
27 слайд
2. Как хранить графы?
Рабочие листы
к вашим урокам
Скачать
6 625 421 материал в базе
Настоящий материал опубликован пользователем Скряго Ольга Сергеевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
600 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
2 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.