Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.

Презентация:

Advertisements

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

Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.

Advertisements

ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.

Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.

1 Лекция 6 Графы. 2 Граф – это множество вершин и соединяющих их ребер. Примеры графов:

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.

ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.

Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,

Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.

Лекция 9 Отношения, графы Определения. Определение. Пусть а и b объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых.

Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.

Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ

Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа

1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.

Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.

1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936.

V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.

Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.

Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.

Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.

Лекция 7. Определение связности узлов коммутации сети связи на основе теории графов Учебные и воспитательные цели: 1.Уяснить алгоритмы определения связности.

Транксрипт:

Теория графов Основные определения

Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j (V i V j ) Г – эту пару назовем дугой U k

Пример

Неориентированные графы Если бинарное отношение симметрично, то наряду с дугой (Vi,Vj) есть дуга (Vj,Vi). В этом случае чаще всего переходят к неориентированным графам.

Задание графов Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. a ij =1 если вершина i инцидентна ребру j, в противном случае a ij =0. Для орграфа a ij =-1 если из вершины i исходит ребро j, a ij =1 если в вершину i входит ребро j. Если ребро - петля, то a ij =2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. D ij = число ребер, соединяющее вершины i,j. Матрица Кирхгофа: b ij =-1, если вершины i и j смежны, b ij =0 если вершины i и j не смежны. Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Полустепень вершины Для ориентированных графов: полустепенью исхода вершины |Г(V i )| будем называть число дуг, исходящих из вершины V i ; полустепенью захода вершин |Г -1 (V i )| будем называть число дуг, заходящих в вершину. В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v). Для неориентированных графах говорят только о степени. Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.

Достижимость Матрица достижимости R={r ij }, {r ij }=1, если V j достижима из V i, {r ij }=0 в противном случае. R=E+A+А 2 +…+A k В степенях используется «булевское» умножение матриц (строк на столбец, но 1+1=1, 0+1=1,0+0=0, 1+0=0). K – такое число, при котором дальнейшее сужение степеней не меняет матрицу R.

Алгоритм Краскалла Составляется список ребер в порядке увеличения весов. В искомое дерево добавляем, начиная с первого элемента списка по порядку этого списка ветви до те пор, пока не встречаем ветвь, образующую с ранее включенной цикл. Данную ветвь вычеркиваем из списка. Затем продолжаем аналогичные действия до (n-1) ветви.

Алгоритм Дейкстры Пусть имеется направленный ориентированный граф с двумя выделенными вершинами V s и V t. Найти минимальный направленный путь из V s в V t. Помечаем вершину V s, и присваиваем ей вес q s :=0, а всем остальным присваиваем временный вес q i = Полагаем i=s – номер последней отмеченной вершины Для каждой неотмеченной вершины V j выполняется следующий оператор q j :=min(q j, q i +p ij ), где p ij – вес ветви, ведущей из i-той вершины в j-тую, если нет p ij, считаем p ij =

Алгоритм Дейкстры Проверяем, есть ли среди только что отмеченных q j конечное значение. Если таких вершин нет, то мы завершаем алгоритм, пути из s в t не существует. Если же конечное значение q j найдется, то из них выбирается минимальная. Пусть это вершина j 0, тогда мы помечаем эту вершину, а так же помечаем ту дугу, по которой мы добирались в вершину V j0, при получении этого минимального значения. I=j o Проверяем условие i=t. Если это так, алгоритм завершается, L(s-t)=q j0. Сам же минимальный путь считается, начиная с вершины Vt по выделенным дугам в обратном порядке. Если же it, возвращаемся к пункту 3.