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

UptoLike

ВУЗ: 

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

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

Рубрика: 

144
крыты на ремонт. Докажите, что из любого города
можно проехать в любой другой по оставшимся
дорогам.
Решение.
Пусть A
и B – данные города. Докажем сна-
чала, что из A
в B можно было проехать до закры-
тия на ремонт двух дорог. Рассмотрим для этого
проекцию многогранника на некоторую прямую,
не перпендикулярную ни одному из его ребер (при
такой проекции вершины многогранника не сли-
ваются).
Пусть A'
и B' – проекции точек A и B, а M' и
N' –
крайние точки проекции многогранника (в
точки M'
и N' проецируются вершины M и N). Если
идти из вершины A
так, что в проекции движение
будет происходить по направлению от M'
к N' , то,
в конце концов, мы обязательно попадем в верши-
ну N. Аналогично из вершины B можно пройти в N.
Таким образом, можно проехать из A в B (через N).
Если полученный путь из A
и B проходит че-
рез закрытую дорогу, то есть еще два объезда по
граням, для которых это ребро является общим.
Вторая закрытая дорога не может находиться сра-
зу на двух этих объездах. Значит, из города A
в го-
род
B можно проехать, по крайней мере, одним
путем.
Задача 5.18. (о трех домах и трех колодцах)
А В С
33
Для представления рассматриваемого графа мат-
рицей смежности требуется 5
2
= 25 элементов, а
списком дуг – только 6
⋅ 2 = 12 элементов.
Другим представлением графа, удобным при
работе с графами, в которых удаляются или добав-
ляются вершины, является структура смежно-
сти, получаемая составлением для каждой верши-
ны а списка номеров ее последователей, т. е. но-
меров вершин b, для которых имеется дуга (a, b).
Пример 1.19.
Орграф, изображенный на рис. 15, представляется
следующей структурой смежности:
Вершины Списки последователей
1: 1, 2
2: 3
3: 4
4: 3, 4
5:
Для ненагруженного графа введем понятие
кратчайшего пути. Это путь с минимальным об-
щим числом дуг, причем каждая дуга считается
столько раз, сколько она содержится в этом пути.
Для нахождения минимального пути между
двумя произвольными вершинами для случая, ко-
гда все c
ij
≥ 0 можно воспользоваться простым ал-
горитмом Дейкстры. 
крыты на ремонт. Докажите, что из любого города       Для представления рассматриваемого графа мат-
можно проехать в любой другой по оставшимся           рицей смежности требуется 52 = 25 элементов, а
дорогам.                                              списком дуг – только 6 ⋅ 2 = 12 элементов.
                      Решение.                             Другим представлением графа, удобным при
      Пусть A и B – данные города. Докажем сна-       работе с графами, в которых удаляются или добав-
чала, что из A в B можно было проехать до закры-      ляются вершины, является структура смежно-
тия на ремонт двух дорог. Рассмотрим для этого        сти, получаемая составлением для каждой верши-
проекцию многогранника на некоторую прямую,           ны а списка номеров ее последователей, т. е. но-
не перпендикулярную ни одному из его ребер (при       меров вершин b, для которых имеется дуга (a, b).
такой проекции вершины многогранника не сли-
ваются).                                                               Пример 1.19.
      Пусть A' и B' – проекции точек A и B, а M' и    Орграф, изображенный на рис. 15, представляется
N' – крайние точки проекции многогранника (в          следующей структурой смежности:
точки M' и N' проецируются вершины M и N). Если           Вершины            Списки последователей
идти из вершины A так, что в проекции движение               1:                       1, 2
будет происходить по направлению от M' к N' , то,            2:                        3
в конце концов, мы обязательно попадем в верши-              3:                        4
ну N. Аналогично из вершины B можно пройти в N.              4:                        3, 4
Таким образом, можно проехать из A в B (через N).            5:
      Если полученный путь из A и B проходит че-            Для ненагруженного графа введем понятие
рез закрытую дорогу, то есть еще два объезда по       кратчайшего пути. Это путь с минимальным об-
граням, для которых это ребро является общим.         щим числом дуг, причем каждая дуга считается
Вторая закрытая дорога не может находиться сра-       столько раз, сколько она содержится в этом пути.
зу на двух этих объездах. Значит, из города A в го-         Для нахождения минимального пути между
род B можно проехать, по крайней мере, одним          двумя произвольными вершинами для случая, ко-
путем.
                                                      гда все cij ≥ 0 можно воспользоваться простым ал-
       Задача 5.18. (о трех домах и трех колодцах)
                                                      горитмом Дейкстры.
              А           В           С

                          144                                                   33

Страницы