.RU

§ 6.3: Степени вершин графа - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...


^ § 6.3: Степени вершин графа

Пусть G - неориентированный граф, .

Определение 6.3: Количество v ребер графа, инцидентных вершине v графа, называет ее локальной степенью или просто степенью вершины .

Если степени всех вершин графа конечны, то граф называется локально конечным.

Когда заданы матрицы смежности и инцидентности графа, можно определить локальные степени всех его вершин.

В частности, если задана матрица смежности, то vj=, а если задана матрица инцидентности, то vj=.

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

1) vj=.

2) vj=. Когда i-е ребро обычное, и соответствующее слагаемое внешней суммы равно wik, т.е. 1 для ребер, инцидентных вершине vj, и 0 для остальных. Если же оно является петлей, то , а слагаемое внешней суммы равно 2wij, т.е. 2 для петель, инцидентных вершине vj , и 0 для остальных.

Если степени всех вершин графа равны k, то граф называется однородным степени k. В этом случае, если граф имеет n вершин и m ребер, то n=2m/k.

Рассмотрим теперь орграф, для его вершин определены две локальные степени.

Определение 6.4: Число 1v, равное количеству дуг с началом в вершине v, называется полустепенью исхода вершины v.

Определение 6.5: Число 2v, равное количеству дуг с концом в вершине v, называется полустепенью захода вершины v.

Петля дает вклад в каждую из полустепеней по 1.

Локальные степени вершин ориентированного графа просто выражаются через коэффициенты матрицы смежности:

1vi=, 2vi=.

Если полустепени исхода и захода всех вершин орграфа равны k, то орграф называется однородным степени k и n=m/k

^ § 6.4: Изоморфизм и гомеоморфизм графов

Пусть даны два неориентированных графа

G1= , G2= , V1= n1, V2= n2 ,E1= m1, E2= m2.

Графы G1 и G2 изоморфны, если существует биективное (взаимнооднозначное) отображение : V1 V2, сохраняющее смежность вершин, т. е. если ребро (v', v")E1, то ребро ((v'), ( v"))E2 и наоборот.

Аналогично определяется изоморфизм для орграфов.

Замечание: Изоморфные графы (орграфы) отличаются только обозначением вершин.

^ Свойства изоморфных графов:

а) Если G1 и G2 изоморфные графы и  - биективное отображение, то для любой вершины vV1 n1= n2, m1= m2, (v)=((v)), степень вершины равна степени образа этой вершины.

б) Если G1 и G2 изоморфные орграфы и  - биективное отображение, то для любой vV1 n1= n2, m1= m2, 1(v)=1((v)), 2v2v.




На рис.6.6 графы а) и б) изоморфны, но они неизоморфны графу в).

Изоморфизм графов (орграфов) является отношением эквивалентности на множестве графов (орграфов).

