Гамильтоновых путей и контуров
Замечание. «Внутреннее произведение вершин» пути [x1,…,xk] определяется как формальное выражение вида x2×x3×…xk-1, не содержащее две концевые вершины x1 и xk.
Шаг 1. G – данный орграф на n вершинах; А – матрица смежности с нулевыми элементами на диагонали; 
– модифицированная матрица смежности, в которой bij=b(ij)=xj, если существует дуга из xi в xj и 0 в противном случае. Положить k=1, R k=A.
Шаг 2. Положить k=k+1. Найти P k=B´P k-1.
Шаг 3. Если k=n, то диагональные элементы матрицы P n дают внутренние произведения вершин, которые соответствуют гамильтоновым контурам графа. Получить гамильтоновы контуры. Останов. Иначе перейти к шагу 4.
Шаг 4. Сделать все пути простыми, обнулив в матрице Pk все диагональные элементы, которые содержат сомножителями вершины, соответствующие данной строке. Перейти к шагу 5.
Шаг 5. Если k=n-1, то элементы матрицы Pk дают внутренние произведения вершин, которые соответствуют гамильтоновым путям графа G. Получить гамильтоновы пути. Перейти к шагу 2.
 |
Пример.Рассмотрим граф, изображенный на рис. 4.44.
Матрица смежности А этого графа имеет вид
a b c d e
a 0 1 0 1 0
A = b 0 0 0 1 1
c 0 1 0 0 1
d 0 0 1 0 0
e 1 0 1 0 0
а модифицированная матрица смежности В выглядит следующим образом:
a b c d e
a 0 b 0 d 0
b 0 0 0 d e
B = c 0 b 0 0 e
d 0 0 c 0 0
e a 0 c 0 0
Положим P1=A. Матрица P2’=B×R1 получается равной
a b c d e
a 0 0 d b b
b e 0 d+e 0 0
P2’ = c e 0 e b b
d 0 c 0 0 c
e 0 a+c 0 a c
Матрица P2 почти такая же, как P2’, только подчеркнутые элементы в P2’надо заменить нулями. Матрица P3’=B×P2 равна
a b c d e
a be dc bd+be 0 dc
b 0 dc+ea+ec 0 ea dc
P3’= c be ea+ecbd+be ea 0
d ce 0 0 cb cb
e ce 0 ad ab+cb ab+cb
Матрица Р3 получается из P3’ после замены подчеркнутых элементов нулями. Матрица Р4’=B×P3
a b c d e
a dce 0 0 bea bdc+dcb
b dce 0 ead eab+ecbdcb
P4’= c 0 0 ead bea+eab+ecbbdc
d cbe cea 0 cea 0
e cbe adc+cea abd+abeceaadc
Гамильтоновы пути можно определить по матрице Р4, которая имеет вид
a b c d e
a 0 0 0 0 bdc+cdb
b dce 0 ead 0 0
P4= c 0 0 0 bea+eab 0
d cbe cea 0 0 0
e 0 adc abd 0 0
Гамильтоновы пути abdce и adcbe, соответствующие элементу (1,5) матрицы Р4 дают гамильтоновы контуры abdcea и adcbea, если добавить замыкающую дугу (е,а). Все другие гамильтоновы пути в Р4 приводят к тем же самым контурам, и потому в графе G есть только два таких контура.
Дата добавления: 2015-04-10; просмотров: 1023;