Файл: Дискретная математика_Ч.2_УМП.pdf

41

3.2 

Суграф

 (

частичный

граф

) 

 
Граф  L

′ = ( Х′, Y′ )  является  суграфом графа  L ( Х, U ), если:  

1. Х

′ =X ;   

2. U

′ является подмножеством  U, т.е. U′  ⊂  U . 

 
Примеры. 
    

1. Граф G2 (рисунок 13) является суграфом (частичным гра-

фом) графа G  (рисунок 10). 

2. Граф L1 (рисунок 15) является суграфом (частичным гра-

фом) графа L = (рисунок 14). 

    x5       x4                
    o        

о                 

                               
 u5                            
           G2                  
                             

    o       o           o      
    x1      x2           x3  

Рисунок 13 

х1      х2         х3                    х1        х2     х3  

       o        o         o                     o         o       o 
                                                      
                                            L1     
 L                                                   
                                                 
       o        o         o                     o          o      o   
       

х4       х5        х6                    х4         х5     х6  

                       Рисунок 14                                                   Рисунок 15 

 
ЗАДАНИЕ: 
1.

Построить 

одновершинные, 

двувершинные, 

три-

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

2.

Построить суграфы (частичные графы) для графа, данно-

го в  индивидуальном задании на рисунке 1. 

42

Тема

 4. 

ВЗВЕШЕННЫЕ

ГРАФЫ

. 

МЕТРИКА

ГРАФА

 
Задавая  на  вершинах  и  рёбрах    графа L=(X,U) функции  p:            

X 

→  M

p

,

q

: 

U 

→  M

q

,  где  M

p

  и  M

q 

–  произвольные  множества, 

получим взвешенный граф G(p,q)= (X,U,p,q). 

На множествах X и U можно задавать и более чем по одной 

функции или, напротив, задать функцию только на рёбрах. 

К  взвешенным  графам  принадлежат  электрические  схемы, 

сети коммуникаций,  информационные и логические сети, графы 
автоматов, сетевые графики работ и многое другое. Ограничимся 
здесь  отдельным  вопросом,  в  котором  наличие  весов  является 
идеей чистой теории графов: длины рёбер. Пусть L(q) = (X,U; q) – 
обыкновенный граф с весовой функцией q, относящей каждому 
ребру  u

∈U  действительное  число q(u)>0  в  качестве  длины. 

Если М – маршрут на графе L, то сумма q(M)=

∑

∈M

u

u

q

)

