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

UptoLike

ВУЗ: 

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

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

Рубрика: 

154
Рис. 6.2.
Железные дороги
Предполагается проложить железную доро-
гу, которая соединит несколько крупных городов.
Для любой пары городов известна стоимость про-
кладки пути между ними. Требуется найти наибо-
лее дешевый вариант строительства.
Интересно, что алгоритм нахождения опти-
мального варианта строительства довольно прост
(чего нельзя сказать о других задачах теории гра-
фов).
Продемонстрируем его на примере дороги,
соединяющей пять городов: A, B, C, D и E. Стои-
мость прокладки пути между каждой парой горо-
дов указана в таблице 6.1.
Таблица 6.1.
23
Рис. 9.
(a
1
,a
2
,a
2
) – маршрут длины 3, не являющийся ни
простой, ни элементарной цепью, т.к.
ребро a
2
и вершина x
2
встречаются
дважды.
Граф, в котором найдется маршрут, начи-
нающийся и заканчивающийся в одной вершине, и
проходящий по всем ребрам графа ровно один раз,
называется эйлеровым графом.
5B1.5. Пути, контуры в ориентированном графе
Понятия пути, контура в ориентированном
графе аналогичны понятиям маршрута, цикла в
неориентированном графе.
Определение 1.23. Путем ориентированного гра-
фа называется последовательность дуг, в которой
конечная вершина всякой дуги, отличной от по-
следней, является начальной вершиной следую-
щей дуги. 
                                                                            Рис. 9.

                                                    (a1,a2,a2) – маршрут длины 3, не являющийся ни
                                                                 простой, ни элементарной цепью, т.к.
                                                                 ребро a2 и вершина x2 встречаются
                       Рис. 6.2.
                                                                 дважды.
                   Железные дороги
                                                           Граф, в котором найдется маршрут, начи-
      Предполагается проложить железную доро-
                                                    нающийся и заканчивающийся в одной вершине, и
гу, которая соединит несколько крупных городов.
                                                    проходящий по всем ребрам графа ровно один раз,
Для любой пары городов известна стоимость про-
                                                    называется эйлеровым графом.
кладки пути между ними. Требуется найти наибо-
лее дешевый вариант строительства.                   1.5. Пути, контуры в ориентированном графе
                                                     5B




      Интересно, что алгоритм нахождения опти-
мального варианта строительства довольно прост           Понятия пути, контура в ориентированном
(чего нельзя сказать о других задачах теории гра-   графе аналогичны понятиям маршрута, цикла в
фов).                                               неориентированном графе.
      Продемонстрируем его на примере дороги,       Определение 1.23. Путем ориентированного гра-
соединяющей пять городов: A, B, C, D и E. Стои-     фа называется последовательность дуг, в которой
мость прокладки пути между каждой парой горо-       конечная вершина всякой дуги, отличной от по-
дов указана в таблице 6.1.                          следней, является начальной вершиной следую-
                                     Таблица 6.1.   щей дуги.


                         154                                                  23

Страницы