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

UptoLike

ВУЗ: 

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

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

Рубрика: 

166
0 1 0 1 0 0
∞
3 5 11
∞ ∞ ∞ ∞
6 3 10 7
1 0 0 1 0 0
∞ ∞ ∞
12 6
∞ ∞
6
∞
1 2 3
0 0 0 0 1 1
∞ ∞ ∞
3
∞
2
∞
3 1
∞
5 6
1 1 0 0 1 1
∞ ∞ ∞ ∞
9 8
∞
10 2 5
∞
3
0 0 1 1 0 0
∞ ∞ ∞ ∞ ∞ ∞
7 7 3 6 3
∞
0 0 1 1 0 0
∞ ∞ ∞ ∞ ∞ ∞
10
∞ ∞ ∞ ∞
∞ ∞ ∞
4. Найти числа внутренней и внешней устойчиво-
сти для графов:
4.1.
4.2.
4.3.
11
центральной части города Кенигсберг (ныне Ка-
лининград), включающий два берега реки Прего-
ли, два острова в ней и семь соединяющих их мос-
тов. Задача состоит в том, чтобы обойти все четы-
ре части суши, пройдя по каждому мосту один раз,
и вернуться в исходную точку. Эта задача была
решена (показано, что решения не существует)
Эйлером в 1736 году.
Пример 1.1.
На рис. 2 изображен неориентированный
граф G = (X, A).
X
= {x
1
, x
2
, x
3
, x
4
},
A = {a
1
= (x
1
, x
2
), a
2
=(x
2
, x
3
),
a
3
=(x
1
, x
3
), a
4
= (x
3
, x
4
)}.
Рис. 2.
Пример 1.2.
На рис. 3 изображен ориентированный граф
G = (X, A).
X = {x
1
, x
2
, x
3
, x
4
},
A
= {a
1
= (x
1
, x
2
), a
2
= (x
1
, x
3
),
a
3
= (x
3
, x
4
), a
4
= (x
3
, x
2
)}. 
0   1   0   1   0   0   ∞   3   5   11    ∞    ∞   ∞    ∞    6   3   10   7   центральной части города Кенигсберг (ныне Ка-
1   0   0   1   0   0   ∞   ∞   ∞   12    6    ∞   ∞    6    ∞   1   2    3
0   0   0   0   1   1   ∞   ∞   ∞   3     ∞    2   ∞    3    1   ∞   5    6   лининград), включающий два берега реки Прего-
1   1   0   0   1   1   ∞   ∞   ∞   ∞     9    8   ∞    10   2   5   ∞    3   ли, два острова в ней и семь соединяющих их мос-
0   0   1   1   0   0   ∞   ∞   ∞   ∞     ∞    ∞   7    7    3   6   3    ∞   тов. Задача состоит в том, чтобы обойти все четы-
0   0   1   1   0   0   ∞   ∞   ∞   ∞     ∞    ∞   10
                        ∞   ∞   ∞   ∞     ∞    ∞   ∞
                                                                              ре части суши, пройдя по каждому мосту один раз,
                                                                              и вернуться в исходную точку. Эта задача была
4. Найти числа внутренней и внешней устойчиво-                                решена (показано, что решения не существует)
сти для графов:                                                               Эйлером в 1736 году.
4.1.
                                                                                                    Пример 1.1.
                                                                                   На рис. 2 изображен неориентированный
                                                                              граф G = (X, A).
                                                                                   X = {x1, x2, x3, x4},
                                                                                   A = {a1= (x1, x2), a2=(x2, x3),
                                                                                        a3=(x1, x3), a4= (x3, x4)}.
4.2.




                                                                                                   Рис. 2.

                                                                                                     Пример 1.2.
4.3.
                                                                                    На рис. 3 изображен ориентированный граф
                                                                              G = (X, A).
                                                                                    X = {x1, x2, x3, x4},
                                                                                    A = {a1 = (x1, x2), a2 = (x1, x3),
                                                                                          a3 = (x3, x4), a4 = (x3, x2)}.


                                         166                                                            11

Страницы