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

UptoLike

ВУЗ: 

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

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

Рубрика: 

120
Рис. 5.8.
Решение.
1 2 3 4 5
1 1 1 0 0 0
2 1 0 1 0 0
3 1 0 0 0 1
4 0 0 1 1 0
5 0 1 0 1 0
Число дуг, исходящих из вершины a
i
, назы-
вается степенью ее исхода d
i
–
, заходящих в a
i
–
степенью захода d
i
+
, d
i
–
+d
i
+
=d
i
– степенью верши-
ны i. Так, вершина 3 имеет степень захода, равную
2, степень исхода – 2. Степень вершины равна 4.
57
где Р' ³ U
×
M
×
U, и выполняется (и, a, v) ´ Р'
тогда и только тогда, когда в мультиграфе G вер-
шина а является концом ребер и и v.
Определение 1.43. Раскраской ребер мультиграфа
G называется раскраска вершин мультиграфа
L.(G).
Пример 1.27.
Проводится монтаж аппаратуры. Чтобы не
перепутать проводники, необходимо их окрасить
таким образом, чтобы два проводника, идущие к
одной плате, имели разные цвета. В этом случае
вершинами являются платы, а ребрами – провод-
ники.
Определение 1.44. Неорграф G называется бихро-
матическим, если J (G) = 2.
Рассмотрим простой алгоритм построения
раскраски, который во многих случаях приводит к
раскраскам, близким к минимальным.
Алгоритм последовательной раскраски
1. Произвольная вершина а
1
графа G принимает
цвет 1.
2. Если вершины а
1
, ..., а
i
раскрашены l цветами 1,
2, ..., l, l } i, то новой произвольно взятой вер-
шине а
i+1
припишем минимальный цвет, не ис-
пользованный при раскраске вершин из множе-
ства
{a
j
| ρ (a
i+1
, a
j
) = 1, j < i}. 
                                                       где Р' ³ U × M × U, и выполняется (и, a, v) ´ Р'
                                                       тогда и только тогда, когда в мультиграфе G вер-
                                                       шина а является концом ребер и и v.
                                                       Определение 1.43. Раскраской ребер мультиграфа
                                                       G называется раскраска вершин мультиграфа
                                                       L.(G).
                                                                         Пример 1.27.
                                                              Проводится монтаж аппаратуры. Чтобы не
                                                       перепутать проводники, необходимо их окрасить
                        Рис. 5.8.                      таким образом, чтобы два проводника, идущие к
                     Решение.                          одной плате, имели разные цвета. В этом случае
                                                       вершинами являются платы, а ребрами – провод-
           1        2               3   4       5
                                                       ники.
  1        1        1               0   0       0      Определение 1.44. Неорграф G называется бихро-
                                                       матическим, если J (G) = 2.
  2        1        0               1   0       0             Рассмотрим простой алгоритм построения
  3        1        0               0   0       1      раскраски, который во многих случаях приводит к
                                                       раскраскам, близким к минимальным.
  4        0        0               1   1       0
                                                              Алгоритм последовательной раскраски
  5        0        1               0   1       0      1. Произвольная вершина а1 графа G принимает
                                                          цвет 1.
      Число дуг, исходящих из вершины ai, назы-        2. Если вершины а1, ..., аi раскрашены l цветами 1,
вается степенью ее исхода di–, заходящих в ai –           2, ..., l, l } i, то новой произвольно взятой вер-
степенью захода di+ , di–+di + =di – степенью верши-      шине аi+1 припишем минимальный цвет, не ис-
ны i. Так, вершина 3 имеет степень захода, равную         пользованный при раскраске вершин из множе-
2, степень исхода – 2. Степень вершины равна 4.           ства
                                                                        {aj | ρ (ai+1, aj) = 1, j < i}.

                              120                                                  57

Страницы