Операция подразбиения ребра (v', v") графа G= состоит в удалении из множества E ребра (v', v"), добавление к множеству V вершины v, добавление ко множеству E\{(v', v")} ребер (v', v) и (v, v").

Граф G1 называется подразбиением графа G2, если G1 может быть получен из G2 путем последовательного применения операции подразбиения ребра (рис.6.7).




Графы (орграфы) называются гомеоморфными, если существуют их подразбиения являющимися изоморфными.
^ § 6.5: Часть. Суграф. Подграф

Пусть дан граф G с множеством вершин V и множеством ребер Е : G =.

Граф Н называется частью графа G (H  G), если множество его вершин V(H) содержится во множестве вершин V(G), а множество его ребер E(H) содержится во множестве ребер E(G).

Если V(H)=V(G), то часть Н называется суграфом.

Например, суграфом графа G будет являться граф с тем же множеством вершин, множество ребер которого пусто.

Определение 6.6: Суграф Н покрывает вершины неориентированного графа G и называется покрывающим граф G, если любая вершина последнего инцидентна хотя бы одному ребру графа Н.


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

Любое множество В графа G можно считать множеством ребер некоторой части Н. Множество вершин этой части состоит из вершин, инцидентных элементам множества В. Если В является множеством ребер другой части Н, то Н Н, причем вершины Н, не принадлежащие Н, в графе Н изолированы.

Подграфом G(U) графа G с множеством вершин UV называется часть, которой принадлежат все ребра с обоими концами из U.

Если V(H)=V(G) (множество вершин подграфа Н совпадает с множеством вершин G),то Н называется еще остовным подграфом графа G.

Если же V(H) V(G) (множество вершин подграфа Н не совпадает с множеством вершин G), то Н называется собственным подграфом графа G.

^ Звездный граф для вершины vG состоит из всех ребер с началом или концом в вершине v. Множество вершин звездного графа состоит из вершины v и других, инцидентных его ребрам вершин.




^ § 6.6: Маршруты. Цепи. Циклы

Пусть G - неориентированный граф.

Определение 6.7: Маршрутом называется конечная или бесконечная последовательность ребер (...,e 0,e1,...,en,...) такая, что каждые два ребра ei-1 и ei имеют общую инцидентную вершину (т.е. являются смежными).

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

Определение 6.8: Вершина v0, инцидентная е1 и не инцидентная е2 , называется началом маршрута.

Если какие-либо ребра еj и еj+1 являются кратными, то в маршруте необходимо указать одно из них.

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

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




Пусть маршрут M(е1,...,еn) имеет начало v0 и конец vn. Его называют соединяющим вершины v0 и vn.

^ Длиной маршрута М является количество входящих в него ребер. Если v0 = vn, то маршрут называется циклическим.

Отрезок маршрута (еi,еi+1,...,еj) также является маршрутом и называется участком маршрута М.

^ Определение 6.9:. Маршрут М называют цепью, если каждое ребро в нем встречается не более одного раза. Маршрут является простой цепью, если любая вершина графа инцидентна не более чем двум ребрам (Рис.6.11.)


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

Но фактически циклом (соответственно, простым циклом) считают циклически упорядоченное множество ребер, в котором два соседних ребра имеют общую инцидентную вершину. Т.о. последовательность (e1,e2,e3,e4),(e2,e3,e4,e1),(e3,e4,e1,e2),(e4,e1,e2,e3) считают одним и тем же циклом.

Участок цепи, или цикла, является цепью. Участок простой цепи, или цикла - простой цепью.
^ § 6.7: Связные компоненты графа

Определение 6.10:. Вершины v’ и v’’G называются связными, если существует маршрут М с началом в v’ и концом в v’’.

Пусть вершина vG инцидентна более чем двум ребрам маршрута М, связывающего v’ и v’’. И пусть ei - первое из этих инцидентных ребер, а ej - последнее (j>i+1).

Тогда из маршрута М можно удалить участок от i+1-го ребра до j -1-го. Получим новый маршрут М’=(e1,...,ei,ej,...,en). Если М’ - не простая цепь, то этот процесс можем повторять до тех пор, пока не получим простую цепь. В конце концов, получим простую цепь М*, связывающую v’ и v’’ (рис.6.12). Т.о. связанные маршрутом вершины связаны и простой цепью.



Если вершина vG связана с вершиной v’G, то считается, что она связана и сама с собой.

Пусть вершины v и v’ связывает маршрут М(e1,...,en). Тогда вершины v и v связывает маршрут М(e1,...,en,...,e1). Обычно считают, что и изолированная вершина связана сама с собой. Следовательно, отношение связности 2-х вершин, заданное на множестве вершин графа G, рефлексивно. Оно так же симметрично и транзитивно. Т.о., отношение связности является отношением эквивалентности, и определяет разбиение множества вершин V на подмножества Vi . Вершины одного и того же подмножества Vi связаны друг с другом, а вершины принадлежат разным подмножествам Vi и Vj не связанны. Поэтому в графе G не будет ребер, концы которых принадлежат различным множествам Vi и Vj. Следовательно граф G может быть представлен в виде объединения подграфов G=  G(Vi), которые называются связными компонентами графа.

Определение 6.11: Граф G называется связанным, если все его вершины связаны между собой.

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

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

Рассмотрим теперь ориентированный граф G. Вершина v орграфа достижима из вершины u , если существует ориентированный маршрут (путь), исходящий из вершин u и заходящий в вершинy v.

Определение 6.12:. Орграф называется сильно связанным, если любая его вершина достижима из любой другой вершины.


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

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

Определение 6.14: Орграф называется слабосвязанным, если его канонический граф является связанным.

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

Из сильной связанности графа следует односторонняя связанность, а из нее – слабая связанность графа (Рис. 6.13).
^ § 6.8: Расстояния


Пусть G - связанный неориентированный граф, вершины v’, v’’G. Тогда существует связывающая эти вершины простая цепь М(e1,...,eg).

Если количество ребер g этой цепи не является минимально возможным, то существует цепь М(e1,...,eg’), связывающая те же вершины v’ и v’’ и имеющая меньшее число ребер (g’
Определение 6.15: Минимальная длина простой цепи с началом в v’ и концом в v’’ называется расстоянием d(v’, v’’) между вершинами v’ и v’’.

Т.к. каждая вершина связана сама с собой, то d(v,v)=0.

Рассмотренное d(v’, v’’), где v’ и v’’G, удовлетворяет следующим аксиомам :

1.d(v’,v’’)  0 , d(v’,v’’)=0v’=v’’

2.d(v’,v’’)=d(v’’,v’)

3.d(v’,v’’)+d(v’’,v’’’)  d(v’,v’’’) - неравенство треугольников.

^ § 6.9: Диаметр, радиус и центр графа

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

Определение 6.16: Диаметром графа G называется величина, равная d(G)= (d(v’,v’’)) , v’, v’’G.

Кратчайшие простые цепи, связывающие вершины v’ и v’’, с максимальным расстоянием между ними называется диаметрально простыми цепями.

Пусть v - произвольная вершина графа G. Максимальным удалением в графе G от вершины v называется величина r(v )= (d(v,v’)).

Определение 6.17: Вершина v называется центром v,v’G графа G, если максимальное удаление от нее принимает минимальное значение, т.е. r(G)= (r(v)).

Определение 6.18:. Максимальное удаление r(G) называется радиусом графа, а любая кратчайшая цепь от центра v до максимально удаленной от него вершины v называется радиальной цепью.

Центр не обязательно единственный. Так, в полном графе КIVI, в котором любые вершины v’ и v’’ соединены ребром, радиус равен 1, а любая вершина является центром.




Для графа, изображенного на рис.6.14 имеем:

d(G)=3, r(v1)=3, r(v2)=2, r(v3)=2, r(v4)=2, r(v5)=3, r(G)=2, v1, v2, v3- центры графа G.

^ § 6.10: Эйлеровы и гамильтоновы цепи и циклы

Рассмотрим задачу о кенигсбергских мостах. Необходимо выйти из какой-либо части города, пройти по каждому мосту не более одного раза, побывав во всех частях города, и вернуться в исходную часть города (рис 6.15.).

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

Такой цикл называется эйлеровым, а графы, содержащие эйлеровы циклы, называются эйлеровыми графами.


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

^ Теорема 6.1 (Эйлера):. Конечный неориентированный граф G является эйлеровым тогда и только тогда, когда он связан и степени всех его вершин являются четными.

Следовательно, задача о кенигсбергских мостах не разрешима.

Определение 6.19: Эйлерова цепь – это цепь, включающая все ребра одного не ориентированного графа G, но имеющая различные начало и конец v’ и v’’.

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

Чтобы в конечном орграфе существовала эйлерова цепь необходимо и достаточно, чтобы 1(v)=2(v).

Определение 6.20: Гамильтоновым циклом называется простой цикл, проходящий через все вершины графа.

Такой цикл существует не всегда. Через любые 2-е вершины графа может проходить простой цикл (графа G является циклическим связанным), а гамильтоновый цикл при этом отсутствует (рис.6.16).

^ Теорема 5.2 (Теорема Дирака): Если граф G= , |V|3, является связным и степень каждой вершины viV, (vi), где - ближайшее целое число, то граф является гамильтоновым.



^ § 6.11: Операции над частями графа и графами

Пусть Н - часть графа G.

Дополнение части Н до графа G определяется множеством всех ребер графа G, не принадлежащих Н.

Пусть даны две части Н1 и Н2.

Объединением Н1Н2 называется граф, множество вершин которого V1V2 , а множество ребер Е1Е2.

Пересечением Н1Н2 называется граф с множеством вершин V1V2 и ребер Е1Е2.

Части Н1 и Н2 не пересекаются по вершинам, если они не имеют общих вершин, а следовательно и общих ребер. Объединение не пересекающихся по вершинам частей называются прямой суммой по вершинам.

Части Н1 и Н2 не пересекаются по ребрам , если Е1Е2=0. Например, для любой части и Н не пересекаются по ребрам.

Рассмотрим операции над графами.

Пусть даны графы G1= и G2=.

1) Объединение двух графов - граф G1G2=

2) Симметрическая разность двух графов - граф G1 G2=

