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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
((М \ {a, b})
® {a'}; (R \ {(с, d) | c = а, или d = а,
или с = b, или d = b})
® {(а', с)|(а, с) ´ R, или
(b, с)
´ R} ® {(c, a') |(c, a) ´ R, или (с, b) ´
R}).
Говорят, что построенный граф получается из
графа G отождествлением вершин а и b. В слу-
чае, когда а и b соединены дугой, операцию ото-
ждествления вершин а и b называют стягиванием
дуги (а, b).
Пример 1.33.
Из графа G, показанного на рис. 1.27, добавлением
вершины 5 образуется граф G
1
, добавлением дуги
(3, 1) – граф G
2
, удалением дуги (3, 2) – граф G
3
,
удалением вершины 2 – граф G
4
, отождествлением
вершин 1 и 4 – граф G
5
, стягиванием дуги (2, 3) –
граф G
6
.
Рис. 1.27.
G
2 3
1 4
2 3
1 4
5
2 3
1 4
2 3
1 4
1
4
3
1
′
2 3
1
4
2
′
G
1
G
2
G
3
G
4
G
5
G
6
107
Рис. 4.5.
4.4. Факторы
Определение 4.5. Фактором графа (V, E) называ-
ется частичный граф (V, E
0
), в котором каждая
вершина обладает полустепенями исхода и захода,
равными 1.
Всякий гамильтонов контур является факто-
ром, но обратное неверно, ибо фактор может со-
стоять из нескольких контуров без общих вершин
(рис. 4.6).
Фактор и гамельтонов
контур
Фактор, но не гамельто-
нов контур 
  ((М \ {a, b}) ® {a'}; (R \ {(с, d) | c = а, или d = а,
  или с = b, или d = b}) ® {(а', с)|(а, с) ´ R, или
  (b, с) ´ R} ® {(c, a') |(c, a) ´ R, или (с, b) ´
R}).
Говорят, что построенный граф получается из
графа G отождествлением вершин а и b. В слу-
чае, когда а и b соединены дугой, операцию ото-
ждествления вершин а и b называют стягиванием
дуги (а, b).
                    Пример 1.33.
                                                                                                           Рис. 4.5.
Из графа G, показанного на рис. 1.27, добавлением                                                 4.4. Факторы
вершины 5 образуется граф G1, добавлением дуги                                Определение 4.5. Фактором графа (V, E) называ-
(3, 1) – граф G2, удалением дуги (3, 2) – граф G3,                            ется частичный граф (V, E0), в котором каждая
удалением вершины 2 – граф G4, отождествлением                                вершина обладает полустепенями исхода и захода,
вершин 1 и 4 – граф G5, стягиванием дуги (2, 3) –                             равными 1.
граф G6.                                                                            Всякий гамильтонов контур является факто-
 2        3 2          3   2        3     2     3             3   2   3 2′    ром, но обратное неверно, ибо фактор может со-
                                                                              стоять из нескольких контуров без общих вершин
                                                                              (рис. 4.6).
                  5

  1       4   1        4   1        4      1    4    1        4   1′ 1    4
      G           G1           G2            G3          G4       G5   G6
                                        Рис. 1.27.

                                                                                Фактор   и   гамельтонов               Фактор, но не гамельто-
                                                                                контур                                 нов контур




                                               70                                                                107

Страницы