Основные понятия теории графов. Гладких О.Б - 32 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

32
существует, а для несуществующих дуг веса
обычно помечают нулем или знаком
∞ в зависи-
мости от приложений. Матрица весов имеет вид
0 681 413
681 0 274 589
274 0
413 589 0
W
∞
⎛⎞
⎜⎟
⎜⎟
=
⎜⎟
∞
∞
⎜⎟
∞
⎝⎠
Если граф G = (М, R) является разрежен-
ным, т. е. число дуг R достаточно мало по сравне-
нию с числом вершин М, то более эффективным,
чем с помощью матрицы смежности, является
представление дуг графа посредством списка дуг.
Этот список задается двумя наборами
m
= (m
1
,
m
2
,..., m
R
) и n=(n
1
, n
2
,..., n
R
) , где (a
mi
,a
ni
) – i-я дуга
графа G.
Пример 1.18.
Орграф, изображенный на рис. 15, представляется
следующим списком дуг:
m = (1,1,2,3,4,4),
n = (1,2,3,4,3,4).
Рис. 15.
а
3
а
4
а
1
а
2
а
5
145
Рис. 5.19.
На участке земли были построены три дома
А, В, С и вырыты три колодца X, У, Z. От каждого
из домов имелась тропа к каждому из трех колод-
цев (рис 5.19). Спустя некоторое время обитатели
домов А, В, С поссорились друг с другом и решили
проложить дорожки к колодцам X,
У, Z так, чтобы
по пути к колодцам им не приходилось встречать-
ся друг с другом. Спрашивается, можно ли это
сделать?
Решение.
Попытки решить эту задачу приводят к убе-
ждению, что это невозможно, хотя число точек пе-
ресечения ребер можно свести к 1
(рис. 5.20): 
существует, а для несуществующих дуг веса
обычно помечают нулем или знаком ∞ в зависи-
мости от приложений. Матрица весов имеет вид
                   ⎛ 0 681 ∞ 413 ⎞
                   ⎜ 681 0 274 589 ⎟
                W =⎜               ⎟
                   ⎜ ∞ 274 0    ∞ ⎟
                   ⎜               ⎟
                   ⎝ 413 589 ∞  0 ⎠
        Если граф G = (М, R) является разрежен-                                    Рис. 5.19.
ным, т. е. число дуг R достаточно мало по сравне-                    На участке земли были построены три дома
нию с числом вершин М, то более эффективным,                   А, В, С и вырыты три колодца X, У, Z. От каждого
чем с помощью матрицы смежности, является                      из домов имелась тропа к каждому из трех колод-
представление дуг графа посредством списка дуг.                цев (рис 5.19). Спустя некоторое время обитатели
Этот список задается двумя наборами m = (m1,                   домов А, В, С поссорились друг с другом и решили
m2,..., mR) и n =(n1, n2,..., nR) , где (ami,ani) – i-я дуга   проложить дорожки к колодцам X, У, Z так, чтобы
графа G.                                                       по пути к колодцам им не приходилось встречать-
                     Пример 1.18.                              ся друг с другом. Спрашивается, можно ли это
Орграф, изображенный на рис. 15, представляется                сделать?
следующим списком дуг:                                                             Решение.
                 m = (1,1,2,3,4,4),                                  Попытки решить эту задачу приводят к убе-
                 n = (1,2,3,4,3,4).                            ждению, что это невозможно, хотя число точек пе-
                                                               ресечения ребер можно свести к 1 (рис. 5.20):
                          а5

                    а1                   а2
                         а3                   а4


                              Рис. 15.


                                    32                                                   145

Страницы