книги / Теория графов и её приложения.-1

Вариант 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.

Тел. [phone].