Меню

2 2 Расстояния в ориентированном графе

Электронная библиотека

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w. Это расстояние удовлетворяет аксиомам метрики:

1) d(v, w) 0, причем d(v, w) = 0 тогда и только тогда, когда v=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

Определение. Центром графа называется такая вершина, что максимальное расстояние между ней и любой другой вершиной является наименьшим из всех возможных; это расстояние называется радиусом графа.

Пример 82.

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами dij которой будут расстояния между вершинами vi и vj. Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5. В результате получаем: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v2, v3, v4.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Источник

2.2. Расстояния в ориентированном графе

С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

Пусть ориентированный граф с n³2 вершинами и V,W (V¹W) – заданные вершины из V.

Алгоритм поиска минимального пути из в в ориентированном графе

(Алгоритм фронта волны).

1) Помечаем вершину индексом 0, затем помечаем вершины Î образу вершины индексом 1. Обозначаем их FW1 (V). Полагаем K=1.

2) Если или K=N-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.

В противном случае продолжаем:

3) Если , то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна K. Последовательность вершин

Есть этот минимальный путь. Работа завершается.

4) Помечаем индексом K+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом K. Множество вершин с индексом K+1 обозначаем . Присваиваем K:=K+1 и переходим к 2).

· Множество называется фронтом волны KГо уровня.

· Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько минимальных путей из в .

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу расстояний R(D) между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю ( , I=1. N).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний ( , если ). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка − I-тая и на пересечении с J-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем J-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Примечание. Самый длинный путь найти при помощи алгоритма фронта волны.

Пример

Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин N=7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D Будут иметь размерность 7×7.

Читайте также:  Построение графиков через таблицу

Начинаем заполнять матрицу R(D) минимальных расстояний: сначала ставим нули по главной диагонали и Rij=Aij, если Aij=1, (т. е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, , . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому . В итоге получаем следующую матрицу:

Таким образом, диаметром исследуемого ориентированного графа будет .

Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше : R(Vi) − максимальное из расстояний, стоящих в I-той строке. Таким образом,

R(V1)=3, R(V2)=3, R(V3)=5, r(V4)=4, r(V5)=2, r(V6)=2, r(V7)=3.

Значит, радиусом графа G будет

Соответственно, центрами графа G Будут вершины V5 и V6 , так как величины их эксцентриситетов совпадают с величиной радиуса .

Опишем теперь нахождение минимального пути из вершины V3 в вершину V6 по алгоритму фронта волны. Обозначим вершину V3 как V0, а вершину V6 — как W (см. рис. 8).

Множество вершин, принадлежащих образу V0, состоит из одного элемента — это вершина V4, которую, согласно алгоритму, обозначаем как V1: FW1(V3)=<V4>. Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня — это множество вершин, принадлежащих образу вершины V1: FW2(V3)=<V7>, обозначаем V7≡V2. В образ вершины V2 входят две вершины — V5 и V4, но, так как V4 уже была помечена как V0, то фронт волны третьего уровня состоит из одного элемента: FW3(V3)=<V5>, V5≡V3. Из непомеченных вершин в образ вершины V3 входят V1 и V2, соответственно, FW4(V3)=<V1, V2>, V1≡V4, V2≡V4. Теперь помечены все вершины, кроме V6, которая входит в образ вершины , то есть FW5(V3)=<V6≡W>, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины V3 в вершину V6: V3 V4 V7 V5 V1 V6.

Источник



Тема 7. Маршруты. Расстояние между вершинами графа. Диаметр и центр графа

Пусть G – конечный н-граф.

Маршрутом в G называется последовательность ребер, в которой каждые два соседних ребра имеют общую вершину:

Число ребер в маршруте называется его длиной.

Маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, цепью – если его ребра не повторяются, простой цепью – если его вершины не повторяются,

Маршрут, в котором совпадают начальная и конечная вершины, т.е. , называется циклическим (замкнутым).

Циклический маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца).

Граф, не содержащий циклов, называется ациклическим.

Вершины и называются связными, если существует маршрут с началом в и концом в .

Утверждение: Отношение связности вершин графа является отношением эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества .

Граф называется связным, если для любых двух различных вершин существует маршрут, соединяющий их.

Очевидно, что все подграфы G(Vi) этого графа связны и называются связными компонентами графа.

Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b).

1) d(a, b) = d(b, a);

2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;

3) d(a, b) ≤ d(a, c) + d(c, b)

Матрица расстояний, это симметричная квадратная матрица размерности , строки и столбцы которой соответствуют вершинам графа, а на пересечении строк и столбцов записано расстояние между вершинами .

