Презентация по теме «Графы (основные понятия)» для МДК 01.02 Математический аппарат для построения компьютерных сетей

Тема урока: «Графы (основные понятия)»МДК 01.02 Математический аппарат для построения компьютерных сетейСмоленск 2015 Что такое граф?Как хранить графы? 1. Что такое граф?Граф – набор точек (вершин, узлов), часть из которых соединена отрезками (ребрами, дугами).
1. Что такое граф?Граф определяется парой множеств: Конечное множество элементов V (вершин)Конечное множество элементов (ребер) E, каждый элемент содержит пару вершин (например (a,b))Если вершины соединены ребром, они называются смежными.

1. Что такое граф? 1. Что такое граф?Ориентированный граф (орграф, диграф) – граф, ребрам которого задано направление.
1. Что такое граф?Для ребра (a,c) говорят, что ребро выходит из вершины a и входит в вершину с
1. Что такое граф?Петля – ребро, которое соединяет вершину саму с собой.
1. Что такое граф?Полный граф – граф, в котором каждая пара вершин соединена ребрами.
1. Что такое граф?Взвешенный граф – граф, в котором ребрам поставлены в соответствия какие-то числовые значения.Числа называются весами, ценами, стоимостями и т.д.
1. Что такое граф?Путь от вершины a к вершине b –последовательность смежных вершин, которая начинается от вершины a и заканчивается в вершине b.(0→6): 0→1→2→4→6(0→6): 0→1→3→2→4→6Если все вершины различны – путь называется простым.


1. Что такое граф?Направленный путь от вершины a к вершине b – последовательность смежных вершин в ориентированном графе, которая начинается от вершины a и заканчивается в вершине b.(1→6): 1→2→4→6(1→6): 1→2→4→5→6(1→6): 1→2→3→6

1. Что такое граф?Длина пути - количество ребер, через которые нужно пройти (количество вершин – 1).Длина простого пути №1 0→6: 4№ 2 0→6: 5

1. Что такое граф?Длина пути во взвешенном графе – сумма весов ребер, через которые прошел путь.Длина простого пути №1 0→6: 5+8+6+7=26№2 0→6: 5+2+4+6+7=24

1. Что такое граф?Кратчайший путь в графе – путь с наименьшим количеством ребер.Кратчайший путь во взвешенном графе – путь с минимальным суммарным весом.Кратчайший путь в графе: №1Кратчайший путь во взвешенном графе: №2

1. Что такое граф?Цикл – простой путь, который начинается и заканчивается в одной и той же вершине.Граф, в котором нет циклов – ациклический. Если циклы есть – граф циклический. Циклический Ациклический

1. Что такое граф?Связный граф – граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет.Несвязный граф
1. Что такое граф?Связный компонент графа – максимальный связный подграф, который нельзя расширить за счет включения вершин, смежных, с какой-либо вершиной компонента.Компонент 1: {a,b,c,d,e}Компонент 2: {f,g,h,i}

1. Что такое граф?Сильно связный граф – ориентированный граф, в котором для любой пары вершин есть путь (не обязательно простой), который их соединяет.
1. Что такое граф?Сильно связный компонент графа – максимально связный подграф, в котором любая вершина достижима из любой другой вершины.
1. Что такое граф?Плотный граф – граф, в котором количество ребер близко к максимальному ((n2-n)/2)Разреженный граф – граф, в котором количество ребер далеко от максимального. Плотный Разреженный

2. Как хранить графы?Граф хранится в виде: Матрицы смежности Списков смежности
2. Как хранить графы?Матрица смежности для графа с n вершинами состоит из n*n элементов.Строка – исходная вершина, столбец – входящая.Если существует ребро, которое соединяет вершины a и b, тогда на пересечении строки a и столбца b ставится 1, если ребра нет – ставится 0.Для неориентированного графа матрица смежности симметрична главной диагонали.


2. Как хранить графы?Списки смежности – массив связанных списков. Для n вершин массив будет состоять из n элементов.Каждый элемент массива – вершина, откуда выходит ребро.Каждый элемент списка – вершина, в которую входит ребро.Связный список формируется в произвольном порядке


2. Как хранить графы?Для взвешенного графаМатрица смежности представляет собой матрицу весов. На пересечении a и b ставится вес ребра, или ∞, если ребра нет.В связном списке появляется поле для обозначения веса ребра.

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

2. Как хранить графы? {10A1B5D5-9B99-4C35-A422-299274C87663}ЗадачаОптимальный вариантПроверка на вхождение ребра (x,y) в графМатрица смежностиОпределение степени вершиныСписки смежностиОбъем памяти для небольших графовСписки смежности (m-n),Матрица смежности (n2)Объем памяти для больших графовМатрица смежностиВставка или удаление ребраМатрица смежности O(1),Списка смежности O(d)Обход графаСписки смежности Ѳ(m+n)Матрица смежности Ѳ(n2)Лучше для решения большинства проблемСписки смежности