3) Сумма двух графов - граф G1 + G2= G1G2KIV1I,IV2I

При построении суммы графов определяется их объединение и каждая вершина viV1, не вошедшая в пересечение V1V2 соединяется со всеми вершинами из множества V2\(V1V2 ), а каждая вершина vjV2, не вошедшая в пересечение V1V2 соединяется со всеми вершинами из множества V1\(V1V2).

Будем говорить, что вершина v конусирует граф G, если она смежна со всеми вершинами графа G.

Вершины, не вошедшие в пересечение V1V2 при суммировании графов G1 и G2 конусирует соответственно V1\(V1V2) и V2\(V1V2 ) .

  1. Прямое произведение G1  G2= .

Множество вершин данного графа содержит пары вида (vw), где vV1 и w V2 , а множество Е содержит ребра, соединяющие вершины (vv) и (v’v’) , если v и v’1 смежны в графе G1 , а v2 и v’2 cмежны в графе G2 (Рис.6.17).

Под операцией удаления вершины из графа G понимается операция, заключающаяся в удалении некоторой вершины v из множества V и инцидентных ей ребер.

Под операцией удаления ребра из графа G= понимается удаление соответствующей двойки отношения из .

Если существует такая вершина в графе G, удаление которой превращает связный граф в несвязный, то она называется точкой сочленения.

Ребро с таким же свойством называется мостом.

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




^ § 6.12: Деревья и лес

Неориентированное дерево - это связный неориентированный граф, не содержащий циклов, а следовательно, петель и кратных ребер.

Несвязный неориентированный граф без циклов называется лесом (Рис.6.18).

Любая часть леса или дерева также не содержит циклов и кратных ребер, т.е. является деревом или лесом. Любая часть дерева представляет собой дерево.

Любая цепь в дереве является простой.

Вершина v графа G называется концевой или висячей, если её локальная степень равна 1. Инцидентное концевой вершине ребро так же называется концевым.

