ivanstudent

Путь к Файлу: /Дискретная математика. Часть 2 / 189 / 3.DOC

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   1
Пользователь:   ivanstudent
Добавлен:   24.12.2014
Размер:   223.5 КБ
СКАЧАТЬ

33

где 3

3

Граф Бержа определяется однозначно с точностью до индивидуализации ребер заданием на Х бинарного отношения

3 (x,y)= $ и P(x,y.u).

Вместо отношения 3 обычно задают отображение Г, относящее каждой вершине хÎХ подмножество

Гх={yïyÎx&3(x,y)}.

Поэтому граф Бержа можно обозначать через (Х,Г), а также через (X,U). Например, для графа представленного на рисунке

 

3

3

      X={1,2,3,4},                        

 

2.5. Части с экстремальными свойствами в графах

 

Подграф L/ графа L называется  максимальным полным (пустым) подграфом, если он полный (пустой) и не существует такого подграфа, который содержал бы L/ не совпадая с ним, и тоже был бы полным (пустым).

Подграф L/ называется наибольшим полным (пустым) подграфом, если среди всех полных (пустых) подграфов он содержит наибольшее число вершин.

Число e(L), характеризующее число вершин наибольшего пустого подграфа называется  неплотностью графа.

Число j(L), характеризующее число вершин наибольшего полного подграфа, называется плотностью графа.

В иной терминологии e(L) называется числом внутренней устойчивости.

Дополнительным графом для обыкновенного графа L называется обыкновенный граф 3с тем же множеством вершин и новым множеством ребер

3

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

 

3                 3                                                   3

             

 

2                           4                    2                                 4      

 

 

  

1                          5                       1                                5

 

             L                                                            3

 

Для графа L и его дополнительного графа 3 очевидно, что

j(L)=e( 3); e(L)=j( 3).

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

Пример 2.5.1. Задача о восьми ферзях.

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

Эта задача сводится к нахождению наибольшего пустого подграфа в графе с 64 вершинами (клетки шахматной доски), где клетки х и у смежны, если находятся в одной и той же горизонтали, вертикали или диагонали. Эта задача имеет 92 решения.

Пример 2.5.2. Пусть х - множество лиц, а смежность вершины х и у означает согласие между соответствующими лицами. Требуется найти общество с наибольшим числом взаимно согласных членов, т.е. “максимальную клику”.

Пример 2.5.3. Задача об информационной емкости множества сигналов.

Рассматривается простейший случай одного передатчика, который может передавать четыре сигнала х1, х2, х3, х4; при приеме каждый из этих сигналов может быть истолкован неоднозначно: сигнал х1 дает у1 или у3, сигнал х2 дает у1 или у2 и т.д. (рисунок 2.5.1.а)

 

 

33    x1                               y1                     x1                               x2

 

  

  x2                                 y2                

 

  x3                                 y3

 

  x4                                 y4

 

                 а)                                              б)

Рис. 2.5.1      

 

Какое наибольшее число сигналов можно принять, не рискуя спутать их друг с другом? Задача сводится к  определению наибольшего пустого подграфа L (рисунок 2.5.1 б), где две вершины смежны, если соответствующие системы можно спутать при приеме.

Примером части с экстремальными свойствами является его опора.

Опорой графа L=(x,u,p) называется такой его подграф L’=(x’,u’,p’), что всякое ребро uÎU инцидентно по крайней мере одной вершине х’.

Количество s(L) вершин наименьшей опоры называется опорным числом графа L.

Пример 2.5.4. Задача о часовых. В тюрьме около каждой камеры может быть поставлен часовой. Как, используя наименьшее число часовых обеспечить просматриваемость всех коридоров.

3
 


                                                                        

                                                                    

                                                      

                                                             

 

 

 

                                                     

Рис. 2.5.2

 

Ясно, что подграф L’ есть опора графа L тогда и только тогда, когда подграф L’’, порожденный множеством Х\Х’ остальных вершин, пуст, и что опора L’ минимальна в том и только в том случае, если соответствующий пустой подграф L” максимален (в частности наименьшей опоре отвечает наибольший пустой подграф). Отсюда следует, что задачи выявления максимальных пустых подграфов и минимальных опор равносильны и что e(L) +s(L)=n(L). Для примера (рисунок 2.5.2) вершины множества Х’ обведены кружком, а вершины, образующие опору - квадратом.

