3. Псевдопотенциальные графы
Известно [7, 8], что для того, чтобы граф был псевдопотенциальным, необходимо и достаточно существование чисел a, Д, i = 0,n, таких, что 1ij = bj - ai для всех i,j = 0,n; а также, что любой подграф псевдопотенциального графа является псевдопотенциальным.
Будем считать, что a0 = 0.
Обозначим Mj(m) = ^(Ь* -ai )k=1
- сумма длин первых j дуг гамильтонова контура m, gj = Щ - bj. Определим M(m) = max Mj(m).
1? j ? n
Известно [7, 8], что существует оптимальное решение задачи
(1) M(m) ® min ,
m
в котором сначала идут вершины с g > 0 в порядке возрастания величин Д, а затем вершины с g < 0 в порядке убывания величин Щ*.
Для доказательства этого утверждения обозначим
Mmin = min M(m), а m = (0, ii, i2, ¦¦¦ , in, 0) - оптимальный гамильто-
m
нов контур (решение задачи (1)). Тогда для него имеет место следующая система неравенств:
Mmn > bh Mmn + gii > bi2
( ) min + gii + gi2 > b3 .
Итак, пусть m = (0, i1, i2, ¦¦¦ , in, 0) - контур, являющийся решением задачи (1), то есть
Ylj >0, j = 1, 2, ¦¦¦, s, причем Д. < Д2 < ¦¦¦ < bls ,
Уi <0, j = s + 1, ¦¦¦, n, причем Щ > ai <¦¦¦ < ai .
' ij J ' r s+1 is+2 in
Тогда (3) Mmn = max
f k ^ bi1' bik+i Z giJ
_ V j =
Частным случаем псевдопотенциального графа является потенциальный граф, у которого длина любого гамильтонова контура равна нулю1. В частности, потенциальный граф обладает сле-дующими свойствами:
у потенциального графа длина любого контура равна нулю;
для n-вершинного потенциального графа существуют числа
{Я}, такие, что lij = Я - Я*, i, j = 1,n .
у потенциального графа для любой вершины сумма длин заходящих дуг по абсолютной величине равна сумме длин исходящих дуг.