В последнем столбце матрицы указан эксцентриситет для каждой вершины: расстояние от данной вершины до наиболее удаленной вершины.

Диаметр графа G – максимальное расстояние между вершинами графа. Диаметр находится по формуле:

Читайте также:  Cоветы для Pokemon GO которые я хотел бы услышать 22 уровня назад

Используя найденные эксцентриситеты вершин, диаметр можно найти по формуле:

Радиус графа G – минимальное значение эксцентриситета. Радиус находится по формуле:

Центрграфа G – такая вершина, для которой .

Замечание. Центр в графе может быть не единственный.

Диаметральная цепь графа G – простая цепь, длина которой равна диаметру, соединяющая наиболее удаленные вершины графа.

Радиальная цепь графа G – простая цепь, длина которой равна радиусу, соединяющая центр и наиболее удаленную от него вершину графа.

Пример 7.1.

Для н-графа, приведенного на рисунке 7.1, записать 1) маршрут общего вида, 2) не простую цепь, 3) простую цепь, 4) циклический маршрут общего вида,5) не простой цикл, 6) простой цикл.

Решение:

1) Маршрут общего вида – это маршрут, в котором начальная и конечная вершина различны, и некоторые ребра повторяются. М1 = (1, 4, 5, 1, 4, 7, 3). Здесь повторяется ребро (1, 4).

2) Не простая цепь – это маршрут, в котором не повторяются ребра, но повторяются вершины. М2 = (4, 3, 1, 5, 6, 7, 4, 1). Здесь повторяется вершина 1.

3) Простая цепь – это маршрут, в котором не повторяются вершины. М3 = (4, 3, 7, 5, 6).

4) Циклический маршрут общего вида – это маршрут, в котором начальная и конечная вершины совпадают, и некоторые ребра повторяются. М4 = (1, 5, 1, 5, 1). Здесь повторяется ребро (1, 5).

Рисунок 7.1. Построение маршрутов

в неориентированном графе

5) Непростой цикл – это циклический маршрут, в котором не повторяются ребра, но повторяются вершины. М5 = (3, 4, 5, 7, 4, 1, 3). Здесь повторяется вершина 4.

Заметим, что непростой цикл бывает только в графах, в которых существует конфигурация типа «песочные часы».

6) Простой цикл – это циклический маршрут, в котором не повторяются вершины. М6 = (5, 4, 3, 2, 1, 5).

Пример 7.2.

Для н-графа, приведенного на рисунке 7.1, построить матрицу расстояний. Определить диаметр и радиус графа. Указать центры графа. Записать диаметральные и радиальные цепи

Решение:

Для построения матрицы расстояний, сопоставим строки и столбцы вершинам. На пересечении строк и столбцов укажем расстояние между соответствующими вершинами.

d(a, b) 1 2 3 4 5 6 7
1 1 1 1 1 2 2 2
2 1 1 2 2 3 2 3
3 1 1 1 2 2 1 2
4 1 2 1 1 2 1 2
5 1 2 2 1 1 1 2
6 2 3 2 2 1 1 3
7 2 2 1 1 1 1 2

На месте (1, 1) стоит 0, так как кратчайший маршрут между вершиной 1 и вершиной 1 – это вырожденный маршрут (без ребер) длины 0.

На месте (1, 2) стоит 1, так как кратчайший маршрут между вершиной 1 и вершиной 2 – это единственное ребро, связывающее эти вершины.

На месте (1, 6) стоит 2, так как кратчайшая простая цепь, между вершиной 1 и вершиной 6 – это цепь из двух ребер (1, 5, 6). Значит, расстояние между этими вершинами равно 2.

В последнем столбце таблицы указано расстояние от данной вершины до наиболее удаленной от нее вершины – эксцентриситет. Их значения находим по формуле (7.1).

Максимум значений последнего столбца – диаметр графа. Откуда d(G) = 3.

Минимум значений последнего столбца – радиус графа. Откуда r(G) = 2.

Центрами являются вершины: 1, 3, 4, 5, 7. Их эксцентриситеты равны радиусу графа.

Для построения диаметральных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены друг от друга. Так как максимальное расстояние между вершинами – это диаметр графа, значит, найдем вершины, находящиеся на расстоянии, равном диаметру. Это вершины 2 и 6. Следовательно, все диаметральные цепи в графе связывают эти вершины. Таких цепей две:

D1 = (2, 1, 5, 6) и D2 = (2, 3, 7, 6).

Для построения радиальных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены от центров.

От центра 1 на расстоянии радиуса, равного 2, находятся вершины 6 и 7. Значит можно провести радиальные цепи:

От центра 3 на расстоянии радиуса находятся вершины 5 и 6. Значит можно провести радиальные цепи:

