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

UptoLike

ВУЗ: 

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

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

Рубрика: 

122
x
2
= x
2
+ x
3
+ 0
x
3
= x
2
+ 0
x
4
= x
1
+ x
3
+ 0
Часто нулевые слагаемые не записывают,
как и в системах уравнений в поле действительных
чисел.
Воспользуемся методом последовательного
исключения неизвестных. Поскольку в правой
части первого уравнения нет переменной х
1
, мож-
но исключить эту переменную из системы, под-
ставив в остальные уравнения. С учетом идемпо-
тентности сложения получим:
x
2
= x
2
+ x
3
+ 0
x
3
= x
2
+ 0
x
4
= x
2
+ x
3
+ x
4
+ 1
Из второго уравнения имеем x
2
= 1*(x
3
+ 0).
В полукольце В итерация любого элемента равна
единице полукольца. Поэтому x
2
= х
3
+ 0. Исклю-
чив x
2
из системы, получим
x
3
= x
3
+ 0
x
4
= x
3
+ x
4
+ 1
Далее вычислим x
3
= 1*0 = 1·0 = 0. Подста-
вив х
3
= 0 в последнее уравнение, найдем
x
4
= 1*1 = 1·1 = 1
Итак, первый столбец А* есть
55
1.12. Раскраски графов
Пусть G = (М, R) – неорграф без петель.
Определение 1.40. Раскраской (вершин) графа G
называется такое задание цветов вершинам G, что
если [а, b] – ребро, то вершины а и b имеют раз-
личные цвета. Раскраска называется правильной,
если образы любых двух смежных вершин
различны.
Определение 1.41. Хроматическим числом
J
(G)
графа G называется минимальное число цветов,
требующееся для раскраски G.
Раскраска вершин графа в
J
цвета есть раз-
биение множества вершин графа на попарно непе-
ресекающиеся непустые подмножества, состоящие
из попарно несмежных вершин, т.е.
М = М
1
∪ М
2
∪ …∪ М
J
;
М
i
∩ М
j
∅, i ≠ j, 1 ≤ i, j ≤
J
.
Пример 1.25.
Так как в полном графе К
п
любые две раз-
личные вершины связаны ребром, то
J
(К
п
) = п.
Пример 1.26.
1. Рассмотрим задачу составления расписания.
Предположим, что нужно прочесть несколько лек-
ций за кратчайшее время. Чтение каждой лекции в
отдельности занимает один час, но некоторые лек-
              x2 =            x2 + x3      +0                   1.12. Раскраски графов
              x3 =            x2           +0
              x4 = x1              + x3    +0             Пусть G = (М, R) – неорграф без петель.
                                                    Определение 1.40. Раскраской (вершин) графа G
      Часто нулевые слагаемые не записывают,        называется такое задание цветов вершинам G, что
как и в системах уравнений в поле действительных    если [а, b] – ребро, то вершины а и b имеют раз-
чисел.                                              личные цвета. Раскраска называется правильной,
      Воспользуемся методом последовательного       если образы любых двух смежных вершин
исключения неизвестных. Поскольку в правой          различны.
части первого уравнения нет переменной х1, мож-     Определение 1.41. Хроматическим числом J (G)
но исключить эту переменную из системы, под-        графа G называется минимальное число цветов,
ставив в остальные уравнения. С учетом идемпо-      требующееся для раскраски G.
тентности сложения получим:                               Раскраска вершин графа в J цвета есть раз-
                                                    биение множества вершин графа на попарно непе-
                  x2 = x2 + x3      +0              ресекающиеся непустые подмножества, состоящие
                  x3 = x2           +0              из попарно несмежных вершин, т.е.
                  x4 = x2 + x3 + x4 + 1
                                                                 М = М1 ∪ М2 ∪ …∪ МJ;
      Из второго уравнения имеем x2 = 1*(x3 + 0).                Мi ∩ Мj ∅, i ≠ j, 1 ≤ i, j ≤ J.
В полукольце В итерация любого элемента равна
единице полукольца. Поэтому x2 = х3 + 0. Исклю-                      Пример 1.25.
чив x2 из системы, получим                               Так как в полном графе Кп любые две раз-
                                                    личные вершины связаны ребром, то J (Кп) = п.
                        x3 = x3      +0
                        x4 = x3 + x4 + 1                             Пример 1.26.
      Далее вычислим x3 = 1*0 = 1·0 = 0. Подста-    1. Рассмотрим задачу составления расписания.
вив х3 = 0 в последнее уравнение, найдем            Предположим, что нужно прочесть несколько лек-
                  x4 = 1*1 = 1·1 = 1                ций за кратчайшее время. Чтение каждой лекции в
      Итак, первый столбец А* есть                  отдельности занимает один час, но некоторые лек-


                              122                                            55

Страницы