Задачи по теории графов. Основные понятия, задачи сетевого планирования

Страницы работы

29 страниц (Word-файл)

Фрагмент текста работы

Тема I

Глава 1. Задачи по теории графов

Основные понятия.

1.  Граф – это фигура, состоящая из точек (вершин) и соединяющих их линий (ребер) (рис. 1).

2.  Орграф – это граф, у которого ориентированы ребра (дуги), т.е. указаны начало и конец каждого из них (рис. 2).

3. 


Длина ребра или дуги – это некое число, поставленное в соответствие каждому ребру или дуге.

Рис. 1                                                 Рис. 2

4.  Путь (маршрут) в графе или орграфе – это последовательность ребер, ведущая от некоторой начальной вершины в конечную вершину, в которой каждые два соседних ребра имеют общую вершину, и ни какое ребро не встречается более одного раза.

Например, путями от точки А до точки D (рис. 1) могут быть AD или AED или ABED и т.д.

5.  Длина пути – это число ребер или дуг в нем.

6.  Цикл – это путь, который начинается и кончается в одной и той же вершине.

7.  Граф или орграф называется связанным, если две любые его вершины можно соединить по крайней мере одним путем.

8.  Дерево – это путь без циклов.

Задача 1.

Найти кратчайший путь между всеми вершинами графа (см. рис. 1).

А

5

9

1

A

4E

6EB

4E

1

4E

B

2

3

4E

B

2

6CE

3

7B

2

C

4

6EB

2

C

4

5B

4E

6CE

4

D

3

4E

6CE

4

D

3

1

3

5B

3

E

1

3

5B

3

E

Табл. Т1,2                                                    Табл. Т3,4

1.  Заполним табл. Т1,2 следующим образом.

Обозначим через d(x, y) длину пути от x до y. Диагональю будут являться точки А, В, С, D, E. Для них d(A,A)=d(B,B)=d(C,C)=d(D,D)= d(E,E)=0. Над диагональю запишем длины кратчайших путей, но не более чем из одного ребра (в противном случае поставим ∞).

Таким образом,

d(A,В) = 5, d(А,С) = ∞, d(А,D) = 9, d(A,E) = 1, d(B,C) = 2,

d(B,D) = ∞, d(B,E)= 3, d(C,D) = 4, d(C,E)= ∞, d(D,E) = 3.

Под диагональю запишем длины кратчайших путей, состоящих не более чем из двух ребер (иначе поставим ∞).

d1(A,В) = 5, d2(A,B) = d(A,E) + d(E,B) = 1 + 3 = 4,

d(A,В) = min{d1(A,В); d2(A,В)} = min{5;4} = 4E.

d1(A,C) = d(A,B) + d(B,C) = 5 + 2 = 7,

d2(A,C) = d(A,D) + d(D,C) = 9 + 3 = 13,

d(A,C) = min{d1(A,C); d2(A,C)} = min{7;13} = 7B.

Аналогично находим:

d(A,D) = 4E, d(А,E) = 1, d(B,C) = 2, d(B,D) = 6C или d(B,D) = 6Е,

d(B,Е) = 3, d(С,D) = 4, d(С,E)= 5В, d(D,E) = 3.

2.  Заполним табл. Т3,4 следующим образом.

Над диагональю запишем длины кратчайших путей, но не более чем из трех ребер, а под диагональю - длины кратчайших путей, но не более чем из четырех ребер. Таким образом, под диагональю записаны кратчайшие пути между всеми вершинами графа.

Задача 2.

Найти кратчайшие пути между всеми вершинами графа (рис. 1) через транзитные вершины.

А

5

9

1

 

B

2

3

 

C

4

 

D

3

Табл. Т1

E

1.  Построим таблицу условий Т1 следующим образом: запишем в диагональные клетки обозначения вершин A, B, C, D, E. Для них d(A,A)= d(B,B)=d(C,C)=d(D,D)=d(E,E)=0.

ТА

А

B

C

D

E

A

10B

5

7B

9

1

B

5

10A

2

14A

3

C

7B

2

4B

4

5B

D

9

