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

UptoLike

ВУЗ: 

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

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

Рубрика: 

110
сти n продуктов, используя единственный тип ап-
паратуры. Аппарат должен быть перенастроен по-
сле того как был произведен продукт p
i
(но до того
как начато производство продукта p
j
), в зависимо-
сти от комбинации (p
i
, p
j
). Стоимость перена-
стройки аппаратуры постоянна и не зависит от
производимых продуктов. Предположим, что эти
продукты производятся в непрерывном цикле, так
что после производства последнего из n продуктов
снова возобновляется в том же фиксированном
цикле производство первого продукта.
Возникает вопрос о том, может ли быть най-
дена циклическая последовательность производст-
ва
продуктов p
i
(i = 1, 2, …, n), не требующая пе-
ренастройки аппаратуры. Если представить эту за-
дачу в виде ориентированного графа, то ответ на
поставленный вопрос зависит от того, имеет ли
этот ориентированный граф гамильтонов цикл или
нет.
Если не существует циклической последова-
тельности продуктов, не требующей перенастрой-
ки аппаратуры, то какова должна быть последова-
тельность производства с наименьшими затратами
на перенастройку, т.е. требующая наименьшего
числа необходимых перенастроек?
Таким образом, рассмотрим следующие две
задачи.
67
К =
11 12 1
21 22 2
*( ),1 *( ),2 *( ),
...
...
... ... ... ....
m
m
vG vG vGm
bb b
bb b
bb b
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Поскольку каждый фундаментальный разрез
K
i
содержит ровно одну ветвь, а именно и
i
, матри-
ца К имеет вид
K =
11 1, *( )
21 2, *( )
*(),1 *(),*()
...
10
...
1
... ... ...
...
...
01
vG
vG
vG vGvG
bb
bb
bb
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Таким образом, K = (K
1
| K
2
), где K
2
– еди-
ничная матрица порядка v*(G). Отметим, что если
С = (C
1
| C
2
) – соответствующая матрица фунда-
ментальных циклов, то K
1
=
2
T
C
, где
2
T
C
– транс-
понированная матрица C
2
.
Пример 1.31.
Найдем матрицу фундаментальных разрезов
графа G = (М, R), изображенного на рис. 1.25. По-
скольку v*(G) = 6 – 1 = 5, имеется пять фундамен-
тальных разрезов. Ребру 4 соответствует коцикл
К
1
.= {1, 4}, так как при удалении ребра 4 из остова
Т множество вершин М разбивается на две части:
{а
1
}и М \ {а
1
}, а ребра 1 и 4 образуют разрез по 
сти n продуктов, используя единственный тип ап-                    ⎛ b11          b12     ...   b1m ⎞
паратуры. Аппарат должен быть перенастроен по-                     ⎜ b            b22     ... b2 m ⎟⎟
сле того как был произведен продукт pi (но до того              К= ⎜     21

                                                                   ⎜ ...           ...    ...   .... ⎟
как начато производство продукта pj), в зависимо-                  ⎜⎜                                     ⎟
сти от комбинации (pi, pj). Стоимость перена-                       ⎝ bv*(G ),1 bv*(G ),2     bv*( G ),m ⎟⎠
стройки аппаратуры постоянна и не зависит от               Поскольку каждый фундаментальный разрез
производимых продуктов. Предположим, что эти         Ki содержит ровно одну ветвь, а именно иi, матри-
продукты производятся в непрерывном цикле, так       ца К имеет вид
что после производства последнего из n продуктов
снова возобновляется в том же фиксированном                     ⎛ b11          ...   b1,v*(G ) 1           0⎞
цикле производство первого продукта.                            ⎜ b            ... b2,v*(G )                  ⎟
                                                                                                     1
      Возникает вопрос о том, может ли быть най-            K = ⎜ 21                                          ⎟
                                                                ⎜ ...          ...       ...           ... ⎟
дена циклическая последовательность производст-                 ⎜⎜                                            ⎟
ва продуктов pi (i = 1, 2, …, n), не требующая пе-               ⎝ bv*(G ),1   ... bv*( G ),v*(G ) 0       1 ⎟⎠
ренастройки аппаратуры. Если представить эту за-          Таким образом, K = (K1 | K2), где K2 – еди-
дачу в виде ориентированного графа, то ответ на      ничная матрица порядка v*(G). Отметим, что если
поставленный вопрос зависит от того, имеет ли        С = (C1 | C2) – соответствующая матрица фунда-
этот ориентированный граф гамильтонов цикл или                                    T        T
                                                     ментальных циклов, то K1 = C2 , где C2 – транс-
нет.
      Если не существует циклической последова-      понированная матрица C2.
тельности продуктов, не требующей перенастрой-                            Пример 1.31.
ки аппаратуры, то какова должна быть последова-            Найдем матрицу фундаментальных разрезов
тельность производства с наименьшими затратами       графа G = (М, R), изображенного на рис. 1.25. По-
на перенастройку, т.е. требующая наименьшего         скольку v*(G) = 6 – 1 = 5, имеется пять фундамен-
числа необходимых перенастроек?                      тальных разрезов. Ребру 4 соответствует коцикл
      Таким образом, рассмотрим следующие две        К1.= {1, 4}, так как при удалении ребра 4 из остова
задачи.                                              Т множество вершин М разбивается на две части:
                                                     {а1}и М \ {а1}, а ребра 1 и 4 образуют разрез по

                          110                                                            67

Страницы