Если конечное дерево состоит более чем из одной вершины, то оно содержит хотя бы две концевые вершины и хотя бы одно концевое ребро.




^ Цикломатическим числом графа называется число равное r+m-n, где m- число ребер, n- число вершин, r- число компонент связности графа.

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

Рассмотрим случай орграфа.

Пусть в графе G отмечена вершина v0. Ее называют корнем дерева G, а само дерево - деревом с корнем. В таком дереве можно естественным образом ориентировать ребра в направлении от корня и получим ориентированное дерево.

Если изменить направление всех ребер на противоположное ( к корню ), то получим тоже орграф, ориентированное дерево, которое называется сетью сборки (Рис.6.19.).




В каждую вершину ориентированного дерева входит только одно ребро, в корень не входит ни одно ребро. В любом конечном дереве число вершин на 1 больше числа ребер.

Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.
^ § 6.13: Взвешенные графы

Определим понятие взвешенного (помеченного) графа. При этом сопоставим каждой вершине viV графа G = некоторый вес wiW, а каждому ребру eiE также сопоставим некоторый вес piP.

Т.о., получим граф, содержащий взвешенные вершины (vi,wi) и взвешенные ребра (ei, pi), т.е. граф G =.

Строго говоря, G представляет собой уже не граф, а функцию, определенную на вершинах и ребрах графа, т.е. если f:VW, g:EP, то G = .

Пример. В графе помеченными могут быть только вершины, или только ребра, или и вершины и ребра (Рис. 6.20).

Взвешенный граф полностью определяется матрицей инцидентностии матрицами весов:

Sv = и SE =



^ Поиск остовного дерева минимальной длины во взвешенном графе.

Данный алгоритм (Алгоритм Крускаля) применяется при разработке различных коммуникационных сетей. Суть его состоит в том, чтобы сумма весов ребер полученного дерева была минимальной.

Пусть дан граф G с помеченными ребрами.

  1. Выбирают ребро с минимальным весом.

  2. Из оставшихся выбирают ребро с минимальным весом.

  3. Проверяют, не образует ли выбранное ребро цикла с выбранными ранее ребрами. Если да, то отбрасывают его и переход к п 4 . Если нет, то включают его в отобранную совокупность ребер.

  4. Если не все вершины графа еще связаны, то повторяем все действия, начиная с п.2. В противном случае – конец алгоритма.

Пример: В заданном взвешенном графе (Рис. 6.21) выделить остовное дерево минимальной длины.

Ребра расположены в порядке возрастания следующим образом: AC, FG, EF, EH, IJ, CD, GJ, AD, DG, BC, CF, FI, HI, AB, BE, FD, BF, CH. Алгоритм Крускаля позволяет последовательно сохранять ребра AC, FG, EF, EH, IJ, CD,CJ, а ребро AD исключается, т.к. оно образовывало бы цикл с уже включенными в дерево ребрами AC и CD. Затем добавляются ребра DG и BC. Как можно заметить, все вершины уже связаны и минимальное дерево получено.




^ § 6.14: Планарные графы

Определение 6.21:. Граф G называется планарным, если он может быть изображен на плоскости таким образом, чтобы его ребра не пересекались. Такой рисунок называется картой графа (Рис.6.22)


Графы К5 и К3,3 не являются планарными (Рис.6.23).


Карта G называется связной, если граф G связный.

Каждая картина делит плоскость R2 на области, ограниченные и неограниченные.

Множество таких областей обозначаются через R.

Теорема 6.3(Эйлера): Для произвольной связной карты выполняется равенство : IVI+IRI - IEI = 2 (Рис.6.24).




Каждая область карты ограничена замкнутым маршрутом .

Определение 6.22: Пусть G= - планарный граф. Для карты G определим r - степень области r, как длину замкнутого маршрута, ограничивающего область r.

Для графа, изображенного на рис. 6.20, имеем:

r1=3 r3=3

r2=3 r4=3

Имеют место следующие соотношения:

r=2 |E|

если |V|3, то |E|3|V| - 6

63*4-6

66

Рассмотрим операцию стягивания графа G как слияние двух смежных вершин после удаления ребра между ними.

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

^ Теорема 6.4 (Куратовского):. Граф является планарным, тогда и только тогда, когда он не содержит подграфов, стягиваемых к К5 и К3,3.

Определение 6.23: Раскраской графа G называется задание цвета вершинам таким образом, что если вершины v и w- смежные, v,w V, то они имеют различные цвета.

Величина (G) называется хроматическим числом графа G и равна минимальному числу цветов, необходимых для раскраски графа.

Граф G называется р-хроматическим, если его вершины можно раскрасить р различными цветами.

Одно-хроматический граф  тривиальный граф. Дву-хромотический граф тогда и только тогда, когда он не содержит циклов нечетной длины.

Теорема 6.5: Для любого планарного графа G хроматическое число не более 4.

Пусть М - карта графа G. Определим карту M’ следующим образом: внутри каждой области карты М выберем внутреннюю точку. Если две области имеют общее ребро, то между выбранными внутренними точками проведем дугу. Этот процесс определяет карту М’, называемую двойственной карте М’ (Рис. 6.25).