Наименьший всесмежный подграф, или наименьший внешне неустойчивый подграф L’=(x’,u’,p’), который обладает тем свойством, что любая вершина из Х”=Х\Х’ смежна по крайней мере с одной вершиной Х’. Размер наименьшего всесмежного графа называется числом внешней устойчивости b(L).

Пример 2.5.5. Найти наименьшее число часовых, необходимое для наблюдения за всеми камерами.

 

                          x5

3
 


 

    x1                                                                                                        

 

 

 

 

 

                  

 

 

Рис. 2.5.3

 

Пример 2.5.6. Задача о пяти ферзях.

Сколько ферзей достаточно расставить на шахматной доске так, чтобы каждая клетка доски находилась под ударом. Ответ b=5 для ферзей, b=8 для ладей, b=12 для коней, b=8 для слонов.

К задачам рассматриваемого типа сводятся многочисленные практические задачи распределения ресурсов.

Алгоритм Магу-Уэйсмана нахождения максимальных пустых подграфов.

Пусть L=(x,u) - заданный обыкновенный граф с х={x1,x2,...,xn}и с пронумерованным множеством ребер. Символы вершин x1,x2,...,xn добавляются в качестве новых образующих x, h, z, q, полукольца К и расширенную таким образом систему подчиним условиям

q=1, 2=1, xi2=xi, xi+1=1;

а также условиям коммутативности, ассоциативности и дистрибутивности.

Полученное полукольцо включает в себя булеву алгебру Вх=В{x1,x2,...,xn} многочленов от символов хi с коэффициентами из B=B{0,1}.

Можно показать, что в Кх имеет место закон поглощения:

"a,bÎKx(a+ab)=a.

Например,

x1,x2 +x1x2x3x4 =x1x2 (1+x3x4)==x1x2[(1+x3)+x3x4]=x1x2[1+(x3+x3+x4)]=

 =x1x2[1+x3(1+x4)]=x1x2(1+x3)=x1x2.

33Из матрицы инциденций А=||aij|| (i=1,n; j=1,m) графа L на Кх образуем новую матрицу Аx=||aij xi|| и составим произведение

ПL= ПL(x1,x2,...,xn)=3.

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

Подмножество вершин уÎх порождает в L пустой подграф тогда и только тогда, когда для системы {xi0}значения переменных определены условиями:

3xiÏy           xi0=1;

3xiÎy             xi0=0;

Имеет место равенство ПL(xi0, x20 ,..., xn0 )=1.

В  самом деле, для пустого подграфа с подмножеством вершин у необходимо и достаточно, чтобы каждое ребро графа L было инцидентно хотя бы одной вершине из х\у, т.е. чтобы в каждом сомножителе произведения ПL(x1,x2,...,xn) по крайней мере одно из двух слагаемых представляло вершину не из у; но в этом и только этом случае подстановка единиц вместо переменных xi, обозначающих вершины не из у, обратит все произведение ПL в единицу.

Итак, с помощью вычисления конкретных значений произведения ПL в В{0,1} можно для любого заданного подмножества уÎх узнать, является ли порожденный им подграф пустым.

Далее, пользуясь дистрибутивным, ассоциативным и коммутативным законами, раскроем в произведении ПL все скобки и в каждом слагаемом устраним повторения сомножителей с помощью xi=xi2.

И наконец, применяя закон поглощения, приведем всю сумму к минимальной форме, которая, как известно из математической логики, определяется однозначно, ибо в нашем случае нигде не фигурирует операция логического отрицания в В{0,1}. Полученный многочлен обозначим через SL=SL(x1,x2,...,xn). Разумеется, что при любой системе значений {xi} из B(0,1) имеет место:

ПL(xi0, x20 ,..., xn0) = SL(xi0, x20 ,..., xn0).

