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

UptoLike

ВУЗ: 

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

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

Рубрика: 

68
разбиению {{а
1
}, М \ {а
1
}}. Аналогично ребру 5
соответствует коцикл K
2
= {5}, ребру 6 – коцикл
К
3
= {1, 2, 3, 6}, ребру 7 – коцикл К
4
= {2, 3, 7},
ребру 8 – коцикл К
5
= {3, 8}. Следовательно, мат-
рица фундаментальных разрезов имеет вид
1 2 3 4 5 6 7 8
K
1
1 0 0 1 0 0 0 0
K
2
0 0 0 0 1 0 0 0
K
3
1 1 1 0 0 1 0 0
K
4
0 1 1 0 0 0 1 0
K
5
0 0 1 0 0 0 0 1
1.16. Операции над графами
Пусть G ′= (M ′, R ′) является подграфом гра-
фа G = (M, R), то есть M
′ ³ M и R ′³ (M ′)
2
.
Определение 1.65. Граф G ′ называется частью
графа G, если M
′ ³ M и R ′³ R (M ′)
2
.
Пример 1.32.
Граф G' = ({1, 2, 3}; [1, 2] ® [2, 3] ® {(1,
3)}) (рис. 1.26 б) является подграфом графа
G = ({1,2,3,4}; [1,2]
® [l,4] ® [2,3] ® [3,4] ®
{(1,3)}) (рис. 1.26 а), а граф G" = ({1,2,3}; [1,2]
®
{(3,2)}) (рис. 1.26 в) – частью графа G.
1
1
1
2
3
2
2
3
3
4
а б в
109
Так же можно «склеивать» различные кон-
туры фактора. Рассмотрим вновь задачу о шахмат-
ном коне. Благодаря симметрии шахматной доски
получается фактор. Клетки, помеченные одинако-
выми буквами, образуют контур. Два контура
можно объединить тогда и только тогда, когда две
последовательные вершины одного соответствен-
но смежны с двумя последовательными вершина-
ми другого.
Различные соединения показаны при
помощи вспомогательного графа. Вспомогатель-
ный граф имеет очевидный гамильтонов путь
aDbCdAcB (рис. 4.7).
Рис. 4.7.
4. 5. Задачи, связанные с поиском
гамильтоновых циклов
В ряде отраслей промышленности возникает
следующая задача планирования. Нужно произве-
разбиению {{а1}, М \ {а1}}. Аналогично ребру 5                                        Так же можно «склеивать» различные кон-
соответствует коцикл K2 = {5}, ребру 6 – коцикл                                  туры фактора. Рассмотрим вновь задачу о шахмат-
К3 = {1, 2, 3, 6}, ребру 7 – коцикл К4 = {2, 3, 7},                              ном коне. Благодаря симметрии шахматной доски
ребру 8 – коцикл К5 = {3, 8}. Следовательно, мат-                                получается фактор. Клетки, помеченные одинако-
рица фундаментальных разрезов имеет вид                                          выми буквами, образуют контур. Два контура
                                                                                 можно объединить тогда и только тогда, когда две
                1       2   3           4        5       6       7       8       последовательные вершины одного соответствен-
       K1       1       0   0           1        0       0       0       0
                                                                                 но смежны с двумя последовательными вершина-
       K2       0       0   0           0        1       0       0       0
                                                                                 ми другого. Различные соединения показаны при
       K3       1       1   1           0        0       1       0       0
                                                                                 помощи вспомогательного графа. Вспомогатель-
       K4       0       1   1           0        0       0       1       0
                                                                                 ный граф имеет очевидный гамильтонов путь
       K5       0       0   1           0        0       0       0       1
                                                                                 aDbCdAcB (рис. 4.7).
              1.16. Операции над графами
      Пусть G ′= (M ′, R ′) является подграфом гра-
фа G = (M, R), то есть M ′ ³ M и R ′³ (M ′)2.
Определение 1.65. Граф G ′ называется частью
графа G, если M ′ ³ M и R ′³ R ­ (M ′)2.
                    Пример 1.32.
       Граф G' = ({1, 2, 3}; [1, 2] ® [2, 3] ® {(1,
3)}) (рис. 1.26 б) является подграфом графа
G = ({1,2,3,4}; [1,2]® [l,4] ® [2,3] ® [3,4] ®                                                          Рис. 4.7.
{(1,3)}) (рис. 1.26 а), а граф G" = ({1,2,3}; [1,2] ®
                                                                                        4. 5. Задачи, связанные с поиском
{(3,2)}) (рис. 1.26 в) – частью графа G.
                                                                                              гамильтоновых циклов
          2                         2                                2
                                                                                      В ряде отраслей промышленности возникает
                        1
                                                                                 следующая задача планирования. Нужно произве-
1                   3                                3       1               3

                                            68                                                            109
          4
      а                         б                                    в

Страницы