Раскраска карты М’ соответствует раскраске областей карты М т.о., что области, имеющие общее ребро, имеют разные цвета.

Теорема 6.6: Если области карты М необходимо раскрасить таким образом, чтобы смежные области имели различные цвета, то необходимо не более 4-х цветов.

Толщиной графа G называется наименьшее число планарных графов, объединение которых дает G. Толщина планарного графа равна 1. Нижняя оценка толщины t(G) графа G= определяется неравенством:

t(G)1+, где -целая часть, |V|=n, i – степень i-ой вершины.
^ § 6.15: Задача поиска маршрутов (путей) в графе (орграфе)

Рассмотрим алгоритм поиска маршрута в связном графе G=, соединяющего вершины v,wV причем vw.

^ Алгоритм Тэрри:

Если, исходя из вершины v и осуществляя последующий переход от каждой доступной вершины к смежной ей вершине, следовать следующим правилам 1-4, то всегда можно найти маршрут в связанном графе, соединяющим две заданные вершины.

Правило 1: Идя по произвольному ребру, отмечать направление, в котором оно было пройдено.

Правило 2: Исходя из некоторой вершины v' всегда следовать только по тому ребру, которое не было пройдено или пройдено в противоположном направлении.

Правило 3: Для всякой вершины v'v отмечать первое заходящее в v' ребро, если v встречается в первый раз.

Правило 4: Исходя из некоторой вершины v'v по первому заходящему в v' ребру идти лишь тогда, когда нет другой возможности.

Пример:











а) б)


Найти маршрут из v1 в v5 (рис.6.26)

Знаком  помечены первые заходящие в вершины ребра возле той вершины, в которую это ребро заходит. По рисунку видно, что маршрут имеет вид: v1 v2 v1 v3 v4 v3 v5.

После того как из v1 зашли в v3 по правилу 4 в v1 вернуться не можем, т. к. имеются другие возможности, а ребро v1v3 является первым заходящим в v3 ребром. После того как из v4 зашли в v3 по дуге 5 по правилу 2 в v4 вернуться не можем, а в силу правила 4 не можем идти и к v1, остается идти к v5.

Замечание 6.1: Алгоритм Тэрри остается в силе, когда G связный граф.

Замечание 6.2: Если G не связный псевдограф, то с помощью алгоритма Тэрри, исходя из любой вершины v и помечая пройденные вершины и ребра, можно выделить компоненту связанности псевдографа, содержащую вершину v. Алгоритм закончит свою работу, когда в первый раз невозможно будет выполнить правило 2, т. е. пришли в вершину u такую, что все инцидентные ей ребра пройдены в направлении из u, при этом получим, что u = v.

Замечание 6.3: Из полученного с помощью алгоритма Тэрри маршрута всегда можно выделить простую цепь, соединяющую v и w.

^ § 6.16: Поиск путей (маршрутов) с минимальным числом дуг (ребер)

Путь в орграфе D из вершины v в вершину w, где vw называется минимальным, если он имеет минимальную длину среди всех путей в орграфе из v в w.

Рассмотрим свойства минимального пути(маршрута):

Утверждение 6.1: Любой минимальный путь (маршрут) является простой цепью.

Утверждение 6.2: (о минимальности подпути минимальность пути) Пусть М=v1, ..., vk - минимальный путь (маршрут) из v1 в vk, где v1vk, тогда для любых номеров i, j таких, что 1 i j  k путь (маршрут) M0=vi, vi+1, ..., vj также является минимальным .

Пусть D= орграф, где vV , V1V.

Mножество D(v)=w называется образом вершины v.

Mножество D1(v)= (w, v) E прообраз вершины v.

D(V1)= D(v)  образ множества вершин V1.

D(V1) Dv) прообраз множества вершин V1.

Пусть G= граф, где vV , V1V.

Mножество G(v)=w называется образом вершины v.

G(V1)= G(v)  образ множества вершин V1.

Рассмотрим алгоритм поиска минимального пути в орграфе с n   вершинами из v в w, где vw.

Алгоритм фронта волны:

Шаг 1: Помечаем вершину v индексом 0, затем помечаем вершины принадлежащие образу вершины v индексом 1. Множество вершин с индексом 1 обозначаем FW1(v)  фронт волны 1-го уровня. Полагаем k=1.

Шаг 2: Если FWk(v)= или k= n и wFWk(v), то вершина w недостижима из v и алгоритм прекращает работу, иначе шаг 3.

Шаг 3:Если wFWk(v) перейти к шагу 4, иначе существует путь из v в w длиной k и этот путь является минимальным. При этом последовательность вершин v w1 w2 ... wk-1 w, где

wk-1FWk(v)D(w)

wkFWk(v) D(wk) (6.1)

.................

w1FW1(v) D(w2)

и является искомым минимальным путем из v в w. На этом алгоритм прекращает свою работу.

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

