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

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

2 Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных ребрами – ребро d между вершинами А и В, ребро e между вершинами В и С, ребро f между вершинами В и А, ребро g между вершиной С и С. – Как называется ребро е по отношению к ребру d? – Как называется ребро g?

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

4 Задание графов По матрице смежности построить граф abcd a0110 b1010 c1101 d0010

5 Задание графов Построить граф, если задана матрица инцидентности uvwx a1000 b1110 c0101 d001 1

6 Изоморфизм Показать, что следующие два графа изоморфны

7 Изоморфизм Изобразить все попарно неизоморфные 4- вершинные графы без петель и кратных ребер. Изобразить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

8 Изоморфизм и степень вершин Изобразить все попарно неизоморфные 6- вершинные графы без петель и кратных ребер со следующим набором степеней вершин (2, 2, 3, 3, 3, 5) Изобразить все попарно неизоморфные не имеющие петель и кратных ребер кубические графы с 6 вершинами (кубические – однородные (у которых все вершины – одинаковой степени) графы со степенью 3)

9 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

10 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

11 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

12 Остов минимального веса Задача нахождения остова минимального веса во взвешенном связном графе, возникает при проектировании линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов, связных либо непосредственно соединяющим их каналом, либо через другие центры и каналы, так, чтобы общая длина (или, например, стоимость) каналов связи была минимальной. Решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n (можно доказать, что полный граф Kn содержит nn–2 различных остовных дерева). Однако для ее решения имеются эффективные алгоритмы. Опишем два из них - алгоритмы Дж. Краскала (1956) и Р. Прима (1957), применяемые к произвольному связному графу (G, w) порядка n.

13 Алгоритм Краскалла Шаг 1. Строим граф T 1 =O n +e 1, присоединяя к пустому графу на множестве вершин V G ребро e 1 V G минимального веса. Шаг 2. Если граф T i уже построен и i

14 Задание Дан граф, найти остов минимального веса

15 Задача о минимальной связке Найти остовное дерево графа с наименьшим весом, используя алгоритм Краскалла

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

17 Волновой метод Алгоритм решения задачи волновым методом. Алгоритм решения задачи волновым методом. 1. Помечаем вершину а индексом Вершины, смежные с а и соединенные с а, дугами, инцидентными вершине а, помечаем индексами Вершины, смежные с помеченными индексами 1 и соединенные с ними инцидентными вершинам 1 дугами, помечаем индексами 2.

18 Волновой метод 4. Аналогично помечаем вершины индексами 3, 4, … 5. Совокупность вершин, помеченных индексом m, обозначим A m. 6. В некоторой момент будет помечена вершина b, пусть b A n. Останавливаем процесс индексации.

19 Волновой метод 7. По построению можно найти вершину b 1 A n-1, смежную с b, по тем же соображениям существует вершина b 2 A n-2, смежная с b 1, и т.д. 8. Искомая цепь с наименьшим числом ребер получается теперь как последовательность вершин (b, b 1, b 2, …, b n =a), где b i A n-i, то есть нужно двигаться, начиная от конечной вершины b в сторону убывания индекса вершины.

20 Задание Найти все кратчайшие цепочки от b до а а b

21 Условный радиус вершины Если мы не будем останавливать индексацию, то через некоторое количество шагов все вершины графа будут снабжены индексами, причем наибольший из них является условным радиусом графа G относительно вершины а. r a =max d(a, b)

22 Волновой метод В случае ориентированного графа волновой метод позволяет решить две задачи: – Найти длины кратчайших путей от вершины а до остальных вершин графа; – Найти длины кратчайших путей от каждой вершины графа до вершины а. При этом в основном алгоритме изменяется только построение множества А n.

23 Центр и диаметр графа Расстоянием между вершинами a и b называется длина кратчайшей цепи из a в b. Радиус графа определяется как наименьший из условных радиусов вершин графа. Центром графа G называется такая вершина a, что максимальное расстояние между a и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом графа. Диаметром d связного графа называется максимальное возможное расстояние между любыми двумя его вершинами. Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, – диаметральной цепью.

24 Задание Найти центр, радиус и диаметр графа

25 Задача о кратчайшей цепи Задача о кратчайшем пути. Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети. Известно, что для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

26 Алгоритм Дейкстры Алгоритм основан на приписывании узлам временных или постоянных меток. Первоначально только источнику приписывается постоянная метка, равная нулю. Всем другим узлам приписываются временные метки, соответствующие весу дуги из источника в рассматриваемый узел. Если такой дуги нет, то узлу приписывается временная метка, равная бесконечности.

27 Алгоритм Дейкстры Для определения ближайшего к источнику узла выберем временную метку с минимальным значением и объявим ее постоянной. Затем, до тех пор, пока стоку не будет приписана постоянная метка, необходимо выполнить следующее:

28 Алгоритм Дейкстры 1. Рассмотреть оставшиеся узлы с временными метками. Сравнить величину каждой временной метки с суммой величин последней из постоянных меток и веса дуги, ведущей из соответствующего постоянно помеченного узла в рассматриваемый. Минимальная из двух сравниваемых величин определяется как новая временная метка рассматриваемого узла. 2. Среди временных меток выбрать минимальную и объявить ее постоянной. После постоянного помечивания стока алгоритм прекращает работу, при этом минимальная сумма весов дуг, соединяющий источник и сток, равна постоянной метке стока. Искомая цепь состоит из дуг, для каждой из которых разность между постоянными метками ее концевых узлов равна весу этой дуги.

29 Задание 1 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна. S V1V1 V2V2 t V5V5 V3V3 V4V

30 Задание 2 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна S t

31 Задание 3 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна. t S V1V1 V2V2 V3V3 V8V8 V7V7 V6V6 V4V4 V5V5