Каждому слагаемому в SL отнесем подграф, порожденный всеми теми вершинами графа L, которые не фигурируют в качестве сомножителей этого слагаемого. Покажем, что все выбранные таким образом подграфы М12,...,МК - пустые, и ни один из них не есть подграф другого, а всякий пустой подграф графа L содержится хотя бы в одном из них. Действительно, если все переменные в слагаемом, соответствующем Mj(j=1,к) положить равным единице, а остальные переменные положить равными нулю, то SLL=1, откуда Mj - пустой. Если Mj-подграф Ml(j=1,к; l=1,к; l¹j), то все переменные слагаемого, соответствующего Ml присутствовали бы также в слагаемом, отвечающем Мj и тогда второе слагаемое поглощалось бы первым. Наконец, если М=(у,Æ) - произвольный пустой подграф графа L, то составленная для него система значений {xi0}y обращает ПL в единицу, следовательно, в ПL  есть слагаемое, не имеющее сомножителей xi из у, и соответствующий этому слагаемому подграф Mj содержит М.

Следует заметить, что непосредственное раскрытие всех скобок в ПL дало бы 2m(L)  слагаемых, что практически обесценило бы алгоритм. Однако положение спасает то, что закон поглощения можно применять задолго до полного раскрытия.

Рассмотрим пример для графа на рисунке 2.5.4.

3
 

 

 

 

 

 

 

 

 

 

 

 


Чтобы не выписывать матрицы А и Ах, заметим, что произведение ПL можно представить в виде

                                      ПL=П(xi + xj)

{xixj~/JLxixj};{ij/xixj~ÎU},

где умножение идет по всем неупорядоченным парам смежных вершин графа. В нашем случае

 

ПL=(x1+x2)(x1+x8)(x2+x3)(x2+x4)(x2+x5)(x3+x4)(x4+x5)(x4+x6)(x4+x7)(x4+x8)

      (x4+x9)(x5+x6)(x6+x7)(x8+x9).

Полное раскрытие дает 214 слагаемых. Однако, замечая, что в силу закона поглощения всегда

(a+b)(a+c)...(a+p)=a+bc...p,

можно записать

             ПL=(x1+x2x8)(x2+x3x4x5)(x3+x4)(x4+x5x6x7x8x9)(x5+x6)

    (x6+x7)(x8+x9)=(x1+x2x8)(x2+x3x4x5)(x4+x3x5x6x7x8x9)(x6+x5x7)(x8+x9).

Получить итоговую запись можно следующим образом: для i =1,2...  последовательно составляем сомножители вида xi+xj,xk,...,xp, где xj,xk,..,xp все вершины смежные с xi  и обладающие большими номерами; после этого каждую пару сомножителей вида (a+b)(a+c) заменяем сомножителем a+bc.

В полученном выражении для ПL произведение первых двух скобок равно

(x1+x2x8)(x2+x3x4x5)=x1x2+x1x3x4x5+x2x8+x2x3x4x5x8=x1x2+x1x3x4x5+x2x8.

Умножение на третью скобку дает

x1x2x4+x1x2x3x5x6x7x8x9+x1x3x4x5+x1x3x4x5x6x7x8x9+x2x4x8+x2x3x4x5x7x6x8x9=

     =x1x2x4+x1x3x4x5+x2x4x8+x2x3x5x6x7x8x9.

Продолжая этот процесс, получим в итоге:

åL=x1x3x4x5x6x8+x2x3x3x6x7x8x9+x2x4x6x8+x1x3x4x5x7x8+x2x4x5x7x8+

  +x1x3x4x5x6x9+x1x2x4x5x7x9.

Максимально пустые подграфы графа L порождаются следующими подмножествами вершин:

{x2,x7,x9},{x1,x4},{x1,x3,x6,x9},{x2,x6,x9},{x1,x3,x6,x9},

             {x2,x7,x8},{x3,x5,x7,x8},{x2,x6,x8},{x3,x6,x8}.

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

3

3распространенное на всевозможные пары несмежных различных вершин.

Для графа на рисунке 2.5.4  максимальные полные подграфы порождаются множествами вершин:

{x4,x8,x9},{x4,x6,x7},{x4,x5,x6},{x2,x4,x5},{x2,x3,x4},{x1,x8},{x1,x2}.

 