Замечание 6.4: Множество FWk(v) называют фронтом волны k-ого уровня.

Замечание 6.5: Вершины w1 w2 ... wk-1 из (6.1) могут быть выделены неоднозначно, т. е. могут существовать несколько минимальных путей из v в w.

Пример: Определить минимальный путь из v1 в v6 в орграфе, заданном матрицей смежности.





v1

v2

v3

v4

v5

v6

v1

0

0

0

1

1

0

v2

1

0

0

1

1

1

v3

1

1

0

1

1

1

v4

0

1

1

0

1

0

v5 v4 v4

1

1

1

1

0

0

v6

1

1

1

1

1

0


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

FW1(v)={v4, v5}

FW2(v)=D(FW1(v))\{v1, v4, v5}={v2, v3}

FW3(v)=D(FW2(v))\{v1, v2, v3, v4, v5}={v6}

v6 FW3(v), т. е. существует путь из v1 в v6 длиной 3 этот путь минимальный.

Определим множество

FW2(v)D (v6)={v2, v3}{v2, v3}={v2, v3} Выберем любую вершину из найденного множества, например v3.

Далее определяем множество

FW1(v) D (v3)={ v4, v5}{ v4, v5, v6}={ v4, v5}

Из полученного множества выбираем любую вершину, например v5. Таким образом получим, что искомым минимальным путем будет v1 v5 v3 v6.

Замечание 6.6: Если выражения D( ), D-1( ) заменить на G( ), G-1( ), то данный алгоритм применим и к неориентированному графу.

^ § 6.17: Минимальный путь (маршрут) во взвешенном орграфе (графе)

Пусть каждой дуге взвешенного орграфа D= приписан некоторый вес  число l(e), где eE.

Для любого пути М через l(M) обозначим сумму длин входящих в него дуг и назовем длиной пути М во взвешенном орграфе.

Любой не взвешенный граф можно считать взвешенным, длина каждой дуги которого равна 1.

Пусть во взвешенном орграфе существует путь из v в w, где vw. Он называется минимальным, если имеет минимальную длину среди всех возможных путей из v в w.

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

1) Если для любой дуги eE l(e)>0, то любой минимальный путь (маршрут) является цепью.

2) Если v1, ..., vk минимальный путь (маршрут) из v1 в vk, то для любых i, j таких, что 1 i  j  k путь (маршрут) vi, vi+1, ..., vj также минимальный.

3) Если v, ..., u, w минимальный путь (маршрут) из v в w, содержащий не более k+1 дуг (ребер), то v, ..., u также минимальный путь (маршрут), содержащий не более k дуг (ребер).

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

Если орграф содержит ребро с отрицательным весом, то минимального пути может и не существовать.

Замечание 6.7: Если необходимо найти максимальный путь, то достаточно будет поменять знаки длин дуг на противоположные.

Пусть D= взвешенный орграф с n2 дугами. Введем величины i(k) , где i =1, 2, ..., n k=1, 2, ...  длина минимального пути из v1 в vi, содержащего не более k дуг. Если таких путей нет, то i(k) =. Если произвольную вершину v считать путем нулевой длины из v в v, то можем ввести величины:

1(0)=0 и i(0)= для i =2, 3, ..., n. (6.2)

Рассмотрим квадратную матрицу nn каждый элемент которой

Cij= (6.3)

Такую матрицу назовем матрицей длин дуг взвешенного орграфа.

Утверждение 6.3: При i =2, ..., n, k0 выполняется равенство

i(k+1)={j(k)+ Cj i}, (6.4)

a при i =1, k0 справедливо равенство

1(k+1)=min{0, (j(k)+ Cj,1)} (6.5)

Используя данное утверждение можно описать алгоритм нахождения таблицы значений величин i(k) в виде матрицы из i строк и (k+1) столбцов, начиная с k=0 и увеличивая k по мере необходимости.

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

Утверждение 6.4: Из всякого замкнутого пути отрицательной длины можно выделить простой цикл отрицательной длины.

Утверждение 6.5:. Если во взвешенном орграфе отсутствуют простые циклы отрицательной длины, то в нем нет и замкнутых путей отрицательной длины.

Утверждение 6.6: Во взвешенном орграфе, в котором нет простых циклов отрицательной длины, из всякого незамкнутого пути можно выделить простую цепь с теми же началом и концом, длина которой не превосходит длину исходного пути.

Рассмотрим алгоритм, который позволяет по таблице i(k), где i =2, ..., n k=0, 1,...,n-1, определить минимальный путь во взвешенном орграфе из v1 в любую достижимую вершину, причем из всех возможных путей выбирается путь с минимальным числом дуг.

Алгоритм Форда-Беллмана нахождения пути во взвешенном орграфе из v1 в v i11

Шаг 1: Пусть таблица величин i(k) где i =2, ..., n k=0, 1, ... уже составлена. Если =  то вершина vi не достижима из v1 и алгоритм заканчивает свою работу. В данном алгоритме принимают, что l(e), eE  конечное число.