14A

4

15A

3

E

1

3

5B

3

2A

Над диагональю запишем длины кратчайших путей, но не более чем из одного ребра (в противном случае поставим ∞).

2.  Построим таблицу ТА .

В каждую клетку запишем длину кратчайшего пути, но не более чем из двух ребер (через транзитную вершину А). Например, длина пути DЕ равна 3, а через вершину А – 10. Запишем в клетке (D,E), min{3, 10} = 3. Длина пути ВВ через вершину А равна 10, т.е. d(B,B)= d(В,А) + d(А,В) = 5+5=10. Длина пути DВ через вершину А равна 14, т.е. d(D,B) = d(B,D) = d(D,A)+d(А,В) = 14.

ТB

А

B

C

D

E

A

10B

5

7B

9

1

B

5

10A

2

14A

3

C

7B

2

4B

4

5B

D

9

14A

4

18A

3

E

1

3

5B

3

2A

3.  Построим таблицу ТВ.

В каждую клетку запишем длину кратчайшего пути, но не более чем из трех ребер (через А или В или АВ). Например,

d(С,Е)=min{d1(С,Е);d2(С,Е)} =

= min{8AB; 5B} = 5B, где d1(С, Е) = d1(С, В) + d1(В,А) + d(A,E) = 2 + 5 + 1 = 8AB;

d2(С, Е) = d(С, В) + d(В,E) = 2 + 3 = 5B.

d(Е, B) = min{d1(Е,B); d2(Е,B)} = min{3; 6А } = 3, где d1(Е,B) = 3, d2(Е,B) = d2(Е,А) + d2(А,В) = 6А.

d(D,B) = d(B,D) = d(D,A) + d(А,В)=9 + 5 = 14.

4.  Построим таблицу ТС.

TC

A

B

C

D

E

A

10B

5

7B

9

1

B

5

4C

2

6C

3

C

7B

3

4B

4

5B

D

9

6B

4

8C

3

E

1

3

5B

3

2A

Табл. ТС

В каждую клетку запишем длину кратчайшего пути, но не более чем из четырех ребер (через А, или В, или С, или АВ или ВС, или АВС). Например,

d1(Е,D) = d1(D,Е) = 3,

d2(Е,D) = d2(D,Е) = d2(E,А) + + d2(A,B) + d2(B,C) + d2(C,D) = 1+5+ 2 + 4 = 12;

d3(Е,D) = d3(D,Е) = d3(E,А) + d3(A,D) = 1 + 9 = 10;

d4(Е,D) = d4(D,Е) = d4(E,B) + d4(B,C) + d4(C,D) = 3 + 2 + 4 = 9;

d5(Е,D) = d5(D,Е) = d5(D,A) + d5(A,B) + d5(B,E) = 9 + 5 + 3 = 17;

d(Е,D) = d(D,E) = min{3;12;10;9;17} = 3.

5.  Построить таблицу ТD.

TD

A

B

C

D

E

A

10B

5

7B

9

1

B

5

4C

2

6C

3

C

7B

2

4B

4

5B

D

9

6С

4

8С

3

E

1

3

5B

3

2A

TЕ

A

B

C

D

E

A

2Е

4Е

6ЕВ

4Е

1

B

4Е

4C

2

6СЕ

3

C

6ВЕ

2

4B

4

5B

D

4Е

6ЕС

4

6Е

3

E

1

3

5B

3

2A

6.  Построим таблицу ТЕ.

В табл. ТЕ записаны кратчайшие пути между вершинами данного графа через транзитные вершины.

Например,

d(B,C) = d(B,D) + d(D,C) = 6 + 3 = = 9D;

d(D,A) = d(D,B) + d(B,A) = 8 +1 = 9B;

d(A,B) = min{d1(A,B); d2(A,B)} = min{18; 10} = 10, где d1(A,B) = 18;

d2(A,B) = d2(A,D) + d2(D,B) = 4 + 6 = 10D.

Задача 3.

A

18

4

1

B

6

2

C

8

3

D

Табл. Т1

Найти кратчайшие пути между всеми вершинами графа (см. рис. 2).

