Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ 6 5 4 3 2 1 4 1 2 7 1 6 8 3 2 2. - презентация

1 Введение в теорию графов

2 ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ

3 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 Граф G задается с помощью пары множеств G = (V, R), где V – множество вершин, R – множество ребер, соединяющих пары вершин. Граф G в форме схемы Вершины называются смежными, если их соединяет ребро. Количество вершин и количество ребер графа определяют мощности множеств V и R. Ребро и любая из его двух вершин называются инцидентными. Под степенью вершины подразумевается количество инцидентных ей ребер. Количество вершин графа G равно 5, а количество ребер равно 8. Степень вершины V 1 равна 3, а степень вершины V 5 равна 4.. Вершины V 1 и V 2 смежны.

4 v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 Маршрут графа – это последовательность чередующихся вершин и ребер Маршрут является замкнутым (циклом) если его начальная и конечная вершины совпадают. Маршрут называется простой цепью, если все его вершины и ребра различны. Граф считается связным, если каждая его вершина достижима из любой другой. Одна вершина достижима из другой, если между ними проложен маршрут. Вершины, которые не имеют инцидентных ребер, называются изолированными вершинами. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ В ориентированном графе (орграфе) каждое ребро (дуга) имеет одно направление. Входящая и исходящая степени вершины – это соответственно число входящих в вершину дуг и исходящих из нее дуг Взвешенный граф (сеть) – это такой граф, ребрам или дугам которого поставлены в соответствие числовые величины. Вес сети равен сумме весов ее ребер

5 v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 Для наглядного представления используют схемы. ОПИСАНИЕ ГРАФА С ПОМОЩЬЮ МАТРИЦЫ СМЕЖНОСТИ Граф G в форме схемы Граф и сеть G в форме матрицы смежности Для математических расчетов удобнее использовать представление графа в форме матрицы смежности а)б) Элемент матрицы смежности равен 1, если вершины смежны, и 0, если вершины не смежны. Диагональные элементы равны 0, так как вершины сами с собой не смежны.

6 v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 ПОДГРАФЫ И ДЕРЕВЬЯ Подграфом графа G называется граф, у которого все вершины и ребра принадлежат графу G. а) подгаф графа G Остовной связный подграф – это подграф графа G, который содержит все его вершины и каждая его вершина достижима из любой другой. Дерево – это граф, в котором нет циклов. Остовным связным деревом называется подграф, включающий все вершины исходного графа G, каждая вершина которого достижима из любой другой, и при этом не содержит циклов. v2v2 v3v3 v5v5 R 25 R 23 R 35 v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 23 R 35 R 34 v4v4 v1v1 v2v2 v3v3 v5v5 R 14 R 23 R 35 R 34 б) остовной связный подграф графа G в) остовное связное дерево

7 ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА Граф G в форме схемы Матрица смежности связного взвешенного неориентированного графа G v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 Цикломатическое число γ показывает, сколько ребер графа нужно удалить, чтобы в нем не осталось ни одного цикла. Цикломатическое число γ равно увеличенной на единицу разности между количеством ребер и количеством вершин: γ = m – n +1 Для графа G: γ = m – n + 1 = 8 – = 4

8 ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R 34 Для каждого графа обычно существует несколько остовных связных деревьев, которые обладают различными весами. Остовные связные деревья графа G Граф G в форме схемы v4v4 v1v1 v2v2 v3v3 v5v5 R 14 R 25 R 23 R 34 v4v4 v1v1 v2v2 v3v3 v5v5 R 14 R 23 R 35 R 45 v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 34

9 ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА Для построения остовного связного дерева минимального веса используется алгоритм Крускала Из графа удаляются все ребра, получается остовной подграф, где все вершины изолированы. Каждая вершина такого графа помещается в одноэлементное подмножество. Ребра сортируются по возрастанию весов. Ребра последовательно, по возрастанию их весов, включаются в остовное дерево. Существуют четыре случая: а) обе вершины включенного ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; б) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро. 4 Алгоритм заканчивает свою работу, когда все вершины будут объединены в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.

10 ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА v4v4 v1v1 v2v2 v3v3 v5v5 R 12 R 14 R 15 R 25 R 23 R 35 R 45 R v4v4 v1v1 v2v2 v3v3 v5v5 R 45 R 15 v4v4 v1v1 v2v2 v3v3 v5v5 3 v4v4 v1v1 v2v2 v3v3 v5v5 24 R 23 R 45 R 15 v4v4 v1v1 v2v2 v3v3 v5v5 R 25 5 R 23 R 45 R 15 v4v4 v1v1 v2v2 v3v3 v5v5 6 Не включать в граф ребра R 14, R 12, R 34, R Получено остовное (включены все вершины) связное (все вершины можно соединить маршрутами) дерево (отсутствуют циклы) минимального веса (последовательно включались ребра, отсортированные по возрастанию весов) Минимальный вес дерева: R 23 +R 25 +R 15 +R 45 = = 80 Циклографическое число графа G равно γ = m-n+1=8-5+1=4, что соответствует количеству ребер, не включенных в остовное связное дерево