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

UptoLike

ВУЗ: 

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

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

Рубрика: 

84
2Р = 20 = 3φ
3
+ 4φ
4
+....
Умножив равенство
Г = 7 = φ
3
+ φ
4
+ φ
5
+ …
на три, получим
3Г = 21 = 3 ( φ
3
+ φ
4
+ φ
5
+ …).
Ясно, что
(3φ
3
+ 3φ
4
+ 3φ
5
+…) < (3φ
3
+4φ
4
+ 5φ
5
+…)
или 3Г < 2Р, но по условию, 2Р = 20, а 3Г = 21; по-
этому вывод, полученный при введенном нами
предположении (граф плоский), противоречит ус-
ловию. Отсюда заключаем, что полный граф с пя-
тью вершинами не является плоским.
Теорема 2.11. (Теорема Понтрягина-Куратовского)
Граф является плоским тогда и только тогда, когда
он не имеет в качестве подграфа полного графа с
пятью вершинами.
Теорема 2.12. Пусть G – неорграф без петель,
имеющий хотя бы одно ребро. Тогда следующие
условия эквивалентны:
1) G – бихроматический граф;
2) G – двудольный граф;
3) G не содержит циклов нечетной длины.
Следствие: Если G – лес, то
J
(G) } 2.
Оценим хроматическое число графа G через
его параметры. Обозначим через deg (G) макси-
мальную степень вершин графа G.
93
оптимальным, так как каждое ребро проходится
по один раз и вес этого цикла равен тогда:
Сформулированная выше задача 2) называ-
ется задачей китайского почтальона, и ее реше-
ние имеет много потенциальных приложений, как
например:
а) Сбор мусора. Рассмотрим проблему сбора до-
машнего мусора. Допустим, что определенный
район города обслуживается единственной ма-
шиной. Ребра графа G представляют дороги, а
вершины – пересечения дорог. Величина c.(a
j
) –
вес ребра – будет соответствовать длине дороги.
Тогда проблема сбора мусора в данном районе
сводится к нахождению цикла в графе G, про-
ходящего по каждому ребру G по крайней мере
один раз. Требуется найти цикл с наименьшим
километражем.
b) Доставка молока или почты. Еще две задачи,
когда требуется определить маршрут, проходя-
щий хотя бы один раз по каждой из улиц, воз-
никают при доставке молока или почты. Здесь
задача состоит в нахождении маршрута, мини-
∑
=
m
j
j
ac
1
)(
                  2Р = 20 = 3φ3 + 4φ4 +....             оптимальным, так как каждое ребро проходится
Умножив равенство                                       по один раз и вес этого цикла равен тогда:
              Г = 7 = φ3 + φ4 + φ5 + …                                    m
на три, получим
           3Г = 21 = 3 ( φ3 + φ4 + φ5 + …).
                                                                         ∑ c(a
                                                                          j =1
                                                                                  j   )
Ясно, что
     (3φ3 + 3φ4 + 3φ5 +…) < (3φ3+4φ4+ 5φ5+…)                Сформулированная выше задача 2) называ-
или 3Г < 2Р, но по условию, 2Р = 20, а 3Г = 21; по-   ется задачей китайского почтальона, и ее реше-
этому вывод, полученный при введенном нами            ние имеет много потенциальных приложений, как
предположении (граф плоский), противоречит ус-        например:
ловию. Отсюда заключаем, что полный граф с пя-        а) Сбор мусора. Рассмотрим проблему сбора до-
тью вершинами не является плоским.                       машнего мусора. Допустим, что определенный
Теорема 2.11. (Теорема Понтрягина-Куратовского)          район города обслуживается единственной ма-
Граф является плоским тогда и только тогда, когда        шиной. Ребра графа G представляют дороги, а
он не имеет в качестве подграфа полного графа с          вершины – пересечения дорог. Величина c.(aj) –
пятью вершинами.                                         вес ребра – будет соответствовать длине дороги.
Теорема 2.12. Пусть G – неорграф без петель,             Тогда проблема сбора мусора в данном районе
имеющий хотя бы одно ребро. Тогда следующие              сводится к нахождению цикла в графе G, про-
условия эквивалентны:                                    ходящего по каждому ребру G по крайней мере
      1) G – бихроматический граф;                       один раз. Требуется найти цикл с наименьшим
      2) G – двудольный граф;                            километражем.
      3) G не содержит циклов нечетной длины.         b) Доставка молока или почты. Еще две задачи,
Следствие: Если G – лес, то J (G) } 2.                   когда требуется определить маршрут, проходя-
      Оценим хроматическое число графа G через           щий хотя бы один раз по каждой из улиц, воз-
его параметры. Обозначим через deg (G) макси-            никают при доставке молока или почты. Здесь
мальную степень вершин графа G.                          задача состоит в нахождении маршрута, мини-



                           84                                                    93

Страницы