1.  Построим таблицу Т1.

Запишем в клетки диагонали метки вершин A, B, C, D. Для них d(A,A)=d(B,B)=d(C,C) = =d(D,D) =d(E,E)= ∞. Символ "∞" означает, что связь не существует. Над и под диагональю запишем длины кратчайших путей не более чем из одного ребра (в противном случае - ∞).

Например, d(A,D) = 4, d(D,А) = ∞, d(A,B) = 18, d(B,A) = 1.

2.  Построим таблицу Т2.

A

10D

7D

4

1

B

9D

5A

3B

2

C

8B

9B

8

7

D

Табл. Т2

Над и под диагональю запишем длины кратчайших путей не более чем из двух ребер (в противном случае - ∞).

3.  Построим таблицу Т3.

A

9DC

7D

4

1

B

8AD

5A

3B

2

C

7BA

6CB

5C

3

D

Табл. Т3

Над и под диагональю запишем длины кратчайших путей не более чем из трех ребер.

Например, d1(B,C) = d1(B,A) + d1(D,C) =

= 1+4+3 = 8AD,

d2(B,C) = d2(B,D) + d2(D,C) = 6 + 3 = 9;

d(B,C) = min{d1(B,C); d2(B,C)} =

min{8AD; 9D} = 8AD.

Таким образом, в табл. Т3 записаны кратчайшие пути между вершинами данного графа.

Задача 4.

A

18

4

1

B

6

2

C

8

3

D

Табл. Т

Найти кратчайшие пути между всеми вершинами графа (рис. 2) через транзитные вершины.

1.  Построим таблицу условий Т.

Запишем в клетки диагонали метки вершин A, B, C, D. Для них d(A,A)=d(B,B)=d(C,C) = = d(D,D) =d(E,E)= ∞. Над и под диагональю запишем длины кратчайших путей не более чем из одного ребра (в противном случае - ∞).

Например, d(A,В) = 18, d(B,A) = 1, d(B,C) = ∞.

2.  Построим таблицу ТA.

TA

A

B

C

D

A

18

4

B

1

19A

5A

C

2

D

8

3

Табл. ТA

В каждую клетку запишем длину кратчайшего пути не более чем из двух ребер через транзитную вершину А. Например, длина пути BD через вершину А равна d1(B,D) = d(В,А) + d(А,D) = 1+4=5A,

d2(B,D) = 6, d(B,D) = min {5;6} = 5A.

d(B,B) = d(B,A) + d(A,B) = 1+18 = 19A.

d(A,C) = ∞.

TB

A

B

C

D

A

19B

18

4

B

1

19A

5A

C

3B

2

7BA

D

9B

8

3

19B

Табл. ТВ

3.  Построим таблицу ТВ.

В каждую клетку запишем длину кратчайшего пути, но не более чем из трех ребер через транзитную вершину В (через А или В или АВ). Например,

d(С,A)=d(С,B) + d(B,A) = 2 + 1 = 3B;

d1(С,D) = d1(С,В) + d1(В,D) = 2 + 6 = 8B;

d2(С,D) = d2(С,В) + d2(В,A) + d2(A,D) = 2 + 1 +4 = 7BA;

d(C,D) = min{d1(C,D);d2(C,D)} = min{8B;7BA} = 7BA;

d(A,A)=d(A,B) + d(B,A) = 18 + 1 = 19B;

d(D,D)=d(D,B) + d(B,D) = 8 + 6 = 14B;

d1(A,D) = 4, d2(A,D) = d2(A,B) + d2(B,D) = 18 + 6 = 24B;

d(A,B) = min{4;24B} = 4.

4.  Построим таблицу ТС.

В каждую клетку запишем длину кратчайшего пути, но не более чем из четырех ребер через транзитную вершину С (через А, или В, или С, или АВ или СВ, или ВА и т.д.).

TC

A

B

C

D

A

19B

18

4

B

1

19A

5A

C

3B

2

7BA

D

6CB

5C

3

10CBA

Табл. ТС

Например,

