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

UptoLike

ВУЗ: 

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

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

Рубрика: 

62
Теперь фундаментальное множество циклов
можно задать с помощь матрицы фундаменталь-
ных циклов, строки которой являются векторами
12 ()
, , ..., :
vG
аа а
C =
11 12 1
21 22 2
(),1 (),2 (),
...
...
... ... ... ....
m
m
vG vG vG m
aa a
aa a
aa a
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Так как каждый фундаментальный цикл Ci
содержит ровно одну хорду, а именно v
i
, то матри-
ца С имеет вид:
C =
1, ( ) 1 1
2, ( ) 1 2
(),()1 ()
...
10
...
1
... ... ...
...
...
01
vG m
vG m
vG vG vGm
aa
aa
aa
+
+
+
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Таким образом, С = (C
1
| C
2
), где С
1
– еди-
ничная матрица порядка v (G).
Пример 1.30.
Найдем матрицу фундаментальных, циклов
графа G, изображенного на рис. 1.23.
1 7
3 2 6
4
5
8
115
принадлежит, если ни по одной из дорог Чичиков
не проезжал более одного раза.
Решение.
Рис. 5.1.
По схеме видно, что путешествие Чичиков
начал с имения Е, а кончил имением О. Замечаем,
что в имения В и С ведут только по две дороги,
поэтому по этим дорогам Чичиков должен был
проехать. Отметим их жирной линией (рис. 5.2).
Рис. 5.2.
Определены участки маршрута, проходящие
через А: АС и АВ. По дорогам АЕ, АК и АМ Чи-
чиков не ездил. Перечеркнем их. Отметим жирной
линией ЕD; перечеркнем DК. Перечеркнем МО и
МН; отметим жирной линией МF; перечеркнем
D K
H
O
C
E
E
D K
H
F
O
C
A
M
B
E
D K
H
F
O
C
A
M
B 
         Теперь фундаментальное множество циклов                   принадлежит, если ни по одной из дорог Чичиков
можно задать с помощь матрицы фундаменталь-                        не проезжал более одного раза.
ных циклов, строки которой являются векторами                                          Решение.
а1 , а2 , ..., аv (G ) :                                                         D                  K

             ⎛ a11         a12      ... a1m ⎞                              E     C                 H           O
             ⎜ a           a22      ... a2 m ⎟⎟                                                          F
          C= ⎜      21                                                                   A
             ⎜ ...          ...     ...   .... ⎟
             ⎜⎜                                    ⎟                             B            M
              ⎝ av (G ),1 av (G ),2     av (G ),m ⎟⎠
                                                                                             Рис. 5.1.
      Так как каждый фундаментальный цикл Ci                             По схеме видно, что путешествие Чичиков
содержит ровно одну хорду, а именно vi, то матри-                  начал с имения Е, а кончил имением О. Замечаем,
ца С имеет вид:                                                    что в имения В и С ведут только по две дороги,
                                                                   поэтому по этим дорогам Чичиков должен был
         ⎛1       0 a1,v (G )+1            ...       a1m   ⎞       проехать. Отметим их жирной линией (рис. 5.2).
         ⎜                                                 ⎟
            1        a2,v (G )+1           ...       a2 m                            D                 K
      C= ⎜                                                 ⎟
         ⎜    ...         ...              ...        ...  ⎟                E                                  O
         ⎜                                                 ⎟                         C             H
         ⎜0       1 av (G ),v ( G )+1      ... av ( G ) m ⎟⎠                                               F
         ⎝                                                                               A
     Таким образом, С = (C1 | C2), где С1 – еди-                                 B             M
ничная матрица порядка v (G).                                                                Рис. 5.2.
                 Пример 1.30.                                            Определены участки маршрута, проходящие
      Найдем матрицу фундаментальных, циклов                       через А: АС и АВ. По дорогам АЕ, АК и АМ Чи-
графа G, изображенного на рис. 1.23.                               чиков не ездил. Перечеркнем их. Отметим жирной
             5                             8                       линией ЕD; перечеркнем DК. Перечеркнем МО и
                                                                   МН; отметим жирной линией МF; перечеркнем

                 4          6                    2             3
                                 62                                                                115
                                                                                  D                    K
                     1                    7                                                                    O
                                                                            E

Страницы