3. СВЯЗНОСТЬ ГРАФОВ

 

3.1. Маршруты, цепи и циклы

 

Рассматриванию подлежат такие свойства графов, которые не меняются при произвольной ориентации звеньев графа, переориентации или дезориентации дуг. Поэтому можно рассматривать только неорграфы, либо изучать только такие свойства графов общего вида L=(x,u,p), которые полностью определяются в терминах полуинцидентора 3.

3(xuy)=P(xuy)VP(yux).

Конечная последовательность

x0u1x1u2x2...xl-1ulxl       */

l>=0 элементов графа L,  для которой истинно высказывание

3(x0u1x1)& 3(x1u2x2)&...&(3(xl-1ulxl)

называется маршрутом из вершины x0   в вершину xl или маршрутом, соединяющим x0 c xl; в случае x0 =xl имеем циклический маршрут при вершине x0. Число носит название длины маршрута.

Маршрут - это не просто часть графа, так как порядок его обхода играет существенную роль.

Пусть на полукольцо К наложены соотношения

xh=hx=z=q2=1.

Рассмотрим l-ю степень матрицы смежности  R графа L

Rl=||r(l)ij||.

Ее элемент r(l)ij равен количеству различных маршрутов длины l из вершины с номером i в вершину j.

Это утверждение тривиально при l=1 и легко доказывается в общем случае индукцией по l: если уже известно, что r(l)ik равно количеству различных маршрутов длины l из i-ой вершины в j-ю с фиксированной предпоследней k-ой вершиной получаем выражение r(l)ik, rkj , а для количества таких маршрутов, но без фиксации предпоследней вершины имеем следующее выражение:

3.

Интересуясь только достижимостью j-ой вершины из i-ой за l шагов, можно к определяющим соотношениям в полукольце К добавить соотношение: 2=1, тем самым преобразуя полукольцо в булеву алгебру B{0,1}.

Элемент матрицы r(l)ij будет тогда равен единице, если существует хотя бы один маршрут длины l из i-ой вершины в j-ю и нулю в противном случае.

Рассмотрим следующий пример

 

3              1          b          4                                                                             

 а             2                       5           c                                                             

              3                                                                                            

                                    8        6                                                      

                                                                                                         

 

9           10                      7      

                                                          

Рис.  3.1.1

 

                  

            a   b    c    d    e                             a   b    c    d    e   

3             3

                                          a      b       c       d      e                              

                         3

 

Например, из вершины а в вершину d идут три маршрута длиной 2:

a1b8d, a2b8d, a3b8d

и девять маршрутов длины 3:

a1b4c6d, a1b5c6d, a2b4c6d, a2b5c6d, a3b4c6d,

                             a3b5c6d, a1b8d7d, a2b8d7d, a3b8d7d,

а из d8d идет один маршрут длины 1: d7d, три маршрута длины 2: d6c6d, d7d7d, 8b8d. При исследовании взаимной достижимости вершин имеем:

 

 

3                         3

 

3                   3

      

Маршрут x0u1x1u2x2...xl-1ulxназывается цепью, если ребра u1,u2... ,ul  все различны. Циклическая цепь x0 =xl при l>=1 называется циклом. Цепь называется простой, если все ее вершины различны; при x0 =xl  и  l>=1 имеем простой цикл.

В графе на рисунке 3.1 маршрут a1b4c4b8d (циклический) не является цепью, а значит и циклом; цепи е9е10 (цикл), a2b4c6d8b (не цикл) не просты, цепь a2b4c6d - простая, а цепи e9e и b4c6d8b - простые циклы.

ЛЕММА: Всякий маршрут (в частности всякая цепь) графа содержит хотя бы одну простую цепь, соединяющую ту же пару вершин. Всякий цикл содержит простой цикл.

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

Алгоритм выявления всех маршрутов заданной длины и цепей

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

3
 


                            a                    v                         b  

                          u                                             

                                                         w                  

                                                                            t

                                                              c     

Рис. 3.1.2

Матрица смежности и матрица инциденций А этого графа имеют вид:

 

                       a      b     c                                     u     v     w    t

         3                         3

 

Введем в рассмотрение так называемую “усовершенствованную матрицу смежности” Ru, которая указывает не только на количество ребер, соединяющих заданную пару вершин, но и сами эти ребра:

 

                                                 3

 

Теперь последовательно возводим матрицу Ru в степень:

 

               3

 

 

           3

   

Элемент матрицы Rlu равен сумме таких произведений, в каждом из которых сомножители соответствуют в том же порядке последовательным ребрам некоторого маршрута длины l из i-ой вершины в j-ую, причем ни один маршрут не может быть пропущен и ни один не повторяется. Например, элемент матрицы R2u:

r(2)22=v2+w2+t2+wt+tw

выявляет последовательность ребер во всех маршрутах длины 2 из вершины b в эту же вершину b (последовательность вершин каждого маршрута однозначно восстанавливается с помощью матрицы инциденций

А): эти маршруты суть

bvavb, bwcwb, bcb, bwctb, btcwb.

Элемент

r(3)21=vu2+v3+w2v+t2v+wtv+twv

позволяет выявить все маршруты длины 3 из b в abvauaua, bvavbva, bwcwbva и т.д.

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

Для выделения по матрице Ru только цепей, необходимо после каждого умножения на Ru вычеркивать те слагаемые, в которых какой-либо сомножитель встречается более одного раза.

Например,  для графа,  изображенного на рисунке 3.1.2 имеем

 

                             3

 

         3

 

               3

 

Кофман А. и Мальгранж И. предложили близкий по идее и легко реализуемый на ЭЦВМ алгоритм выявления простых цепей и циклов.

Алгоритм нахождения кратчайших цепей между заданными

вершинами

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

Помечаем вершину х значком 0; затем все смежные с х непомеченные еще вершины помечаем значком 1; далее помечаем значком 2 каждую такую вершину, которая еще не помечена и смежна хотя бы с одной вершиной помеченной значком 1 и т.д. Как только вершина у окажется помеченной некоторым значком l>=1, процесс прекращаем.

Теперь каждая кратчайшая цепь ненулевой длины

xu1x1u2x2...xl-1uly,

соединяющая х с у ищется следующим образом: за xl-1 берем любую вершину, смежную с у и помеченную значком l-1, за Ul- любое ребро, соединяющее xl-1 c у, за   xl-2  берем любую вершину смежную с xl-1 и помеченную значком l-2, за Ul-1 -любое ребро, соединяющее xl-2  c xl-1 и т.д., до тех пор, пока не дойдем до вершины х.

 

Алгоритм выявления всех простых цепей и циклов

В  рассматриваемом алгоритме, являющемся модификацией алгоритма, описанного выше, некоторые вершины метятся более чем одним значком. Помечаем вершину х значком 0. Все смежные с х - значком 1; при этом если вершина х смежна сама с собой, т.е. имеет петлю, единица будет ее вторым значком.

Далее метим значком 2  вершину z, где z не имела до этого значка 2 и смежна хотя бы с одной вершиной, у которой значок 1 - первый. Затем помечаем значком 3 все те вершины, которые не имели еще этого значка и смежны с какой-нибудь из вершин, имеющих 2 в качестве первого значка и т.д.

Продолжаем процесс до тех пор, пока все вершины не получат хотя бы по одному значку и для каждой вершины, имеющей первый значок i, все смежные с ней вершины будут содержать i+1 в числе своих значков.

Далее выявляем цепи также как и в предыдущем алгоритме, с той лишь разницей, что если уже построена часть цепи (i=1..l; xl=y)

xiui+1xi+1...xl-1ulxl

и вершина xi имеет значки j1,j2,...,jk, то за xi-1 можно взять любую такую вершину, которая отлична от всех  xi,...xl, смежна с xi и у которой первый (!) значок равен одному из чисел j1-1, j2-1,...,jk-1.

 

 

 

Пример 3.1.1.

3                   

u3                   a(1,2,3)                   b(2,3)            c(2,3,4)              d(3)

                                                    u4                                          u5                         u6

                                         

         u2                                                                              u8          u9              u10    u7          

 

u1                                                             u11                                                               u13

        x(0,1,2)          u12                    e(1,3)                            y(2,3,4)  

Рис. 3.1.3.

 

Разметка осуществлялась следующими шагами:

x0

x(0,1), a(1), e(1).

x(0,1,2), a(1,2), b(2), c(2), y(2).

a(1,2,3), b(2,3), c(2,3), d(3), e(1,3), e(2,3).

c(2,3,4), y(2,3,4).

В процессе выявления цепей будем указывать не все значки вершины xi, а лишь один или два из них: тот, согласно которому xi выбрана и тот, который служит для выбора xi-1 (если он отличен от первого).

Последовательность y(2), e(1), x(0) дает две цепи: xu11eu13y и xu12eu13y. Последовательность y(4), d(3), c(2,3), b(2), x(0) дает цепь xu6au4bu5cu6du7y и т.д.

Разрешая повторение вершин в последовательности y,xl-1,xl-2,.., но запрещая повторения ребер в цепи мы получим алгоритм выявления всех цепей и циклов, а не только простых.

 

3.2. Отделимость и соединимость.

               Компоненты связности

 

Вершины х и у графа L=(x,u,p) называются отделенными, если не существует никакой соединяющей их цепи, и неотделенными, если хотя бы одна такая цепь имеется. Отношение неотделимости рефлексивно, симметрично и транзитивно, т.е. представляет собой отношение эквивалентности и поэтому х разбивается на классы х1, х2,...,хк  попарно неотделимых вершин.

Подграфы Li=(xi,ui,p), порожденные множествами xi, не имеют друг с другом общих вершин и называются компонентами связности. Число их обозначается x(L). При x(L)=1 граф называется связным.

Рассмотрим матрицу смежности R=RL графа над В{0,1} и обозначим через Е единичную матрицу порядка n(L), образуем последовательно матрицы

E+R; (E+R)2=E+R+R2;

                                      (E+R)3 =E+R+R2+R3      и.т.д.,

элементы которых выражают количество маршрутов длины не более 1, не более 2, не более 3 и т.д. Для некоторого l0 заведомо не превышающего m(L), будем иметь

(E+R)lo=(E+R)lo+1.

Каждой системе всех одинаковых столбцов (или строк) “установившейся” матрицы (E+R)lo отвечает компонента связности графа L для ускорения процесса получения установившейся матрицы берут l=2,4,8...

 

3

Пример 3.2.1.

 

 

                       3

 

Отделимость и соединимость

Две несмежные вершины х и у графа L=(x,u,p) называются К-отделимыми, если из L можно так удалить не более К  вершин, чтобы в оставшемся подграфе вершины х и у оказались отделенными.

Вершины х и у графа L называются К-соединимыми, если в L существует К цепей, соединяющих х с у и попарно не имеющих других общих вершин, а также общих ребер.

Теорема Менгера. В графе L=(x,u,p) две вершины х и у тогда и только тогда К-неотделимы, когда они (х+1) соединимы.

Граф называется К-связным, если любые две его вершины (К-1)-неотделимы.

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

Ребро u графа L называется перешейком, если после его удаления из графа соединяемые им вершины 1-отделимы.

Пример 3.2.2.

3

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

 

3.3. Метрика графа

 

Расстоянием rL х,у между вершинами х и у графа L=(x,u,p) называется длина кратчайшего из маршрутов, соединяющих эти две вершины; если х и у отделены, то

rL (х,у)=¥.

Функция rL (х,у) заслуживает названия метрики графа, поскольку она удовлетворяет трем аксиомам Фреше:

"x,yÎx[r(х,у)=0 «x=y],

"x,yÎx[r(х,у)=r(y,x)],

"x,y,zÎx[r(х,у)+r(y,z)³r(x,z)].

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

Для нахождения метрики графа достаточно знать его матрицу смежности R над В{0,1}. Далее образуется матрица R+E и последовательно возводится в степень до тех пор, пока не получим установившуюся матрицу (E+R)k=(E+R)k+1=... Обозначим (E+R)l=||S(l)ij||. Тогда

r(xixj)=min{l; S(l)ij=1}

Пример 3.3.1. Для графа на рисунке 3.2.1, например r(1,2)=1; r(1,3)=2 и т.д.

3                         3

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика