v a rv , j , i : in teger;
Begin {Work}
v := P o r[k -l]
; {ном ер п о с л е д н е й вершины}
For j :=1 to N do I f (G [v,j]<>0) then
{Е с л и е с т ь ребро
[ v , j ] }
I f (k=N+l) and (j= l) then
{Е с л и п р о см о тр е ли в се в е р -
шины и приш ли к п е р в о й }
begin
For i := l to N do W rite (Por [i]
, ' , ' ) ; { Выводим ц и к л . В
конце н е в ы в о ди тся н а ч а ль н а я верш ина, но мы зн а е м ,
ч то она пр о см о тр е н а и замы кает ц и к л }
W riteln;
{С тр о ч к а д л я следую щ его ц и к л а }
end
e lse I f Not Is V is ite d [j] then
{Е с л и вершина н е п р о -
с м о тр е н а }
begin
Рог[k ]:=j ; I s V is ite d [j] : =true; W o rk (k + l);IsV isit-
ed
[
j
]
:= fa ls e ;
{Посещ аем ее и запуска е м "рабочую "
п р о ц е д у р у с парам етром k + 1 }
end;
End; {Work}
BEGIN {Gamilton}
Por[1]: = 1; V i s i t e d [ l ] : = t r u e ; Work(2); {Н а ч а ль н а я
п е р в а я вершина с ч и т а е т с я посещ енной — запуска ем " р а -
бочую " п р о ц е д у р у с парам етром 2 }
END; {Gamilton}
В о т и все! В р е зу л ь та те б у д е м им еть н а э к р а н е все с у щ е -
с тв у ю щ и е гам и л ьто н о вы циклы в з а д а н н о м граф е. К аж д ы й из
них н а ч и н а е тся в н а ч а л ь н о й в е р ш и н е , за к а н ч и в а е т с я в ней
*ж е и со д е р ж и т в се в е р ш и н ы граф а.
К п р и м ер у, для гр а ф а
п р о г р а м м а вы д аст с л е д у ю щ и е циклы с п о р я д к о м верш и н:
1, 2, 3, 6, 5, 4
1, 2, 5, 6, 3, 4
1, 4, 3, 6, 5, 2
1, 4, 5, 6, 3, 2.
З д е сь у к а з а н п о р я д о к ве рш и н . Р а зум ее тся, каж ды й цикл
за м ы к а е тся в 1-й в е р ш и н е , т о есть начал ьн о й .
Часть 13. Раскраски
П р е ж д е чем н а ч и н а ть вчиты ваться в стр о к и это й главы,
всем читател ям -испы тате лям с о в е т у ю взять в руки п о л и ти ч е -
с к ую к а р т у м и р а. Если в н и м а те л ьн о п р и см о тр е ться, т о м о ж -
н о за м е ти ть н е к о т о р у ю з а к о н о м е р н о с т ь р а с к р а с к и т е р р и т о -
р и й стр ан : н а к о р т е вы н е н а й д е те ни о д н о й п а р ы со се д н и х
го суд ар ств, р а с к р а ш е н н ы х в о д и н ак о вы й цвет. Н и ч е го о с о -
б е н н о го , п р а в д а ? Ведь со с е д н и е г о с у д а р с т в а для у д о б с т в а
п о -р а з н о м у о к р а ш е н ы , д а б ы не сли вал и сь их границы .
К ак ни стр ан н о, таким и вещ ам и то ж е зани м ается те ор и я гр а -
фов. П ред ставим , что политическая к а р т а м и р а — это граф.
Здесь каж дое госуд арство представляет с о б о й его верш ину, гр а-
ницы — р е б р а , а м атерики и о с тр о в а — ком поненты связности
граф а. Теперь п о п р о б у е м определиться с понятием р аскр аски
граф а. Э т о п ро извольная ф ункция £ У— эС, где V — м нож ество
верш ин граф а, а С = {1 , 2, 3, .
.., к} — конечное подм нож ество
натуральны х чисел. Бо лее просты м языком: функция р аскр аски 1
каж дой верш и не гр аф а ставит в соответствие н е к о то р о е нату-
р ал ьн о е число (р а ск р а ш и в а е т верш ины цветами из опр ед ел ен -
ной палитры). Если каждый цвет п р о н ум е р о в а ть натуральны м
числом, то тако й палитрой как р а з и вы ступает м н ож ество С.
О т с ю д а м о ж н о зам е ти ть, что ве р ш и н ы гр а ф а м о ж н о р а с -
к р а ш и в а т ь как у го д н о — хо ть все о д н и м цветом . Н а п р а ш и -
вается е щ е о д н о о п р е д е л е н и е . П р а в и л ь н о й р а с к р а с к о й г р а -
ф а н а зы в а е тс я та к а я е го р а с к р а с к а , к о гд а л ю б ы е е го две
см еж ны е ве рш и н ы р а с к р а ш е н ы в р азн ы е цвета. Т о есть f(u)*f(v)
для л ю б ы х д вух см еж ны х в е р ш и н и И
V.
Д а в а й т е ж е п о п р о б у е м н аучи ться р а с к р а ш и в а т ь гр аф ы
п р а в и л ь н о © ! В м е ст о н а зв а н и й ц в е то в б уд е м и сп о л ьзо в а ть
н а ту р а л ь н ы е числа. М е т о д п р а в и л ь н о го р а с к р а ш и в а н и я б а -
зи р уется н а т а к о й п р о с т о й идее: р а с к р а ш и в а т ь о ч е р е д н у ю
в е р ш и н у в м и н и м а л ь н о в о зм о ж н ы й цвет. Для р е а л и з а ц и и м е -
т о д а мы и сп о л ьзу е м м н о ж е с тв о цветов:
Туре С=1. .N;
ColorM atrix=array[ 1 .
.N] of С;
S=Set of С;
П о л у ч а е тс я , что к аж д о й в е р ш и н е б у д е т п р и п и с а н ц ве т в
виде числа. Д ля э то го введ ем п е р е м е н н у ю
Var C ol: ColorMatrix;
к о т о р а я п окаж е т, ч то зн а ч е н и е эл е м е н та
col
[
j
] о п р е д е л я -
ет н о м е р ц в е та в е р ш и н ы j. З д е сь
j
п р и н а д л е ж и т м н о ж е с тв у
в е р ш и н {1, 2, .
.., N }, а C o l — м н о ж е с тв у ц в е то в {1, 2, .
.., к}
п р а в и л ь н о й р а с к р а с к и гр аф а. О ч е в и д н о , ч то k < N .
Procedure Colorize(G :M atrixOfA djacencies)
; {П о -
с к о л ь к у
Col
мы о п р е д е ли ли в к а ч е с тв е гл о б а л ь н о й п е р е -
м енной, она з д е с ь о т с у т с т в у е т }
Function C o lo r(r,j :С) :in te g e r;
{Ф у н к ц и я , р е а ли зую -
щая п о и с к ц в е та д л я о дн о й вершины. З д е с ь г — номер
ц в е т а , с к о то р о го с л е д у е т и с к а ть о к р а с к у вершины
j }
Var i : in teg er;
Q: S;
{м нож е ство ц в е т о в }
Begin {Color}
Q: = t] г {
и зн а ч а ль н о м нож ество п у с т о
}
For i : =1 to j- 1 do
{П росм атри вае м вершины с меньшими
ном ерами, чем у те кущ е й }
I f G [i, j] = l then Q: =Q+ [Col [ i l l ;
{З д е с ь по луч а е м мно-
ж ество ц в е т о в , в которы е окрашены смежные с текущ ей
вершины с меньшими ном ерами}
i:= r ;
While (i inQ) do
{ Ищем минимальный ц в е т , в которы й
можем о к р а с и ть верш ину
j
}
i:= i+ l;
C olori= i;
End; {Color}
BEGIN {Colorize}
For j
:
=1 to N do Col
[
j
] :
=Color
(
1, j
) ; { Начинаем с п е р -
в о го ц в е т а }
END; {C olorize}
П р а в и л ь н а я р а с к р а с к а п о л уч е н а. Д а в а й т е р а с с м о т р и м
при м ер чи к, к о то р ы й п о м о ж е т н а м о с о з н а т ь ве сь см ы сл а л -
гор и тм а:
П о с л е за п у с к а п р о ц е д ур ы
colorize
и м еем н а вы ходе м а с -
сив
Col:
,-1 ТАБЛИЦА
Н ом ер вершины
в
скобочках
с а д
Со1[2]
с а д
с а д
C ol 5
Н ом е р цвета
соответствующ ей
і
2
і 3
І 2
3
верш ины
Н азвание цвета
Голубой
Зеленый
О ранж евый
Зеленый
О ранж евый
Т аким о б р а з о м , мы с вам и научи ли сь р а с к р а ш и в а т ь гр а -
фы п р а в и л ьн о . К счастью , э то е щ е не пик с о в е р ш е н с т в а © .
(Продолжение следует)
№ 52/275 29 декабря-5 января 2003/04
предыдущая страница 48 Мой Компьютер 2004 52 читать онлайн следующая страница 50 Мой Компьютер 2004 52 читать онлайн Домой Выключить/включить текст