Дата добавления: 2018-04-15 ; просмотров: 5240 ; Мы поможем в написании вашей работы!

Источник

Теория графов — Основные свойства

Графы имеют различные свойства, которые используются для характеристики графов в зависимости от их структуры. Эти свойства определены в конкретных терминах, относящихся к области теории графов. В этой главе мы обсудим несколько основных свойств, которые являются общими для всех графиков.

Читайте также:  Подлежащее статистической таблицы это объект изучения

Расстояние между двумя вершинами

Это число ребер в кратчайшем пути между вершиной U и вершиной V. Если существует несколько путей, соединяющих две вершины, то кратчайший путь рассматривается как расстояние между двумя вершинами.

Обозначение — d (U, V)

Может быть любое количество путей из одной вершины в другую. Среди них вам нужно выбрать только самый короткий.

пример

Посмотрите на следующий график —

Расстояние между двумя вершинами

Здесь расстояние от вершины ‘d’ до вершины ‘e’ или просто ‘de’ равно 1, поскольку между ними есть одно ребро. Существует много путей от вершины ‘d’ до вершины ‘e’ —

  • да, а, бе
  • дф, фг, гэ
  • де (считается для расстояния между вершинами)
  • дф, фц, ca, ab, be
  • да, ac, cf, fg, ge

Эксцентриситет вершины

Максимальное расстояние между вершиной и всеми остальными вершинами рассматривается как эксцентриситет вершины.

Обозначение — e (V)

Расстояние от конкретной вершины до всех других вершин графа берется, и среди этих расстояний эксцентриситет является наибольшим из расстояний.

пример

На приведенном выше графике эксцентриситет «а» равен 3.

Расстояние от «a» до «b» равно 1 («ab»),

от ‘a’ до ‘c’ равно 1 (‘ac’),

от «а» до «d» равно 1 («объявление»),

от ‘a’ до ‘e’ равно 2 (‘ab’ — ‘be’) или (‘ad’ — ‘de’),

от ‘a’ до ‘f’ равно 2 (‘ac’ — ‘cf’) или (‘ad’ — ‘df’),

от ‘a’ до ‘g’ равно 3 (‘ac’ — ‘cf’ — ‘fg’) или (‘ad’ — ‘df’ — ‘fg’).

Таким образом, эксцентриситет равен 3, что является максимумом от вершины «а» от расстояния между «ag», которое является максимальным.

Радиус связного графа

Минимальный эксцентриситет от всех вершин рассматривается как радиус графа G. Минимальный среди всех максимальных расстояний между вершиной до всех остальных вершин рассматривается как радиус графа G.

Обозначение — r (G)

Из всех эксцентриситетов вершин графа радиус связного графа является минимумом всех этих эксцентриситетов.

Пример — На приведенном выше графике r (G) = 2, что является минимальным эксцентриситетом для «d».

Диаметр графика

Максимальный эксцентриситет от всех вершин рассматривается как диаметр графа G. Максимальный из всех расстояний между вершиной до всех других вершин рассматривается как диаметр графа G.

Обозначение — d (G)

Из всех эксцентриситетов вершин графа диаметр связного графа является максимальным из всех этих эксцентриситетов.

Пример. На приведенном выше графике d (G) = 3; что является максимальным эксцентриситетом.

Центральная точка

Если эксцентриситет графа равен его радиусу, то он называется центральной точкой графа. Если

тогда «V» является центральной точкой графа «G».

Пример — в примере графика ‘d’ является центральной точкой графика.

Центр

Множество всех центральных точек «G» называется центром графа.

Пример. В примере графика <‘d’>является центром графика.

Длина окружности

Число ребер в самом длинном цикле «G» называется окружностью «G».

Пример. На графике примера длина окружности равна 6, что мы получили из самого длинного цикла acfgeba или acfdeba.

обхват

Число ребер в кратчайшем цикле G называется его обхват.

Обозначения — g (G).

Пример — в примере графика обхват графа равен 4, который мы получили из кратчайшего цикла acfda или dfged или abeda.

Теорема о сумме степеней вершин

Если G = (V, E) ненаправленный граф с вершинами V = 1 , V 2 ,… V n >, то

Следствие 1

Если G = (V, E) ориентированный граф с вершинами V = 1 , V 2 ,… V n >, то

Следствие 2

В любом неориентированном графе число вершин с нечетной степенью является четным.

Следствие 3

В неориентированном графе, если степень каждой вершины равна k, то

Следствие 4

В неориентированном графе, если степень каждой вершины не меньше k, то

Следствие 5

В неориентированном графе, если степень каждой вершины не более k, то

Источник