Шаг 2: Пусть < тогда выражает длину любого минимального пути из v1 в vi1. Определим минимальное число k11 при котором выполняется равенство: = . По определению чисел i(k) получаем, что k1 - это минимальное число дуг в пути среди всех минимальных путей из v1 в v.

Шаг 3: Последовательно определяем номера i2, i3, ..., i

+ C,=

+ C,= (6.6)

.......................

+C=

эти номера находим в соответствии с равенством (2). С учетом того, что =< имеем, что C,<, ..., C, , откуда, используя (6.2) получаем ребро(v,v),...,(,)E, l(v,v)= C,,..., l(,)= C,

=0, i=1, = v1. (6.7)

Складывая (6.6) и учитывая (6.7) имеем, что длина маршрута l(v1, , ..., v, v)=, т. е. v1, , ..., v,v  искомый минимальный путь из v1 в v в орграфе D с k1 дугами.

Замечание 6.8: Номера i2, i3,...i, удовлетворяющие (6.6) могут быть выделены неоднозначно, т. е. может существовать несколько минимальных путей из v1 в v.

Замечание 6.9:Данный алгоритм можно модифицировать т.о., чтобы определить минимальный путь из v1 в v , содержащий не более k0 дуг, где k01 – заданное число. Для этого в алгоритме вместо необходимо рассматривать . При этом, если в орграфе D имеются простые циклы отрицательной длины, может выполняться неравенство .

Замечание 6.10: Алгоритм Форда-Беллмана и его модификация, описанная выше, после соответствующего изменения в терминологии и обозначениях применимы и к неориентированному графу.

Пример: Определим минимальный путь из v1 в v6 во взвешенном орграфе (рис.6.27), матрица длин дуг которого имеет вид:







v1

v2

v3

v4

v5

v6
















v1





5

5

2

12

0

0

0

0

0

0

v2











2





7

5

5

5

v3



2











5

3

3

3

3

v4



2











5

4

4

4

4

v5





1

2







2

2

2

2

2

v6















12

12

9

7

7


Величина 6(5) выражает длину минимального пути из v1 в v6. Найдем минимальное число k11 дуг, при котором выполняется равенство 6(5) = 6(k1) Из таблицы получаем k1=4, значит минимальный маршрут будет содержать самое меньшее 4 дуги. Определим теперь последовательность номеров i1, i2, ..., i5, где i1=6, в минимальном пути, удовлетворяющую (6.6). Из таблицы получаем, что это последовательность номеров 6,2,3,5,1, так как:

2(3)+С2,6=5+2=7=6(4)

3(2)+С3,2=3+2=5=2(3)

5(1)+С5,3=2+1=3=3(2)

1(0)+С1,5=0+2=2=5(1).

Тогда v1 v5 v3 v2 v6  минимальный путь из v1 в v6, содержащий наименьшее число дуг.