(

 по всем 

его рёбрам называется его q-длиной, а просто «длина»  понима-
ется как количество рёбер маршрута (каждое ребро графа надо 
считать столько раз, сколько оно встречается в маршруте). Чис-
ло  

ρ(x,y,)=min{q(M)/M∈M(x,y)} (*), 

где M(x,y) – множество всех простых цепей из x в y, называется 
расстоянием между вершинами x,y

∈X взвешенного графа L(q); 

если x = y, то М – цепь нулевой длины и её длина q(M)=0, а если 
вершины x и y отделены в графе, то 

ρ(x,y,)= +∞. 

Термин «расстояние» оправдан тем, что функция 

ρ

,  опре-

делённая  посредством  выражения (*),   удовлетворяет  трём ак-
сиомам Фрише: 

∀x,y∈X[ρ(x,y)=0⇒ x=y],                                (1) 

∀x,y∈X[ρ(x,y,)= ρ(y,x)],                                 (2)  

∀x,y∈X[ρ(x,y)+ ρ(y,z)= ρ(x,z)],                     (3) 

т.е. 

ρ

  является  метрикой  на  множестве  вершин  Х.  В  частном 

случае, когда все q(u)=1 и, значит, q-длина всякой цепи совпада-
ет с её обычной длиной, метрика 

ρ

  = 

1
L

ρ

 графа L[1] называется 

естественной метрикой обыкновенного графа L=(X,U). 

43

Вершина x

0

∈X графа L=[q] называется центральной, если  

∀x∈X[max ρ(x,y)≥ max ρ(x

0

,y)]; 

y

∈X                    y∈X 

Вершина x

0

∈X графа G=[q] называется периферийной, если 

∀x∈X[max ρ(x,y)≤ max ρ(x

0

,y)]. 

                   y

∈X                     y∈X 

В силу того, что множество Х конечно, а величина +

∞ до-

пускается как возможное значение функции 

ρ, вершины каждо-

го из двух указанных типов всегда существуют. Величина  

 r(G)=min max 

ρ(x,y) 

               х

∈X  y∈X 

носит название радиуса, а величина  

 d(G )= max 

ρ(x,y) 

                  х,y

∈X   

называется  диаметром  графа L(X,U). У  несвязного  графа               
max 

ρ(x,y)=+∞  для любой пары вершин х,y∈Х, поэтому каждая 

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

 
  ПРИМЕР.  Дан  граф L=(X,U) (рисунок 1) с  естественной 

метрикой 

ρ

. 

 x1        x9    x8     x7     x6      x5                       x13
  

о         о     о     о       о       о                        о  

О        о                 о          о        о        о

 x2       x3                 x4         x10      x11      x12 

Рисунок 1 

 
У данного графа вершины x4 и x10 – центральные, верши-

ны x1, x7, x8, x13 – периферийные, r(L)=4 , d(L)=7 .                                        

44

Способ нахождения метрики графа 
 
Для нахождения метрики 

ρ

    = 

1
L

ρ

  графа L = (X,U) доста-

точно знать его матрицу смежности R={ r

i,j

}   над    булевой  ал-

геброй B = ( 0,1 ),   т.е.  элементы матрицы r

i,j

 = 1,  если вершины 

x

i

 и x

j

 – смежны и  r

i,j

 = 0,   в противном случае, все действия над 

элементами  матрицы R  производятся  по  правилам  логической 
алгебры:  

      1 + 1 = 1;  0 + 0 = 0;  1 + 0 = 1;  0 * 0 = 0;  1 * 0 = 0.      
Сопоставляя уже известные нам способы для установления 

существования  маршрутов  в  графе  длины q = m, можно  утвер-
ждать,  что  при  возведении  в степень   матрицы  S = R + E, где           
Е – единичная матрица той же размерности, что и размерность 
матрицы R,  на некотором шаге возведения в степень получим:  

S

 =  S

k+1

, т.е.  устойчивую матрицу  S в степени  «k». 

Значения степеней p  матрицы  S

p

:  p= {k, k–1, k–2, ... , 1}   

равны  длинам  простых  кратчайших  цепей,  связывающих  вер-
шины  x

i

 и x

j

. 

 Таким образом, последовательно возводя в степень  p = {1, 

2, 3,…, k}  матрицу  S до  получения  устойчивой    матрицы  S

k

, 

можно  определить  расстояния  между  всеми  вершинами  графа 
L=(X,U), построив матрицу метрики графа L. 

 
Алгоритм построения матрицы метрики графа   
 
Исходные  данные  для  построения  матрицы  метрики  (от-

клонений): 

1. Граф L=(X,U). 
2. Матрица смежности  R графа L c элементами логического 

типа: 

⎧ 1, если вершины x

i

, x

j

 – смежны; 

 r

i,j  

 =   

⎨  

⎩0 в противном случае. 

 
Введем обозначения:  
R – матрица смежности заданного графа L; 
E – единичная матрица; 

45

М – матрица метрики (отклонений). 
 
Описание алгоритма 
 
Матрица метрики M= (m

i,j

) строится  за несколько итераций 

по  результатам  последовательного  возведения  матрицы 
R=(E+R) в степень q= k

,

1

 до получения устойчивой матрицы R

k

, 

где k – степень устойчивой матрицы R

k

. Матрица R

k  

называется 

устойчивой, если R

k 

 = R

k +1

. 

Размерность  матрицы М равна размерности матрицы R. 
Все элементы матрицы М не определены. 
Шаг 1.  
Степень q матрицы R равна «1»: q=1. 
∀  m

i,i

    присваиваем  значение «0», на  основании  аксиомы 

Фрише. 

Шаг 2. Всем элементам m

i,j

, значения которых не определе-

ны,  присвоить  значение  степени q, если  соответствующие  им 
элементы  матрицы    R

q

≠ 0. (Не  забывайте,  что  значения  эле-

ментов m

i,j  

определяются только один раз).  

Шаг 3. Проверяем,  имеются ли в матрице M элементы m

i,j

,  

значения которых ещё не определены? 

Если  такие  элементы  имеются,  то  переходим  к  шагу 4; в 

противном случае – к шагу 7. 

Шаг 4. Повышаем степень q матрицы R:  q=q+1.  
Шаг 5. Проверяем,  является  ли матрица R

q–1

 устойчивой. 

Если матрица R

q–1

  – неустойчивая, то переходим к шагу 2. 

Иначе – переходим к шагу 6. 
Шаг 6. Всем  элементам  m

i,j 

  матрицы    M,  значения  кото-

рых  остались  неопределенными,  присваиваем  значение 

∞ 

(бесконечность).  Это  говорит  о  том,  что  граф L=(X,U) несвяз-
ный. 

Шаг 7. Матрица  метрики  М=(m

i,j

)  построена.  Конец  алго-

ритма.  

Примечание:  1.  *Элементам  m

i,j 

значения  присваиваются 

только один раз! Следовательно, если элемент m

i,j

 уже опреде-

лён, то его значение не меняется*.