Нахождение кратчайших маршрутов

106. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.
Рис. 4. Граф для задачи 106

107. На рис. 5 показана транспортная сеть, соединяющая 13 городов и расстояния между ними. Считая возможным передвижение лишь из городов с меньшими номерами в города с большими номерами, найти кратчайший маршрут между городами 1 и 13.

108. Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 10. На рис. 6 показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами (первое число – из пункта с меньшим номером в пункт с большим номером, второе число – в обратном направлении). Определить маршрут доставки груза, которому соответствуют наименьшие затраты.

Решить задачу, если перевозки осуществляются от пункта с большим

номером к пункту с меньшим номером и требуется перевести груз из 13-го пункта в 1-й.

Варианты значений параметров приведены в таблице. Длина дуги равная µ означает, передвижение в данном направлении невозможно и на графе ее не показывают.

 

Таблица 1

Варианты значений параметров для задач 108, 109, 118, 119, 121

Вариант

a

b

c

d

e

f

g

h

i

j

k

l

m

n

а)

µ

µ

µ

µ

б)

µ

µ

µ

в)

µ

µ

µ

µ

г)

µ

µ

µ

д)

µ

µ

µ

µ

е)

µ

µ

µ

µ

 

109. Для сети дорог, показанной на рис.7, для значений параметров, приведенных в таблице, определить кратчайшие пути между любыми двумя пунктами. Указать маршруты и их длины из 1-го пункта в 6-й, из 4-го во 2-й, из 7-го в 4-й.

110. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. 8).
	Рис. 8. Граф для задачи 110

Обходы графов

111. Проверить на эйлеровость и найти минимальное множество покрывающих цепей для графа, изображенного на рис. 9.

Рис. 9	Рис. 10

112. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.

113. Найти остов минимального веса взвешенного графа (рис. 10).

114. Найти упорядоченный лес, соответствующий бинарному дереву, изображенному на рис. 11.

115. Найти хроматическое число графа (рис. 12).

116. Найти толщину графа (рис. 13).

 

Рис. 11	Рис. 12	Рис. 13

 

117. Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта М в пункт N, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут (рис. 14)?

Рис. 14. Граф путешествия по историческим местам задачи 117

118. Районной администрацией принято решение о газификации одного из небольших сел района, имеющего 12 жилых домов. Расположение домов указано на рисунке 15. Числа в кружках обозначают условный номер дома. Узел 13 является газопонижающей станцией. На рисунке показано также возможное расположение трубопроводов и длины участков (первое число). Длина участка, равная µ значит, что в этом место прокладывать трубопровод нельзя. Разработать такой план газификации села, чтобы общая длина трубопровода была наименьшей.

Варианты значений параметров приведены в таблице 1.

 

119. Решите задачу коммивояжера для 5 городов, если матрица попарных расстояний между городами имеет следующий вид:

№
	A	f	J	B	I
	f	H	l	k	D
	E	l	F	M	g
	C	k	A	B	j
	J	K	g	j	L