119-105-publichnij-otchyot-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-pospelihinskaya-selskaya-srednyaya-obsheobrazovatelnaya.html
11atlanta-tekst-glavi-nahoditsya-tut12odin-iz-nashih-mark-olshejker-dzhon-duglas-ohotniki-za-umami-fbr-protiv-serijnih-ubijc.html
11problemi-mediavospriyatiya-i-razvitiya-auditorii-v-oblasti-mediakulturi-monografiya-chast-1.html
12-2-problemi-klassifikacii-regionov-tema-vvedenie-v-ekonomicheskuyu-teoriyu-2.html
12-alekseev-bg-bavlov.html
12-dekabrya-v-0900-informacionnij-byulleten-administracii-sankt-peterburga-47-648-7-dekabrya-2009-g.html
  • learn.bystrickaya.ru/glava-18-obshie-metodi-i-sredstva-vospitaniya-literatura-dlya-samostoyatelnoj-raboti-20.html
  • holiday.bystrickaya.ru/nekommercheskaya-tom-pervij-kanal-novosti-03-09-2008-pankratova-yuliya-12-00-9.html
  • studies.bystrickaya.ru/lord-skiminok-mladshij-odin-za-drugim-podnimalis-oni-na-pomost-i-derzali-kosnutsya-rukoyati-mecha-bez-imeni-stranica-2.html
  • kolledzh.bystrickaya.ru/42-chasi-modelnogo-vremeni-konspekt-lekcij-dlya-studentov-specialnosti-080801-65-prikladnaya-informatika-v.html
  • literature.bystrickaya.ru/duhovno-iravstvennoe-stanovlenie-rebenka-v-sovremennom-rossijskom-obshestve-semya-ditya-socium.html
  • laboratornaya.bystrickaya.ru/rabota-s-himicheskimi-reaktivami-metodicheskie-rekomendacii-k-laboratornim-rabotam-po-kursu-himiya.html
  • spur.bystrickaya.ru/kurs-1-nazva-disciplni-druga-nozemna-mova-przvishe-vikladacha.html
  • obrazovanie.bystrickaya.ru/programma-kursa-i-metodicheskie-rekomendacii-samara-2008-pechataetsya-po-resheniyu-redakcionno-izdatelskogo-soveta-samarskogo-filiala-gosudarstvennogo-obrazovatelnogo.html
  • holiday.bystrickaya.ru/neskolko-idej-dlya-knizhnih-vistavok-otchet-o-prodelannoj-rabote-104-po-proektu-knigi-deti-i-cveti-104-vpoiskah-informacii-106.html
  • uchit.bystrickaya.ru/uchebnaya-rabota-nauchno-issledovatelskaya-rabota-22-uchebno-vospitatelnaya-rabota-34-uchebno-organizacionnaya-rabota.html
  • literatura.bystrickaya.ru/rekomendacii-visshim-organam-finansovogo-kontrolya-25-7-zaklyuchenie-i-vozmozhnie-temi-dlya-obsuzhdeniya-na-kongresse-eurosai-31.html
  • knowledge.bystrickaya.ru/napravleniya-podgotovki-po-kotorim-idyot-obuchenie-v-aspiranture.html
  • reading.bystrickaya.ru/men-basheva-majra-mazhitizi-1972-zhili-5-mamirda-gurev-oblisi-tez-audani-kirov-seloli-sovetnde-dniege-keldm.html
  • portfolio.bystrickaya.ru/petrushka-enciklopediya-specij-izrailskoj-kuhni.html
  • shpargalka.bystrickaya.ru/uchebnoe-posobie-2004-meshkov-n-a-issledovanie-sistem-upravleniya-uchebnoe-posobie-stranica-21.html
  • urok.bystrickaya.ru/proekt-stranica-4.html
  • zadachi.bystrickaya.ru/sotrudniki-alkon-stali-donorami-dlya-detej-postradavshih-v-dtp-horoshie-novosti-s-evgeniej-korobkovoj-24.html
  • tetrad.bystrickaya.ru/voprosi-k-ekzamenu-po-antichnoj-literature-2005-2006-uch-g-formirovanie-polisnoj-sistemi-v-drevnej-grecii-kak-osnova-dlya-razvitiya-demokratii-i-grazhdanstvennosti.html
  • learn.bystrickaya.ru/glava-22-triumf-anzheliki-ann-i-serzh-golon-chast-pervaya-shepetilnost-somneniya-i-muki-shevale-glava-1.html
  • ucheba.bystrickaya.ru/proektnaya-iissledovatelskaya-deyatelnost-uchashihsya.html
  • school.bystrickaya.ru/i-3-vakcinologiya-nauka-o-lekarstvennih-kniga-g-p-chervonskoj-privivki-mifi-i-realnost.html
  • paragraph.bystrickaya.ru/metodi-refnansuvannya-centralnim-bankom-komercjnih-bankv.html
  • teacher.bystrickaya.ru/gosduma-rf-monitoring-smi-24-noyabrya-2006-g.html
  • lektsiya.bystrickaya.ru/proekt-programmi-kandidatskogo-ekzamena-po-specialnosti-05-05-04-dorozhnie-stroitelnie-i-podemno-transportnie-mashini.html
  • occupation.bystrickaya.ru/montazh-i-tehnicheskaya-ekspluataciya-promishlennogo-oborudovaniya-v-pishevoj-promishlennosti-stranica-4.html
  • nauka.bystrickaya.ru/uprazhneniya-po-vosstanovleniyugrammaticheskogo-stroya-rechi-kniga-dolzhna-yavitsya-vazhnim-podsporem-dlya-rodstvennikov.html
  • upbringing.bystrickaya.ru/konspekt-uroka-literaturi-v-10-klasse-po-teme-nikak-mi-iz-vojni-ne-vijdem.html
  • klass.bystrickaya.ru/8-termicheskie-cehi-termicheskie-cehi-po-pozharnoj-opasnosti-otnosyatsya-k-kategorii-g.html
  • student.bystrickaya.ru/24-prognoz-potrebleniya-ozonorazrushayushih-veshestv-otchet-programma-001-obespechenie-deyatelnosti-upolnomochennogo.html
  • textbook.bystrickaya.ru/kak-stat-hozyainom-pridomovoj-territorii-yazikom-zakona-statej-89-zemelnogo-kodeksa-ukraini-predusmotreno-chto-v-obshej-sovmestnoj-sobstvennosti-nahodyatsya-zemelnie-uchastki-v-tom-chisle-i-sovladelcev-zhilogo-doma.html
  • lesson.bystrickaya.ru/uran-soma-planeta-sonyachno-sistemi.html
  • college.bystrickaya.ru/0-vigre-prinimayut-uchastie-dve-komandi-po-tri-igroka-kazhdaya-komanda-mozhet-imet-maksimum-tri-zapasnih-igroka-igra-proishodit-v-sportivnom-zale-na-polu-k.html
  • knowledge.bystrickaya.ru/mifi-drevnej-grecii-verovaniya-drevnih-grekov.html
  • thescience.bystrickaya.ru/investicionnoe-proektirovanie-3.html
  • uchit.bystrickaya.ru/struktura-filosofskogo-znaniya.html
  • bool(false)
    © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.