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

UptoLike

ВУЗ: 

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

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

Рубрика: 

22
Рис. 8.
Длина маршрута M
1
равна 3, а длина маршрута M
2
равна 4.
Определение 1.22. Маршрут (цикл), в котором все
ребра различны, называется простой цепью (цик-
лом). Маршрут (цикл), в котором все вершины,
кроме первой и последней, различны, называется
элементарной цепью (циклом).
Пример 1.12.
В приведенном на рис. 9 графе выделим сле-
дующие маршруты:
(a
1
,a
3
,a
4
) – простая элементарная цепь длины 3, т.к.
все ребра и вершины попарно различны;
(a
2
,a
4
,a
3
) – простой элементарный цикл, т.к. это
замкнутый маршрут, у которого все
ребра и вершины, кроме первой и по-
следней, различны;
(a
1
,a
2
,a
4
,a
3
) – цепь, которая является простой, но не
элементарной, т.к. все ребра различны,
но вершина x
2
встречается дважды;
155
А В С D E
A
1,5 1 2 2,5
B 1,5
1,2 3 0,8
C 1 1,2
1,1 0,9
D 2 3 1,1
2,7
E 2,5 0,8 0,9 2,7
Сначала строим ту дорогу, которая имеет
наименьшую стоимость. В нашем случае это мар-
шрут В – Е. теперь найдем самую дешевую линию,
соединяющую город В или Е с каким то из осталь-
ных городов. Это путь между Е и С. Включаем его
в схему. Далее поступаем аналогично – ищем са-
мый дешевый из путей, соединяющих один из го-
родов В, С, Е с одним из оставшихся – А или D.
Дешевле всего соединить его с С. Получим сеть,
изображенную на рисунке 6.3. 
                                                                 А        В        С       D        E

                                                         A                1,5      1        2      2,5

                                                         B       1,5              1,2       3      0,8

                                                         C        1       1,2              1,1     0,9

                          Рис. 8.                        D        2       3       1,1              2,7
Длина маршрута M1 равна 3, а длина маршрута M2           E       2,5      0,8     0,9      2,7
равна 4.
Определение 1.22. Маршрут (цикл), в котором все
ребра различны, называется простой цепью (цик-               Сначала строим ту дорогу, которая имеет
лом). Маршрут (цикл), в котором все вершины,            наименьшую стоимость. В нашем случае это мар-
кроме первой и последней, различны, называется          шрут В – Е. теперь найдем самую дешевую линию,
элементарной цепью (циклом).                            соединяющую город В или Е с каким то из осталь-
                                                        ных городов. Это путь между Е и С. Включаем его
                      Пример 1.12.                      в схему. Далее поступаем аналогично – ищем са-
       В приведенном на рис. 9 графе выделим сле-       мый дешевый из путей, соединяющих один из го-
дующие маршруты:                                        родов В, С, Е с одним из оставшихся – А или D.
(a1,a3,a4) – простая элементарная цепь длины 3, т.к.    Дешевле всего соединить его с С. Получим сеть,
             все ребра и вершины попарно различны;      изображенную на рисунке 6.3.
(a2,a4,a3) – простой элементарный цикл, т.к. это
             замкнутый маршрут, у которого все
             ребра и вершины, кроме первой и по-
             следней, различны;
(a1,a2,a4,a3) – цепь, которая является простой, но не
             элементарной, т.к. все ребра различны,
             но вершина x2 встречается дважды;

                            22                                                  155

Страницы