книги / Теория графов и её приложения.-1
.pdfВариант 6
Определить кратчайший путь из вершины 6 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
Вариант 7
Определить кратчайший путь из вершины 7 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
201
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
Вариант 8
Определить кратчайший путь из вершины 8 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
202
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
Вариант 9
Определить кратчайший путь из вершины 9 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
203
Вариант 10
Определить кратчайший путь из вершины 10 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
Вариант 11
Определить кратчайший путь из вершины 11 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
204
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
Вариант 12
Определить кратчайший путь из вершины 12 в вершину 22 в графе достижимости охраняемых объектов:
(1,2)=3;(1,5)=5;
(2,3)=5;(2,11)=15;
(3,4)=7;(3,12)=10;
(4,13)=12;
(5,6)=3;(5,10)=12;
(6,7)=4;
(7,8)=3;(7,9)=8;
(8,9)=4;
(9,10)=6;(9,19)=3;
(10,11)=2;
(11,12)=5;(11,18)=10;
(12,13)=7;(12,17)=3;
205
(13,14)=1;
(14,15)=7;(14,16)=8;
(15,16)=3;
(16,17)=4;(16,22)=7;
(17,18)=1;(17,22)=12;
(18,19)=8;(18,21)=7;
(19,20)=10;
(20,21)=5;
(21,22)=2.
206
Учебное издание
Тюрин Сергей Феофентович
ТЕОРИЯ ГРАФОВ И ЕЁ ПРИЛОЖЕНИЯ
Практикум
Редактор и корректор И.Н. Жеганина
Подписано в печать 8.02.2016. Формат 60×90/16. Усл. печ. л. 13,0. Тираж 100 экз. Заказ № 13/2017.
Издательство Пермского национального исследовательского
политехнического университета.
Адрес: 614990, г. Пермь, Комсомольский проспект, 29, к. 113.
Тел. (342) 219-80-33.