Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 16 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

инцидентных этой вершине. Удаление вершины x
3
показано на рис.8, б (для
исходного графа , изображенного на рис.8, а).
Удаление ребра или удаление дуги. Если a
i
-дуга графа G=(X,A), то G-a
i
-
подграф графа G, получающийся после удаления из G дуги a
i
. Заметим, что
концевые вершины дуги a
i
не удаляются. Удаление из графа множества вершин
или дуг определяются как последовательное удаление определенных вершин
или дуг. Удаление дуг a
4
и a
7
показано на рис.8, в.
Замыкание или отождествление . Говорят, что пара вершин x
i
и x
j
в
графе G замыкается (или отождествляется), если они замыкаются такой новой
вершиной, что все дуги в графе G, инцидентные x
i
и x
j
, становятся инцидентными
новой вершине. Например , результат замыкания вершины x
1
и x
6
показан на
рис.8,г для графа G (рис.8, а).
Стягивание. Под стягиванием подразумевают операцию удаления дуги
или ребра и отождествление его концевых вершин . Граф, изображенный на
рис.6,д получен стягиванием дуги A
1
, а на рис.8,е - стягиванием дуг a
1
, a
6
и a
7
.
x
1
x
2
x
3
x
4
x
5
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
x
1
x
2
x
4
x
5
a
1
a
2
a
3
a
8
x
1
x
2
x
3
x
4
x
5
a
1
a
2
a
3
a
5
a
6
a
8
(x
1
,x
2
)
x
3
x
4
x
5
a
3
a
4
a
5
a
6
a
7
a
8
a
2
a
1
(x
1
,x
2
)
x
3
x
4
x
5
a
3
a
4
a
5
a
6
a
7
a
8
a
2
(x
1
,x
2
)
(x
3
,x
4
)
x
5
a
3
a
4
a
5
a
8
a
2
а) б
)
в
)
г)
д
)
е)
Рис. 8. Исходный граф G
1
(а) ; удаление вершины G- x
3
; (б) удаление
ребер G \ {a
4
, a
7
} (в); отождествление вершин x
1
, x
2
(г)
;
стягивание дуги a
1
(д)
;
стягивание дуги a
6
и a
7
(е).
инцидентных этой вершине. Удаление вершины x3 показано на рис.8, б (для
исходного графа , изображенного на рис.8, а).
       Удаление ребра или удаление дуги. Если ai-дуга графа G=(X,A), то G-ai -
подграф графа G, получающийся после удаления из G дуги ai. Заметим, что
концевые вершины дуги ai не удаляются. Удаление из графа множества вершин
или дуг определяются как последовательное удаление определенных вершин
или дуг. Удаление дуг a4 и a7 показано на рис.8, в.
       Замыкание или отождествление . Говорят, что пара вершин xi и xj в
графе G замыкается (или отождествляется), если они замыкаются такой новой
вершиной, что все дуги в графе G, инцидентные xi и xj , становятся инцидентными
новой вершине. Например , результат замыкания вершины x1 и x6 показан на
рис.8,г для графа G (рис.8, а).
       Стягивание. Под стягиванием подразумевают операцию удаления дуги
или ребра и отождествление его концевых вершин . Граф, изображенный на
рис.6,д получен стягиванием дуги A1, а на рис.8,е - стягиванием дуг a1, a6 и a7.
                     x2                                             x2                                       x2

           a1                   a4                                                                 a1
                                                         a1
 x1                                       x3   x1                                        x1                                     x3
            a3                                                a3                                    a3
                      a5                                                                                     a5
                           a6                                                                                          a6
      a2                                  a7                                                  a2
                                                    a2
           x5 a8 x4                                                                                x5 a8 x4
                                                         x5 a8 x4                                    в)
                а)                                          б)

                                                                   (x1,x2)                          (x1,x2)
                (x1,x2) a1
                                                                              a4                              a4
                          a4
                                                a2                                      a2                                  (x3,x4)
a2                                                                                 x3         a3
      a3                             x3                   a3                                            a5
                a5                                                  a5
                     a6                                                  a6
                                 a7                                                a7                             a8
                                                                                             x5
     x5 a8 x4                                        x5 a8 x4
                                                         д)                                                  е)
         г)
 Рис. 8. ИсходныйграфG1(а) ; удаление вершиныG-x3; (б) удаление
 реберG \ {a4, a7} (в); отождествлениевершинx1, x2(г); стягиваниедугиa1
 (д); стягиваниедугиa6иa7(е).

Страницы