Графы Волновой метод
Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Задание графов По матрице смежности построить граф abcd a0110 b1010 c1101 d0010
Задание графов Построить граф, если задана матрица инцидентности uvwx a1000 b1110 c0101 d001 1
Изоморфизм Показать, что следующие два графа изоморфны
Изоморфизм Изобразить все попарно неизоморфные 4- вершинные графы без петель и кратных ребер. Изобразить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.
Изоморфизм и степень вершин Изобразить все попарно неизоморфные не имеющие петель и кратных ребер кубические графы с 6 вершинами (кубические – однородные (у которых все вершины – одинаковой степени) графы со степенью 3)
Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.
Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.
Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.
Волновой метод Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется найти цепь, соединяющую вершины а и b и содержащую наименьшее число ребер.
Волновой метод Алгоритм решения задачи волновым методом. Алгоритм решения задачи волновым методом. 1. Помечаем вершину а индексом Вершины, смежные с а и соединенные с а, дугами, инцидентными вершине а, помечаем индексами Вершины, смежные с помеченными индексами 1 и соединенные с ними инцидентными вершинам 1 дугами, помечаем индексами 2.
Волновой метод 4. Аналогично помечаем вершины индексами 3, 4, … 5. Совокупность вершин, помеченных индексом m, обозначим A m. 6. В некоторой момент будет помечена вершина b, пусть b A n. Останавливаем процесс индексации.
Волновой метод 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 в сторону убывания индекса вершины.
Задание Найти все кратчайшие цепочки от b до а а b
Волновой метод В случае ориентированного графа волновой метод позволяет решить две задачи: Найти длины кратчайших путей от вершины а до остальных вершин графа; Найти длины кратчайших путей от каждой вершины графа до вершины а. При этом в основном алгоритме изменяется только построение множества А n.
Условный радиус вершины Если мы не будем останавливать индексацию, то через некоторое количество шагов все вершины графа будут снабжены индексами, причем наибольший из них является условным радиусом графа G относительно вершины а. r a =max d(a, b)
Центр и диаметр графа Расстоянием между вершинами a и b называется длина кратчайшей цепи из a в b. Радиус графа определяется как наименьший из условных радиусов вершин графа. Центром графа G называется такая вершина a, что максимальное расстояние между a и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом графа. Диаметром d связного графа называется максимальное возможное расстояние между любыми двумя его вершинами. Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, – диаметральной цепью.
Задание Найти радиус и диаметр графа
Задание Найти радиус, диаметр и центр графа
Задание Найти радиус, диаметр и центр графа
Задание Найти радиус, диаметр и центр графа