d1(D,A) = d1(D,B) + d1(B,A) = 8 + 1 = 9B;

d2(D,A) = d2(D,C) + d2(C,B) + d2(B,A) = = 3 + 2 + 1 = 6CB;

d(D,A) = min{9,6} = 6CB;

d1(D,D) = d1(D,B) + d1(B,D) = 8 + 6 = 14B;

d2(D,D) = d2(D,C) + d2(C,B) + d2(B,D) = 3 + 2 + 8 = 13CB;

d3(D,D) = d3(C,D) + d3(C,B) + d3(B,A) + d3(A,D) = 3 + 2 + 1 + 4 = 10CBA;

d(D,D) = min{14;13;10} = 10.

5.  Построим таблицу ТD.

TD

A

B

C

D

A

10DCB

9DC

7D

4

B

1

1DC

8AD

5A

C

3B

2

10BAD

7BA

D

6CB

5C

3

10CBA

В каждую клетку запишем длину кратчайшего пути, не более чем из пяти ребер (через А, или В, или С, или В; или АВ или ВA, или АВ, или DС и т.д.). Например,

d1(A,A) = d1(A,B) + d1(B,A) = 18 + 1 = 19B;

d2(A,A) = d2(A,C) + d2(D,B) + d2(B,A) = 4 + 8 + 1 = 13DB;

d3(A,A) = d3(A,D) + d3(D,C) + d3(C,B) + d3(B,A) = 4 + 3 + 2 + 1 = 10DCB;

d(A,A) = min{19;13;10} = 10DCB;

d(A,C) = d(A,D) + d(D,C) = 4 + 3 = 7D.

Таким образом, в табл. ТD записаны кратчайшие пути между вершинами данного графа через транзитные вершины.

Залача 5.

Найти кратчайшие пути между всеми вершинами графа (рис. 3).

А

9

3

9

В

4

3

С

Табл. Т1

1.  Построим таблицу условий Т1. Запишем в клетки диагонали метки вершин A, B, C. Для них d(A,A)=d(B,B)=d(C,C) = ∞. Над и под диагональю запишем длины кратчайших путей не более чем из одного ребра (в противном случае поставим ∞).

Например, d(В,С) = 4, d(С,В) = ∞.

2.  Построим таблицу Т2.

A

9

3

7С

B

4

3

12А

C

Табл. Т2

Над и под диагональю запишем длины кратчайших путей не более чем из двух ребер.

Например, d1(B,А) = d1(В,С) + d(С,А) = 4+3=7С; d2(B,А) = 9, d(B,А) = min{7С;9} = 7С;

d(С,B) = d(С,A) + d(A,B) = 3+9 = 12A.

Задача 6.

Найти кратчайший путь между всеми вершинами графа (рис. 3) через транзитный вершины.

А

2

3

2

В

4

3

С

Табл. Т1

TA

A

B

C

A

9

3

B

9

18A

4

C

3

12A

6A

Табл. ТA

1.  Построим таблицу условий Т1. Запишем в клетки диагонали метки вершин A, B, C. Для них d(A,A)=d(B,B)=d(C,C) = ∞. Над и под диагональю запишем длины кратчайших путей не более чем из одного ребра (в противном случае поставим ∞).

2.  Построим таблицу ТА следующим образом:

В каждую клетку запишем длину кратчайшего пути не более чем из двух ребер через транзитную вершину А. Например, d(B,В) = =d(В,А)+d(А,В)=9+9=18A, d1(B,С)=d1(B,A) + d1(A,C) = 9 + 3 = 12A,

d2(B,C) = 4,

d(B,C) = min{12A;4} = 4.

TВ

A

B

C

A

18В

9

3

B

9

18A

4

C

3

12A

6A

Табл. ТВ

3.  Построим таблицу ТB следующим образом:

В каждую клетку запишем длину кратчайшего пути не более чем из трех ребер через А или В; или АВ; или через ВА. Например, d(А,А) = d(А,В) + d(В,А) = 9+9=18В.

4.  Построим таблицу ТС.

В каждую клетку запишем длину кратчайшего пути через

Похожие материалы

Информация о работе