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

UptoLike

ВУЗ: 

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

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

Рубрика: 

106
(a
k
, x) . E . (x, a
k+1
) . E . (a
k+1
, x) . E.
Если не существует пути m
0
= xa
1
…a
p
, то
(a
1
, x) . E . (a
2
, x) . E, (a
p
, x) . E, и путь m
p
= a
1
…a
p
x
существует, вопреки допущению. Таким образом,
можно шаг за шагом построить путь, содержащий
все вершины графа.
Примечание: Из этого результата вытекает, что
всегда возможно упорядочить множество участни-
ков турнира таким образом, чтобы каждый пред-
шествующий был победителем непосредственно
следующего (если, конечно, ни одна из встреч не
заканчивается ничьей).
4.3. Задача о шахматном коне
Поставим задачу обойти конем шахматную
доску так, что побывать в каждой клетке ровно по
одному разу. Эта задача интересовала многих ма-
тематиков, особенно Эйлера (Euler L.), де Муавра
(de Moivres), Вандермонда (Vandermonde) и др.
Правило, которое, видимо, оправдывается на
практике, но еще не подтверждено теоретически
состоит в следующем: всякий раз ходим конем ту-
да, откуда
он угрожает наименьшему числу еще не
пройденных клеток.
Другой способ состоит в нахождении мар-
шрута по половинке доски, симметричном дублиро-
вании его и соединении обоих маршрутов (рис. 4.5).
71
Определение 1.71. Дополнением графа без петель
G = (М, R) называется граф
G= (M, M
2
\ (R ®
id
M
)).
Пример 1.34.
Дополнением графа G, изображенного на
рис. 1.27, является граф
G , показанный на рис.
1.28.
Рис. 1.28.
Пусть G
1
= (М
1
, R
1
) , G
2
= (М
2
, R
2
) – графы.
Определение 1.72. Объединением графов G
1
® G
2
называется граф (М
1
® М
2
, R
1
® R
2
).
Определение 1.73. Если М
1
∩ М
2
≠ ¬, то пересе-
чением графов G
1
G
2
называется граф
(М
1
М
2
, R
1
R
2
).
Определение 1.74. Кольцевой суммой графов
G
1.
«.G
2
называется граф (М
1
® М
2
, R
1
« R
2
), где
R
1
« R
2
= (R
1
\ R
2
) ® (R
2
\ R
1
)
Пример 1.35.
1 4
3 2 
           (ak, x) . E . (x, ak+1) . E . (ak+1, x) . E.      Определение 1.71. Дополнением графа без петель
        Если не существует пути m0 = xa1…ap, то               G = (М, R) называется граф G = (M, M 2 \ (R ®
(a1, x) . E . (a2, x) . E, (ap, x) . E, и путь mp = a1…apx                        idM)).
существует, вопреки допущению. Таким образом,
можно шаг за шагом построить путь, содержащий                                   Пример 1.34.
все вершины графа.                                                 Дополнением графа G, изображенного на
Примечание: Из этого результата вытекает, что                рис. 1.27, является граф G , показанный на рис.
всегда возможно упорядочить множество участни-               1.28.            2              3
ков турнира таким образом, чтобы каждый пред-
шествующий был победителем непосредственно
следующего (если, конечно, ни одна из встреч не
заканчивается ничьей).
          4.3. Задача о шахматном коне
      Поставим задачу обойти конем шахматную                                 1   Рис. 1.28.   4
доску так, что побывать в каждой клетке ровно по                  Пусть G1 = (М1, R1) , G2 = (М2, R2) – графы.
одному разу. Эта задача интересовала многих ма-              Определение 1.72. Объединением графов G1 ® G2
тематиков, особенно Эйлера (Euler L.), де Муавра             называется граф (М1 ® М2, R1 ® R2).
(de Moivres), Вандермонда (Vandermonde) и др.
                                                             Определение 1.73. Если М1 ∩ М2 ≠ ¬, то пересе-
      Правило, которое, видимо, оправдывается на
                                                             чением графов G1 ­ G2 называется граф
практике, но еще не подтверждено теоретически
                                                                           (М1 ­ М2, R1 ­ R2).
состоит в следующем: всякий раз ходим конем ту-
                                                             Определение 1.74. Кольцевой суммой графов
да, откуда он угрожает наименьшему числу еще не
                                                             G1.«.G2 называется граф (М1 ® М2, R1 « R2), где
пройденных клеток.
                                                                       R1 « R2 = (R1 \ R2) ® (R2 \ R1)
      Другой способ состоит в нахождении мар-
шрута по половинке доски, симметричном дублиро-                                   Пример 1.35.
вании его и соединении обоих маршрутов (рис. 4.5).


                              106                                                       71

Страницы