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

UptoLike

ВУЗ: 

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

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

Рубрика: 

56
ции не могут читаться одновременно (например,
их читает один и тот же лектор). Построим граф G,
вершины которого биективно соответствуют лек-
циям и две вершины смежны тогда и только тогда,
когда соответствующие им лекции нельзя читать
одновременно. Очевидно, что любая раскраска
этого графа определяет допустимое расписание:
лекции, соответствующие вершинам одного цвета,
могут читаться одновременно. Напротив, любое
допустимое расписание определяет раскраску гра-
фа G. Оптимальные расписания соответствуют
раскраскам с минимальным числом цветов, а чис-
ло часов, необходимое для прочтения всех лекций,
равно
J
(G).
2. Рассмотрим граф G, вершины которого – стра-
ны, а ребра соединяют страны, имеющие общую
границу. Числу
J
(G) соответствует наименьшее
число красок, необходимых для раскраски карты
так, чтобы никакие две соседние страны не были
окрашены в один цвет.
Существуют и практические задачи, связан-
ные с раскраской ребер в мультиграфе.
Раскраска ребер в мультиграфе G может
быть определена с помощью раскраски вершин так
называемого реберного мультиграфа L (G).
Определение 1.42. Для произвольного неориенти-
рованного мультиграфа G = (М, U, Р) реберным
мулътиграфом L (G) называется тройка (U, М, Р'),
121
Задача 5.6.
Для графа, изображенного на рис. 5.9, ре-
шить задачу вычисления матрицы достижимости.
Решение
На числовые метки дуг внимания пока не
обращаем, считая, что ориентированный граф раз-
мечен над полукольцом В и метка каждой дуги
равна 1, т.е. ориентированный граф задан матри-
цей А.
Рис. 5.9.
0111
0110
0100
1010
A
⎛⎞
⎜⎟
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
Запишем систему уравнений в полукольце В
для определения первого столбца матрицы А*:
x
1
= x
2
+ x
3
+ x
4
+ 1
v
2
v
1
v
3
v
4
2
5
1
3
10
1
3
4
ции не могут читаться одновременно (например,                               Задача 5.6.
их читает один и тот же лектор). Построим граф G,
вершины которого биективно соответствуют лек-             Для графа, изображенного на рис. 5.9, ре-
циям и две вершины смежны тогда и только тогда,     шить задачу вычисления матрицы достижимости.
когда соответствующие им лекции нельзя читать                            Решение
одновременно. Очевидно, что любая раскраска               На числовые метки дуг внимания пока не
этого графа определяет допустимое расписание:       обращаем, считая, что ориентированный граф раз-
лекции, соответствующие вершинам одного цвета,      мечен над полукольцом В и метка каждой дуги
могут читаться одновременно. Напротив, любое        равна 1, т.е. ориентированный граф задан матри-
допустимое расписание определяет раскраску гра-     цей А.                          2
фа G. Оптимальные расписания соответствуют                             v1        5
                                                                                               v2
раскраскам с минимальным числом цветов, а чис-
ло часов, необходимое для прочтения всех лекций,                                     10
равно J (G).                                                       3         1             3   1
2. Рассмотрим граф G, вершины которого – стра-
ны, а ребра соединяют страны, имеющие общую                            v4                      v3
границу. Числу J (G) соответствует наименьшее                      4
число красок, необходимых для раскраски карты
                                                                             Рис. 5.9.
так, чтобы никакие две соседние страны не были
окрашены в один цвет.                                                    ⎛0      1 1 1⎞
      Существуют и практические задачи, связан-                          ⎜            ⎟
                                                                           0     1 1 0⎟
                                                                       A=⎜
ные с раскраской ребер в мультиграфе.                                    ⎜0      1 0 0⎟
      Раскраска ребер в мультиграфе G может                              ⎜            ⎟
                                                                         ⎝1      0 1 0⎠
быть определена с помощью раскраски вершин так
называемого реберного мультиграфа L (G).                  Запишем систему уравнений в полукольце В
Определение 1.42. Для произвольного неориенти-      для определения первого столбца матрицы А*:
рованного мультиграфа G = (М, U, Р) реберным
мулътиграфом L (G) называется тройка (U, М, Р'),                  x1 =               x2 + x3 + x4 + 1


                          56                                                         121

Страницы