Программирование
В
графском
оарке
Юрий Д О В ГА Н Ь
г
В прошлый раз мы остановились на проблеме эйлеровых циклов в графах. С большой долей
серьезности не побоюсь назвать ее «эйлеровой проблемой». Почему так? Давайте на некоторое
время перенесемся в далекий 1736 год.
Продолжение, начало см. в М К Ne 33-34, 38, 43, 46, 48 (256-257, 261, 266, 269, 271)
И
м ен н о в этом году великий м атем ати к
Леонард Эйлер
д о -
казал н е возм о ж н о сть сущ ествован ия р еш ения зад ач и о
кенигсбергских м остах. Закл ю чае тся за д а ч а в следую щ ем .
Го р о д К енигсберг (более известный н ам сей час как К али-
нинград) исторически поделен н а четы ре части: п равы й и левый
б е р е га речки П регел ь и д ва остр о ва. Разн ы е части этого го р о -
д а в то врем я соединялись сем ью м остам и. Т р е б о в а л о сь найти
м ар ш р ут, которы й бы проход ил п о каж дом у м осту р о в н о один
р а з и в итоге заканчи вался бы в н ачал ьн о й точке пути.
I
I
I
I
Н а р и сун ке о тч е тл и в о видны все 4 ч асти г о р о д а зе л е н о -
го цвета, р е ч к а и 7 м о с т о в ж е л то го цвета. В виде гр а ф а го-
р о д м о ж н о п р е д ста в и ть с л е д у ю щ и м о б р а з о м :
(3 )
П усть А , В, С , О — верш и н ы , с о о тв е т с тв у ю щ и е частям К е -
ни гсбер га. Р е б р а гр а ф а п р е д с та в л я ю т с о б о ю м осты , к о т о -
ры е с о е д и н я ю т р а з н ы е ч асти го р о д а . В о зл е каж д о й в е р ш и -
ны в с к о б о ч к а х у к а з а н а ее сте пе н ь — ко л и че ство м о сто в, к о -
то р ы е с о е д и н я ю т эту часть г о р о д а с с о се д н и м и частям и. И дея
д о к а за т е л ь с т в а н е в о зм о ж н о с ти т а к о го м а р ш р у т а с о с то и т в
след ую щ ем : п ри п о с е щ е н и и каж д о й в е р ш и н ы м осту, п о к о -
т о р о м у мы во ш л и в часть го р о д а , д о л ж ен с о о тв е т с тв о в а ть
м ост, п о к о т о р о м у мы ее покинем . Д руги м и сл о вам и , кол и -
ч ество р е б е р , инцидентны х каж д о й в е р ш и н е д о л ж н о бы ть чет-
ным, что и д о к а з а л Э й л е р в сво е й те о р е м е , о го р ч и в всех с в о -
их п р е д ш е стве н н и ко в. В о т та к а я в о т гр устн ая и сто р и я © .
Т епер ь м а ш и н а вр ем е н и н е се т н а с в 1 8 5 9 год. Д р уго й м а -
те м атик, н о сей р а з и р л ан д е ц , сэр
Уильям Гамильтон,
п р и д у-
м ал игру, в к о т о р о й т р е б о в а л о с ь о б о й т и цикл всех р е б е р
д о д е к а э д р а (ничего с е б е и гр а © ), п о с е щ а я к а ж д ую в е р ш и н у
единож ды . Разум ее тся, долж ны б ы ть п о с е щ е н ы все верш ины .
К а к о к а за л о с ь , сэр у Гам и л ьто н у б о л ь ш е п о в е зл о , чем Э й л е -
р у — цикл о н таки н а ш е л , хо ть и не б е з усилий. С е й ч а с и мы
с вам и, д о р о ги е читатели, п о и гр а е м в и н те р е с н у ю и гру — н а -
хо ж д е н и е гам и л ьто н о вы х ци клов гр а ф а © .
Часть 12. Гамильтоновы циклы и гамилылвновы графы
И так, га м и л ьто н о в ы м ци кло м в гр аф е н а зы в а е тс я цикл, к о -
то р ы й с о д е р ж и т к а ж д ую в е р ш и н у э то го гр а ф а (то есть п р о -
хо д ит п о всем в е р ш и н а м п о о д н о м у разу). С л е д о в а т е л ь н о ,
граф , с о д е р ж а щ и й га м и л ьто н о в цикл, н а зы в а е тс я
гамильто-
новым графом.
Т аких ци клов в гр а ф е м о ж е т бы ть несколько.
Д остаточн ы м условием «гамильтоновости» граф а м ож ет слу-
жить такая теорем а: если в граф е с N верш инам и для лю бы х его
двух несм еж ны х ве р ш и н v l и v 2 с п р а в е д л и в о н е р а в е н ст в о
St(vl)+St(v2]>N,
где St(vi) — степень і-й верш ины, то в нем сущ ест-
вует цикл Гамильтона. П оскольку те о р е м а о то б р а ж а е т лиш ь дос-
таточны е условия сущ ествования гамильтоновых циклов в граф е,
то найдутся и такие экземпляры, которы е не удовлетворяю т не-
равенству теорем ы , но в то ж е время являются гамильтоновыми.
Другими словами, если н еравенство справедливо, т о граф га р а н -
ти р о ван н о будет содерж ать гамильтонов цикл. В противном же
случае мы не м ож ем утверж дать наверняка отсутствие оных.
Пускай но входе имеется связный неориентированный
граф С с N вершинами. Требуется найти все гамильтоновы
циклы графа G, если таковые в нем имеются.
К б о л ь ш о м у н а ш е м у с о ж а л е н и ю , н а у к е п о к а е щ е н е и з-
вестны эф ф ективны е м етод ы р е ш е н и я п о с та в л е н н о й зад ачи.
П о э т о м у п р е д л а га е тся в о с п о л ьзо в а ть ся «д еш евы м и се р д и -
ты м » м е то д о м п е р е б о р а с в о зв р а т о м , в н а р о д е и м е н уем ы м
как
back-tracking алгоритм.
А выглядит он с л е д ую щ и м о б р а з о м . Н а ч и н а я с о п р е д е -
л е н н о й ве рш и н ы (пускай это б у д е т в е р ш и н а с н о м е р о м 1) б у -
д е м про д ви гаться вп е р е д по граф у, вклю чая о ч е р е д н о е р е б -
р о в га м и л ьто н о в цикл. П р и н ай д ен н ы х п ер вы х
к
к о м п о н е н т
р е ш е н и я р а с с м а т р и в а е м р е б р а , к о т о р ы е вы ходят из п о с л е д -
ней верш и ны . Если н а х о д и м р е б р о , к о т о р о е вед ет в н е уч те н -
н у ю р а н е е в е р ш и н у, д о б а в л я е м н о в у ю в е р ш и н у в цикл — о н а
ста н о в и тся
просмотренной,
(к+1) к о м п о н е н та р е ш е н и я при
это м пол учен а. П р и о тсутстви и та к о й ве р ш и н ы в о з в р а щ а е м -
ся к пре д ы д ущ е й и и щ е м д ругие см еж ны е с ней. Ц икл с ч и та -
ется
найденным,
если п р о с м о т р е н ы все в е р ш и н ы гр аф а, и из
п осл е д н е й м о ж н о д о стичь н ачал ьн о й . Т а к о й цикл м о ж н о вы-
вести н а э к р а н и п р о д о л ж и ть п о и ск других.
Д а в а й т е п о п р о б у е м за п и с а т ь все это н а и н о п л а н е тн о м
язы ке © .
В с п о м н и м н е к о то р ы е гл о б а л ь н ы е типы:
T y p e M a t r ix O f A d ja c e n c ie s = a r r a y [ 1 .
. N , 1 .
. N ] o f i n t e -
g e r ;
T y p e A r B o o l= a r r a y [ 1 . -N ] o f b o o le a n ;
T y p e M a t r i x = a r r a y [ l . .N ] o f i n t e g e r ;
А те п е р ь в п е р е д !
P ro c e d u re G a m ilto n (G : M a t r i x O f A d j a c e n c ie s ); {H a
в хо де гр а ф , п р е д ста в ле н н ы й м атр иц ей см еж ностей }
V a r Р о г : M a t r i x ; {М а с с и в , в кото ром б у д е т ф и кси ро-
в а ть с я п о р я д о к о б хо д а верш ин}
I s V i s i t e d : A r B o o l; {М а с с и в , в котором ф и кси рую тся
посещенные вершины}
P ro c e d u re W ork (k : i n t e g e r ) ; { " Р а б о ч а я" п р о ц е д ур а с
парам етром к — номером и те р а ц и и }
М П И К О М П Ь Ю Т Е Р
предыдущая страница 47 Мой Компьютер 2004 52 читать онлайн следующая страница 49 Мой Компьютер 2004 52 читать онлайн Домой Выключить/включить текст