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

UptoLike

ВУЗ: 

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

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

Рубрика: 

146
Рис. 5.20.
Предположим, что граф допускает плоскую
реализацию. Начертим на плоскости непересекаю-
щиеся ребра АХ, ВХ, УВ, УС, СZ, ZА
(рис. 5.21):
Рис. 5.21.
Можно считать, что полученный замкнутый
контур описывается непрерывной кривой. Проводя
непересекающиеся непрерывные линии АУ и ВZ,
можно считать, что одна из них лежит внутри кон-
тура, а вторая – вне его. Но тогда дуга СХ обяза-
31
Пример 1.17.
Пусть М = {a
1
, a
2
, a
3
, a
4
},
R = [a
1
, a
2
] ® [a
2
, a
3
] ® [a
1
, a
4
] ® [a
2
, a
4
],
f: M
→ С,
где С – множество городов,
Рис. 14.
g: R → ω,
f (a
1
) = Омск,
f (a
2
) = Новосибирск,
f (а
3
) = Кемерово,
f (а
4
) = Павлодар,
g ([a
1
, a
2
]) = 681,
g ([a
2
, a
3
]) = 274,
g ([a
1
, a
4
]) = 413,
g ([a
2
, a
4
]) = 589.
Помеченный граф (M, R, f, g) изображен на рис. 14
и представляет собой схему автомобильных дорог
с указанием их протяженности.
Информацию о весах дуг во взвешенном
графе можно представлять в виде матрицы весов
W = (w
ij
), где w
ij
– вес дуги (a
i
, a
j
), если дуга (a
i
, a
j
)
Омск а
1
а
2
Новосибирск
Кемерово а
3
Павлодар а
4
589 413
681
274 
                                                                        Пример 1.17.
                                                          Пусть М = {a1, a2, a3, a4},
                                                         R = [a1, a2] ® [a2, a3] ® [a1, a4] ® [a2, a4],
                                                                          f: M → С,
                                                    где С – множество городов,
                                                    Омск а1              681                а2 Новосибирск

                                                                   413         589              274
                    Рис. 5.20.
                                                          Павлодар а4                     Кемерово а3
     Предположим, что граф допускает плоскую                                   Рис. 14.
реализацию. Начертим на плоскости непересекаю-
щиеся ребра АХ, ВХ, УВ, УС, СZ, ZА (рис. 5.21):                       g: R → ω,
                                                                      f (a1) = Омск,
                                                                      f (a2) = Новосибирск,
                                                                      f (а3) = Кемерово,
                                                                      f (а4) = Павлодар,
                                                                      g ([a1, a2]) = 681,
                                                                      g ([a2, a3]) = 274,
                                                                      g ([a1, a4]) = 413,
                                                                      g ([a2, a4]) = 589.
                    Рис. 5.21.                      Помеченный граф (M, R, f, g) изображен на рис. 14
                                                    и представляет собой схему автомобильных дорог
      Можно считать, что полученный замкнутый
                                                    с указанием их протяженности.
контур описывается непрерывной кривой. Проводя
                                                          Информацию о весах дуг во взвешенном
непересекающиеся непрерывные линии АУ и ВZ,
                                                    графе можно представлять в виде матрицы весов
можно считать, что одна из них лежит внутри кон-
                                                    W = (wij), где wij – вес дуги (ai, aj), если дуга (ai, aj)
тура, а вторая – вне его. Но тогда дуга СХ обяза-


                          146                                                        31

Страницы