Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 11 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

13
путь, то граф ),(
M
A
сильно связан. Минимальное число дуг, требуемое
для обеспечения сильной связности графа, равно
n [3].
Граф ),(
M
A
называется полным, если любые две вершины
соединены хотя бы в одном направлении [1]:
,),(),(
M
i
j
M
j
i
∈
⇒
∉
(1.3)
т.е. если дуги ),(
j
i не существует, то имеется дуга ),( i
j
.
Примечание. Понятие «полный граф», однако, не будем
отождествлять с равенством единице коэффициента полноты
ϕ
матрицы
c, который вводится в [3] как доля числа дуг графа m от их
максимально возможного количества:
4,056
/
12 ),1(
/
=
⋅
=
−=
ϕ
ϕ
nnm (табл. 1).
Согласно (1.3) граф на рис. 1 не является полным, а
коэффициент полноты
4,0
=
)1(
<
, однако данный граф сильно
связан.
Введённый минимум необходимых понятий и обозначений позволяет
записать формальную постановку задач, разработка достаточно
эффективных алгоритмов решения которых является основной целью
данной работы.
2. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА ГРАФЕ
2.1. Постановка задачи
На графе ),(
M
A
требуется найти такую последовательность номеров
вершин, соединяющую вершины
k
A и
l
A (путь
kl
μ
(1.1)), при которой
длина пути (1.2) будет минимальной (
0
kl
μ
).
В 1956 г. Л. Форд [4] предложил алгоритм решения задачи поиска
кратчайшего маршрута на графе. Поскольку запись исходной информации
в форме графа (рис. 1) мало приемлема для использования ЭВМ, то в [4]
отмечается возможность решения задач построения кратчайшего маршрута
большого размера «вручную». Однако возможности человека также
существенно ограничены. В [4] оценка по требуемым вычислительным
затратам
не приводится.

Страницы