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

1 Графы Волновой метод

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

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

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

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

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

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

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

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

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

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

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

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

14 Волновой метод 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 в сторону убывания индекса вершины.

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

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

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

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

19 Задание Найти радиус и диаметр графа

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

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

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