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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

12
Путь от вершины
k
A к вершине
l
A
kl
μ
– это упорядоченная
последовательность (кортеж) дуг (или номеров вершин) с началом пути в
узле-источнике
k
A
и концом пути в узле-приёмнике
l
A
(
l
k
, – номера
концевых (граничных) вершин (пунктов) маршрута
kl
μ
):
,),(,),,( ljik
kl
K=
μ
или ljik
kl
,,,, K
=
μ
, (1.1)
где ),(
i
k
, ),(
l
j
– начальная и конечная дуги маршрута
kl
μ
(граничные,
концевые дуги).
Путь называется
элементарным, если никакая вершина в нём не
встречается более одного раза.
Путь называется
простым, если никакая дуга не входит в него
дважды. В противном случае путь является
составным.
Контур – это конечный путь, у которого начальная вершина
совпадает с конечной. Контур, как и путь, может быть элементарным,
простым и составным.
Если на месте некоторого элемента
ij
c в матрице с нет никакой
записи, то считается, что от узла-источника
i
A до узла-приемника
j
A нет
прямой связи (
∞
=
ij
с ). Указанные элементы в расчётах не используются.
Никаких записей не делается также на месте элементов
ij
c при
j
i
=
,
однако
0=
ii
c .
Цепь от пути отличается только тем, что некоторые дуги в ней могут
иметь различную направленность. Тем же отличается и
цикл от контура,
который можно рассматривать как частный случай цикла, где вместо
понятия «дуга» фигурирует понятие «ребро» [1].
Длина пути равна сумме длин дуг его составляющих и вычисляется по
формуле
,)(
),(
,
∈
=
=
kl
ji
ijkllk
cLL
μ
μ
(1.2)
где запись
kl
ji
μ
∈),(
означает, что суммируются длины дуг, образующих
данный путь
kl
μ
. Например, из табл. 1 для
3,6,4,1
0
3,1
=
μ
имеем
8323)(
3,66,44,1
0
3,1
0
3,1
=++=++== cccLL
μ
,
где
0
3,1
μ
– кратчайший маршрут от пункта
1
A к
3
A .
Если между любыми двумя вершинами существует хотя бы один

Страницы