Метрические характеристики неориентированного графа

Пусть G(V,X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний Cn2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа: d(G) = maxd(v, w).

v, wÎV

 

Эксцентриситет (максимальное удаление) вершины: r(v) = maxd(v, w);

vÎV

Радиус графа : r(G) = min r(v);

vÎV

Центр графа: любая вершина vÎV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин , радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

 

 

 

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С52 = 5!/3!2! = 10: d(v1, v2) =1, d(v1, v3) = 2, d(v1, v4) = 2, d(v1, v5) = 3, d(v2, v3) = 1, d(v2, v4) = 1, d(v2, v5) = 2, d(v3, v4) = 1, d(v3, v5) = 2, d(v4, v5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3.

Радиус графа r(G) = 2.

Центры графа v2, v3, v4 .

 

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

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

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v1 в vn.

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(vi): a(v1) = 0, a(vi) = ¥, i ¹ 1. окрасить вершину v1 и положить v = v1.

Шаг 2. Для каждой неокрашенной вершины vj изменить индекс по правилу:

a(vj) = min {a(vj), a(v) + l(v, vj)}.

Окрасить ту из вершин, для которой a(vj) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину vj . Положить v = vj.

Шаг 3. Если v = vj , закончить процедуру, так как кратчайший маршрут из v1 в vn . если v ¹ vn , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(vj)= ¥. В этом случае вершина vn недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v1 в v6.

 

 

Шаг 1. Окрасим вершину v1 . Присвоим вершинам индексы: a(v1) =0, a(v2) = a(v3)=…= a(vn)=¥. Полагаем v1 = v.

Шаг 2.

a(v2) = min {¥, 0+4} = 4,

a(v3) = min {¥, 0+7} = 7,

a(v4) = min {¥, 0+3} = 3,

a(v5) = min {¥, 0+¥} = ¥,

a(v6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v4 и ребро {v1, v4}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v4.

Шаг 2.

a(v2) = min {4, 3+¥} = 4,

a(v3) = min {7, 3+¥} = 7,

a(v5) = min {¥, 3+3} = 6,

a(v6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v2 и ребро {v1, v2}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v2.

Шаг 2.

a(v3) = min {7, 4+3} = 7,

a(v5) = min {6, 4+2} = 6,

a(v6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v5 и ребро {v4, v5}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v5.

Шаг 2.

a(v3) = min {7, 6+¥} = 7,

a(v6) = min {¥, 6+2} = 8.

Окрашиваем вершину v3 и ребро {v1, v3}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v3.

Шаг 2.

a(v6) = min {8, 7+2} = 8.

Окрашиваем вершину v6 и ребро {v5, v6}.

Так как вершина v6 окрашена, то работу прекращаем. Получили минимальный маршрут v1 v4 v5 v6 , длина которого равна 8 .

 

Заметим, что это в данном случае не единственный для вершин v1 и v6 минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v4, v5} ребро {v2, v5}, тогда бы получили другой маршрут той же длины.

 

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

Граф без циклов называется лесом.

Дерево – это связный ациклический граф.

 

           
   
   
 
 

 


 

 

Лес Дерево

 

 

Компоненты связности леса – деревья.

Свойства деревьев.

Граф G – дерево, если он связный и число ребер на единицу мкньше числа вершин.

Если G – дерево, тогда любая цепь будет простой.

Любые две вершины дерева можно соединить цепью, притом простой.

Пусть G – дерево. Если добавить одно ребро, то получим ровно один простой цикл.

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

Рассмотрм одну из таких задач. Для этого введем еще одно определение.

Остовом (покрывающим деревом) графа называется его подграф, являющийся деревом и содержащий все вершины графа.

Пусть требуется n городов соединить сетью дорог. Стоимость строительства каждой дороги между двумя городами известна. Построим граф, в котором вершшины – города, ребра – дороги. Каждому ребру припишем вес, равный стоимости строительства дороги.. определим вес остова, как сумму весов составляющих его ребер.

Проектирование сети дорог сводится к построению остова гарфа, имеющего минимальный вес. В силу связности дерева выполнится условие соединить каждый город с каждой дорогой.

Рассмотрим сначала задачу построения остова без учета весов его ребер. Идея алгоритма состоит в том, что просматриваются в произвольном порядке ребра графа и св соответствии с правилом принимается решение о включении очередного ребра в остов.

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

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

Алгоритм построения остова

Шаг 1. Выбрать любое ребро и окрасить в зеленый цвет. Образовать подграф G1 из этого ребра. Выполнить шаг 2.

Шаг 2. Пусть просмотрено i > 1 ребра графа G. Выбрать любое неокрашенное ребро. Возможны четыре варианта.

Вариант а. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , добавив к компонентам подграфа Gi новую компоненту связности – рассматриваемое ребро. Выполнить шаг 2.

Вариант б. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , объединив две компоненты связности в одну. Выполнить шаг 2.

Вариант в. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , добавив к одной компоненте подграфа Gi рассматриваемое ребро. Выполнить шаг 2.

Вариант г. Окрасить ребро в красный цвет, если оно образут в построенным подграфе цикл.

Замечание. Данный алгоритм называется «жадным», т.к. каждое ребро просматривается не более одного раза, т.е. после просмотра оно окрашивается в зеленый или красный цвет , и в рассмотрение больше не включается.

Построим остов для графа, заданного диаграммой, не учитывая вес ребер.

Окрасим ребро {v1, v2} в зеленый цвет.

Окрасим ребро {v4, v5} в зеленый цвет, т.к имеет место вариант а.

Окрасим ребро {v4, v1} в зеленый цвет, т.к имеет место вариант б.

Окрасим ребро {v2, v5} в красный цвет, т.к имеет место вариант г.

Окрасим ребро {v4, v3} в зеленый цвет, т.к имеет место вариант в.

Ациклический подграф содержит все вершины графа, значит остов построен:

 

 
 

 


Присвоим каждому ребру вес. И построим остов с минимальным весом (минимальный остов).

Алгоритм построения такого остова отличаеися от вышеизложенного лишь тем, что ребра просматриваются в порядке возрастания их весов. Если на каком – то шаге среди непросмотренных ребер имеется более одного ребра с наименьшим весом, то рассматривается на данном шаге любое из них.

 

 

У порядочим ребра графа, переписывая их в порядке возрастания их весов: {v1, v2}, {v4, v5},{v1, v4},{v5, v2},{v3, v5},{v3, v2},{v1, v3},{v4, v3}.

Окрасим ребро {v1, v2}в зеленый цвет.

Окрасим ребро {v4, v5} в зеленый цвет (вариант а).

Окрасим ребро {v1, v4} в зеленый цвет (вариант б).

Окрасим ребро {v5, v2} в красный цвет (вариант г).

Окрасим ребро {v3, v5} в зеленый цвет (вариант в).

Ациклический подграф содержит все вершины графа, значит остов построен:

 

 

 
 

 


 

5. Цикловой ранг графа. Цикломатическое число

Если G(V, X) не является ациклическим графом, то в нем можно выделить цикл.

Независимыми называются циклы графа G, если они отличаются хотя бы одним ребром.

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

Количество простых циклов в базисе называется цикломатическим числом или циклическим рангом графа G.

Обзначим цикломатическое число через n(G).

Справедливо утверждение:

Если G(V, X) – связный граф, то n(G) = m(G) – n(G) + p(G), где m(G) – количество ребер в графе, n(G) – количество вершин в графе, p(G) – количество компонент связности в графе.

Так, например, для дерева не существует цикловой базис, т.к. в дереве m = n – 1, р = 1(дерево – связный граф). Тогда цикломатическое число равно n(G) = n – 1 – n +1 = 0. Следовательно в базисе нет ни одного цикла.

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

Если n(G) = 0, то граф ациклический, циклового базиса не существует.

Пусть n(G) > 0. Выделим в G любое остовное дерево Т. Пусть число вершин в графе G равно n, а число ребер – m. x1, x2,…, xn-1 – ребра в Т (остовное дерево содержит все вершины графа, а по свойству дерева число ребер на 1 меньше числа вершин), xn, xn+1,…, xm – остальные ребра графа G (заметим, что n ³ 2, m ³ n). Число последних ребер m – (n – 1) = m – n + 1, и совпадает с цикломатическим числом связного графа. Добавляя любое из ребер xi ( i = n, …, m) , к дереву Т, получаем некоторый подграф графа G, из которого выделяем простой цикл mi-(n-1) , проходящий через ребро xi . Действуя таким образом, находим совокупность простых циклов {m1, mm-n+1}. Т.к. в каждом из циклов этой системы имеется ребро, не содержащееся в других циклах, то полученная система независимая, следовательно, является цикловым базисом графа G.

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

Вычислим цикломатическое число: n =4, m = 8, p =1, следовательно, n(G) = 8 - 4 + 1 = 5. Значит, цикловой базис содержит 5 независимых циклов. Построим остовное дерево:

 

 

Добавим по одному удаленные из графа ребра и будем, таким образом, получать простые циклы:

Добавим ребро х3, получим цикл v1 x2 x3 x5 v1.

Добавим ребро x6 , выделим простой цикл: v1 x2 x3 x6 v1.

Добавим ребро x7 , выделим простой цикл: v1 x2 x7 x1 v1.

Добавим ребро x8 , выделим простой цикл: v1 x2 x8 x1 v1.

Добавим ребро x4 , выделим простой цикл: v1 x2 x3 x4 х1 v1.

Получили пять циклов, составляющих цикловой базис графа.