Презентация. Алгоритмы на графах

Скачать презентацию




Алгоритмы на графах
 


Определение 1 Граф – это множество точек (называемых вершинами) вместе с набором линий (называемых ребрами), которые соединяют определенные пары вершин.
 


Определение 2 Неориентированным графом называется такая пара
 


Две вершины называют смежными (adjacent) если их соединяет ребро Пусть V и V’ являются вершинами и n?0. Последовательность (V0, V1, …, Vn) называется путем длины n от вершины V к вершине V’ , если V=V0 , V’=Vn и вершина Vk является смежной для вершины Vk+1 для всех 0?k 


Путь называется простым, если различны вершины (V0, V1, …, Vn-1) и различны вершины (V1, …, Vn) . Другими словами: различны все вершины за исключением может быть первой и последней. Например, пусть дан граф: Определения Простые пути: 1,2,3,4,5 1,2,4,5,3,1 Не простой путь: 1,3,2,4,3,5
 


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


Пример: Связный граф. Вершина 3 является смежной с вершинами 1,2,4,5. Вершина 1 не является смежной с вершиной 4 От вершины 2 к вершине 3 есть три пути: Длиной 1: (2,3) Длиной 2: (2,1,3) и (2,4,3) В графе есть несколько циклов: (3,5,4,3), (1,2,3,1) (1,2,4,3,1) и др. Имеет 5 вершин, 7 ребер
 


Пример: Несвязный граф. Граф имеет две компоненты смежности Вершина 7 является смежной с вершинами 8 и 9 От вершины 5 к вершинам 7,8,9 нет ни одного пути Вершина 2 имеет степень 2 Вершина 1 имеет степень 3 Имеет 9 вершин, 11 ребер
 


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


Справедлива теорема: Если G – граф, то для него эквивалентны утверждения: G – свободное дерево G – связный граф, который при удалении любого ребра перестает быть связным Если V и V’ – две различные вершины графа G, то существует единственный простой путь от вершины V к вершине V’
 


Справедлива теорема: Если граф конечен и имеет ровно n>0 вершин, то эквивалентны следующие утверждения: G – не содержит циклов и имеет n-1 ребро G – связный граф, имеющий n-1 ребро
 


Определения: Ориентированным графом или орграфом называют граф, в котором каждое ребро (дуга) является упорядоченной парой (u,v), где u является началом, а v – концом дуги. Дугу (или ребро) записывают u -> v или изображают
 


Орграфы Используются для представления отношений между объектами Вершины используют для обозначения объектов Дуги – для обозначения отношений между объектами Например: задача о движении автобусов: Вершины – названия городов Дуги – маршруты автобусов из одного города в другой
 


Орграфы Пример: блок-схема компьютерной программы Вершины – блоки операторов Дуги – направленное перемещение потоков данных
 


Орграфы: определения Ориентированный граф – это множество вершин и множество дуг, каждая из которых проходит от некоторой вершины V к вершине V’. При этом вершина V называется началом дуги или начальной вершиной, V’ – концом дуги или конечной вершиной. Различные дуги могут иметь одни и те же начальные и конечные вершины.
 


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


Орграфы: определения Ориентированный граф называется строго связным, если для любых двух вершин V и V’ существует ориентированный путь из V->V’ Орграф является корневым, если существует хотя бы один корень: т.е. такая вершина R , для которой существует ориентированный путь от любой другой вершины V к R Строго ориентированный граф всегда корневой (обратное неверно)
 


Орграфы: определения Ордеревом (или корневым) называется орграф с корнем R: Любая вершина V является начальной только для одной дуг; R не является начальной ни для какой дуги; R является корнем.
 


Оргафы: способы представления: Матрица смежности Пусть задан граф, имеющий n вершин. Матрицей смежности - называется матрица размерами nxn со значениями булевого типа (True, False) или (1,0):
 


Оргафы: способы представления: Матрица смежности Пусть дан граф: Матрица смежности:
 


Оргафы: способы представления: Матрица смежности Помеченный граф: 1 2 4 3 Матрица смежности: для помеченных графов вместо 0 и 1 часто ставят значения соответствующих дуг b b d d c a c a
 


Неориентированный граф Представление с помощью матриц Неориентированный граф: 1 2 4 3 В строках указывают вершины (n - количество вершин) В столбцах – ребра (m- количество ребер) Размерность матрицы nxm
 


Неориентированный граф Матрица инциденций Неориентированный граф: 1 2 4 3 Матрица инциденций строится аналогично матрице смежности для орграфа Размерность матрицы nxn Матрица симметрична
 


Матрицы смежности Недостатком представления орграфа с помощью матрицы смежности является тот факт, что для ее хранения требуется O(N2) объема памяти. При этом количество дуг может быть много меньше N2. В связи с этим становится невозможным создание алгоритмов порядка O(N) для работы с орграфами, имеющими O(N) дуг
 


Орграфы: способы представления Списки смежности Пусть задан орграф, вершины которого имеют некоторые метки. Списком смежности для вершины i называется список всех вершин, смежных с ней, причем упорядоченный определенным образом. Для описания орграфа, состоящего из n вершин потребуется n списков смежности, по одному для каждого узла.
 


Орграфы: способы представления Списки смежности Орграф можно представить в виде массива HEAD[n], в котором i-тый элемент является указателем на список смежности вершины I. Достоинства данного способа: Если дуги имеют метки, их можно заносить в ячейки связных списков Вставка и удаление элементов в списки осуществляется достаточно просто Не задействована избыточная память
 


Орграфы: способы представления Списки смежности HEAD
 

< <       > >