68 Â

WIAT

N

AUKI

Paêdziernik 1997

N

a pierwszy rzut oka problem
Ziemia-Ksi´˝yc wydaje si´ nie-
szkodliwà zabawà. Ziemia zo-

sta∏a podzielona pomi´dzy wiele naro-
dów, z których ka˝dy posiada jedno
spójne terytorium – làd i morze. Co wi´-
cej, ka˝dy ziemski naród zaanektowa∏
terytorium na Ksi´˝ycu, tworzàc impe-
rium sk∏adajàce si´ z dwóch cz´Êci: jed-
nej na Ziemi, a drugiej na jej satelicie.
Jaka jest najmniejsza liczba kolorów, któ-
re pokryjà takà map´ w ten sposób, ˝e
obie cz´Êci danego imperium majà ten
sam kolor, ale ˝adne dwa przyleg∏e ob-
szary nie sà tej samej barwy – czy to na
Ziemi, czy na Ksi´˝ycu?

Problem ten, który po raz pierwszy

przedstawi∏em cztery lata temu [Âwiat
Nauki, czerwiec 1993] jest bardzo sztucz-
ny. Czy˝by by∏ typowym bezu˝ytecz-
nym produktem intelektualisty za-
mkni´tego w wie˝y z koÊci s∏oniowej?
Wr´cz przeciwnie. W paêdzierniku 1993
roku Joan P. Hutchinson z Macalester
College w St. Paul (Minnesota) opubli-
kowa∏a w Mathematics (vol. 66, nr 4) po-
wa˝ny przeglàdowy artyku∏ dotyczàcy
tych zagadnieƒ: „Coloring Ordinary
Maps, Maps of Empires, and Maps of
the Moon” (Kolorowanie zwyk∏ych
map, map imperiów i map Ksi´˝yca).
W jednym z jego ust´pów opisuje ona
zastosowanie powy˝szego problemu do
testowania drukowanych p∏ytek obwo-

dów scalonych. Na pomys∏ ten wpadli
badacze z AT&T Bell Laboratories w
Murray Hill (New Jersey), a istniejàce
zale˝noÊci wcale nie sà takie oczywiste.
Tym razem opowiem o mapach, im-
periach i grafach; wiele ksi´˝yców póê-
niej zaÊ zajmiemy si´ p∏ytami obwodów
scalonych.

Mapa jest uk∏adem obszarów albo na

p∏aszczyênie, albo na powierzchni ta-
kiej jak sfera. Ka˝dy obszar jest poje-
dynczà spójnà cz´Êcià p∏aszczyzny lub
powierzchni, a obszary majà wspólne
brzegi b´dàce krzywymi.

Graf to diagram utworzony z pewnej

liczby kropek, zwanych w´z∏ami lub
wierzcho∏kami, które sà po∏àczone pew-
nà liczbà linii zwanych kraw´dziami.
Grafy sà prostsze i bardziej abstrakcyj-
nie ni˝ mapy. Jednak˝e dowolnà map´
mo˝na przedstawiç w postaci grafu,
przyporzàdkowujàc ka˝demu obszaro-
wi w´ze∏, a dwa takie w´z∏y ∏àczàc kra-
w´dzià wtedy i tylko wtedy, gdy odpo-
wiadajàce obszary b´dà mia∏y wspólny
kawa∏ek granicy.

Wyobraêmy sobie w´z∏y jako stolice,

a kraw´dzie jako autostrady ∏àczàce
miasta w przyleg∏ych krajach, przecho-
dzàce przez wspólnà cz´Êç granicy. To
w∏aÊnie jest graf mapy. Pokazuje on, któ-
re obszary ze sobà graniczà, ale odrzu-
ca wszelkie niepotrzebne szczegó∏y, ta-
kie jak kszta∏t.

Graf nazywamy p∏askim, jeÊli daje si´

go narysowaç na p∏aszczyênie, tak by
jego kraw´dzie si´ nie przecina∏y. JeÊli
zaczniemy od mapy na p∏aszczyênie, jej
graf b´dzie oczywiÊcie p∏aski. Co zaska-
kuje: jeÊli mapa zostanie narysowana na
sferze lub kilku roz∏àcznych p∏aszczy-
znach albo sferach – jak to jest w przy-
padku map Ziemia-Ksi´˝yc – to otrzy-
many graf b´dzie w dalszym ciàgu
p∏aski. By to stwierdziç, wyobraêmy so-
bie map´ narysowanà na sferze. Za-
znaczmy po jednym w´êle w ka˝dym
obszarze i po∏àczmy je kraw´dzià, gdy
tylko dwa odpowiadajàce obszary b´-
dà mia∏y wspólnà granic´. Otrzymany
w ten sposób graf mo˝e byç narysowa-
ny na sferze tak, ˝e ˝adne jego kraw´-
dzie si´ nie przetnà.

Ale ka˝dy taki graf mo˝na otworzyç

i roz∏o˝yç na p∏aszczyênie. Wyobraêmy
sobie wyci´cie ma∏ej dziurki w sferze,
która nie dotyka ˝adnego w´z∏a ani te˝
˝adnej kraw´dzi grafu. Nast´pnie za-

∏ó˝my, ˝e sfera zosta∏a zrobiona z ela-
stycznego materia∏u. Mo˝na wtedy roz-
ciàgaç t´ ma∏à dziurk´, tak ˝e staje si´
ona coraz wi´ksza. Pozosta∏a cz´Êç sfe-
ry te˝ si´ wówczas rozciàga i deformu-
je, a wraz z nià graf. Odpowiednio roz-
ciàgajàc, mo˝emy jà wi´c rozp∏aszczyç
tak, ˝e powstanie ko∏o. Nak∏adajàc zaÊ
ko∏o na p∏aszczyzn´, otrzymujemy graf
mapy bez przeci´ç.

JeÊli mapa zostanie narysowana na

kilku sferach, to trzeba wykonaç powy˝-
sze operacje dla ka˝dej sfery i uzyskane
ko∏a rozmieÊciç na wspólnej p∏aszczyê-
nie, tak by si´ nie nak∏ada∏y. Otrzyma-
ny graf b´dzie niespójny – rozpadnie
si´ na kilka roz∏àcznych cz´Êci, po jednej
dla ka˝dej sfery – ale jest to ca∏kiem po-
spolita w∏asnoÊç grafów.

Innym wa˝nym przyk∏adem grafu

jest graf zupe∏ny K

n

. Ma on n wierzcho∏-

ków i jednà kraw´dê ∏àczàcà ka˝dà pa-
r´ ró˝nych wierzcho∏ków. JeÊli n jest
równe pi´ç lub wi´cej, to graf K

n

nie jest

p∏aski.

Map´ – czy to na p∏aszczyênie, sfe-

rze, kilku sferach, czy gdziekolwiek –
nazywamy k-kolorowalnà, jeÊli jej obsza-
ry mo˝na zamalowaç nie wi´cej ni˝ k
kolorami, tak ˝e obszary majàce wspól-

REKREACJE MATEMATYCZNE

Ian Stewart

Imperia na Ksi´˝ycu

DOWOLNÑ MAP¢ mo˝na przedstawiç

w formie „grafu”, zaznaczajàc

jeden w´ze∏, powiedzmy – stolic´,

w ka˝dym kraju i ∏àczàc te miasta, które sà

na terytoriach majàcych wspólne granice.

Problem kolorowania wymaga

znalezienia ró˝nych barw

dla ka˝dego z dwóch po∏àczonych miast.

GRAF ZUPE¸NY K

5

ma pi´ç w´z∏ów,

a ka˝dy z nich jest po∏àczony

z wszystkimi pozosta∏ymi.

Tak wi´c graf ten

wymaga pi´ciu kolorów.

GRAF ROLFA SULANKE ma gruboÊç dwa

i potrzebuje dziewi´ciu kolorów.

Jego dolna cz´Êç zawiera zupe∏ny graf K

8

.

MICHAEL GOODMAN

MICHAEL GOODMAN

MICHAEL GOODMAN

Â

WIAT

N

AUKI

Paêdziernik 1997 69

nà granic´ b´dà mia∏y ró˝ne barwy. Ob-
szary, które spotykajà si´ w jednym
punkcie lub w skoƒczonej ich liczbie,
mogà, jeÊli to konieczne, mieç ten sam
kolor. Analogicznà w∏asnoÊç grafów
mo˝na bardzo podobnie sformu∏owaç.
Graf nazywamy k-kolorowalnym, gdy
jego wierzcho∏ki dajà si´ pokolorowaç
za pomocà najwy˝ej k kolorów, tak ˝e
wierzcho∏ki po∏àczone kraw´dziami b´-
dà mia∏y ró˝ne kolory.

Jak ∏atwo zauwa˝yç, mapa jest k-ko-

lorowalna wtedy i tylko wtedy, gdy jej
graf jest k-kolorowalny. Wystarczy jed-
nak pomalowaç ka˝dà stolic´, czyli
ka˝dy wierzcho∏ek grafu, kolorem od-
powiadajàcego kraju. Najni˝szà takà
liczb´ k nazywamy liczbà chromatycznà
grafu. Wskazuje ona najmniejszà liczb´
kolorów potrzebnà do pomalowania
tego grafu, a wi´c tak˝e odpowiadajà-
cej mu mapy. OczywiÊcie K

n

ma liczb´

chromatycznà n, poniewa˝ ka˝dy wierz-
cho∏ek tego grafu jest po∏àczony z ka˝-
dym innym, tak wi´c ˝adne dwa jego
wierzcho∏ki nie mogà byç tego samego
koloru.

W 1989 roku brytyjski matematyk

Percy John Heawood przedstawi∏ pe-
wien blisko spokrewniony z ziemsko-
-ksi´˝ycowymi mapami problem. Sce-
nà w nim jest sama Ziemia, ale tym ra-
zem ka˝dy kraj stanowi cz´Êç imperium
sk∏adajàcego si´ co najwy˝ej z m krajów
i ten sam kolor musi byç u˝yty dla ka˝-
dego kraju danego imperium, ponadto
– jak poprzednio – przyleg∏e obszary
majà inne kolory. (Z za∏o˝enia kraje da-
nego imperium si´ nie stykajà.) Taka
mapa nazywana jest m-perium*. Hea-
wood udowodni∏, ˝e dowolne m-perium
mo˝na zawsze pokolorowaç za pomocà
6m kolorów dla m wi´kszych lub rów-
nych 2 – bez wzgl´du na liczb´ impe-
riów przedstawionych na mapie.

Poniewa˝ dowolne m-perium jest

szczególnym typem mapy, ma ono
zwiàzany z nià graf, w którym poszcze-
gólne w´z∏y odpowiadajà krajom. Jed-
nak˝e nie jest ju˝ prawdà, ˝e ka˝de do-
puszczalne kolorowanie grafu mapy
odpowiada kolorowaniu imperium.
Podstawowe zasady kolorowania gra-
fu nie zawsze bowiem prowadzà do te-
go, ˝e w´z∏y pochodzàce od tego same-
go imperium majà ten sam kolor.
Trudno jest sprawiç, by warunek ten
spe∏nia∏o samo pokolorowanie grafu
mapy. Zamiast tego zostaje zmodyfi-
kowana konstrukcja grafu, tak by zasa-
dy kolorowania by∏y automatycznie
poprawne.

A robi si´ to tak: w grafie m-perium

zwiàzanym z danà mapà m-perium je-
den w´ze∏ odpowiada jednemu impe-
rium, a nie tylko jednemu obszarowi. Je-

Êli wydaje si´ to zbyt skomplikowane, to
przyjmijmy, ˝e ka˝dy w´ze∏ odpowiada
imperatorowi. Dwa w´z∏y po∏àczone sà
kraw´dzià wtedy i tylko wtedy, gdy od-
powiadajàce im imperia majà co najmniej
jednà par´ przyleg∏ych krajów. Graf
m-perium mo˝na uwa˝aç za „graf inwa-
zyjny” w∏adców, którzy walczà ze sobà
przez wspólnà granic´: jeden w´ze∏ na
imperatora, jedna kraw´dê na ka˝dà
mo˝liwà dwustronnà wojn´.

Konceptualnie, graf m-perium otrzy-

mujemy ze zwyczajnego grafu dzi´ki
uto˝samieniu wszystkich w´z∏ów nale˝à-
cych do danego imperium, tj. rysujàc je
w tym samym miejscu. Konstrukcja ta-
ka cz´sto prowadzi do wielokrotnych
kraw´dzi. Niepotrzebne kraw´dzie tego
typu sà usuwane i zostaje tylko jedna.
Uto˝samienie wszystkich w´z∏ów dane-
go imperium gwarantuje, ˝e zostanà one

pokolorowane tym samym kolorem, tak
wi´c liczba potrzebnych barw do poma-
lowania m-perium jest równa liczbie
chromatycznej grafu jego m-perium.

W roku 1983 Bradley W. Jackson

z San Jose State University oraz Gerhard
Ringel z University of California w San-
ta Cruz zastosowali powy˝sze podej-
Êcie do udowodnienia, ˝e liczba 6m
z twierdzenia Heawooda jest najlepszà
mo˝liwà. Dokonali tego pokazujàc, ˝e
mo˝na znaleêç m-perium, którego graf
jest zupe∏nym grafem K

6m

. Poniewa˝

oczywiÊcie K

6m

wymaga 6m kolorów, to

istnieje m-perium, którego nie da si´ za-
malowaç mniej ni˝ 6m kolorami.

Ziemsko-ksi´˝ycowà map´ mo˝na

uwa˝aç za szczególnego typu dwu-pe-
rium z troch´ dziwnà geometrià pod-
stawowà – dwie sfery – co powoduje
rozci´cie ka˝dego dwu-perium na dwa

GRAF ZIEMSKO-KSI¢˚YCOWY dla oÊmiu cesarstw ma dwa roz∏àczne kawa∏ki (a i b),

które sà p∏askie (ich linie si´ nie przecinajà). Odpowiadajàcy graf dwu-periów (c)

zosta∏ utworzony przez na∏o˝enie w´z∏ów nale˝àcych do tego samego imperium.

Ten rysunek jest zupe∏nym grafem K

8

i wymaga oÊmiu kolorów.

A

rtyku∏ poÊwi´cony alfamagicznym
kwadratom [Âwiat Nauki, marzec

1997] ujawni∏ pewnà liczb´ interesujà-
cych drobiazgów. Delia T. Lewit z Hun-
tington Park (Kalifornia) zwróci∏a uwag´
na dziwny schemat wyst´pujàcy we
wszystkich przyk∏adach magicznych kwa-
dratów 3 x 3 (alfamagicznych lub nie). Je-
Êli liczby po∏àczymy w porzàdku rosnàcym, to pojawia si´ ten sam wielokàtny kszta∏t
w ka˝dym z kwadratów (byç mo˝e odwrócony lub odbity). Czy ktoÊ mo˝e to udo-
wodniç lub obaliç t´ hipotez´ dla magicznych kwadratów 3 x 3?

Z kolei Lee Sallows z Nijmegen w Holandii przes∏a∏ mi swoje najnowsze rozwa-

˝ania na temat kwadratów magicznych. Wspomina on tak˝e problem-wyzwanie
postawiony w roku 1996 przez Martina Gardnera w czasopiÊmie Quantum: skon-

struuj kwadrat magiczny 3 x 3 sk∏adajàcy si´ z dziewi´ciu ró˝-
nych figur. Nagrodà jest 100 dolarów. Do tej pory najlepszà pró-
bà wydaje si´ prawie trafienie z magicznà sumà 1472 – sam

w sobie doskona∏y kwadrat – dla wszyst-
kich rz´dów, kolumn i jednej przekàtnej,
ale nie drugiej. A Julius Telesin z Uniwer-
sytetu Bena-Guriona w Izraelu przes∏a∏
fascynujàcà analiz´ „magicznych Dawi-
dów”. Na przedstawionym obok ka˝da li-
nia prosta po zsumowaniu daje 26.

SPRZ¢˚ENIE ZWROTNE

4 9 2

3 5 7

8 1 6

4 9 8

11 7 3

6 5 10

8 19 18

25 15 5

12 11 22

CIEKAWE WZORY pojawiajà si´

w kwadratach magicznych 3 x 3.

127 46 58

2 113 94

74 82 97

2 2 2

2 2 2

2 2 2

3

10 5 4 7

6 8

12 1 2 11

9

PRAWIE TRAFIENIE

kwadratu magicznego

(powy˝ej) i magiczny

Dawid (z prawej).

MICHAEL GOODMAN

MICHAEL GOODMAN

a

b

c

fragmenty. Jej graf sk∏ada si´ z dwóch
roz∏àcznych p∏askich grafów; jeden
z mo˝liwych uk∏adów zosta∏ przedsta-
wiony na rysunku powy˝ej. (Zaokrà-
glony kszta∏t nie ma nic wspólnego
z Ziemià ani Ksi´˝ycem, po prostu tak
by∏o ∏atwiej rysowaç.)

Za∏ó˝my teraz, ˝e myÊlimy o grafie

Ziemia-Ksi´˝yc jako o grafie dwu-pe-
rium, tak wi´c w´z∏y nale˝àce do tego
samego imperium sà uto˝samiane, two-
rzàc ostatni graf na rysunku. Jak ∏atwo
zauwa˝yç, otrzymany graf nie musi byç
p∏aski i rzeczywiÊcie taki nie jest. Jed-
nak˝e jest on prawie p∏aski. Sposób,
w jaki zosta∏ skonstruowany, pokazuje,
˝e jego kraw´dzie mogà byç rozdzielo-
ne na dwa podzbiory, z których ka˝dy
wraz w pierwotnym zbiorem w´z∏ów
tworzy p∏aski graf. Te dwa zbiory to
kraw´dzie dwóch poprzednich grafów.

Mówimy, ˝e taki graf ma gruboÊç

dwa. Ogólnie graf ma gruboÊç t, jeÊli je-
go kraw´dzie mo˝na podzieliç na t pod-
zbiorów (lecz nie na mniej) w taki spo-
sób, ˝e ka˝dy z tych podzbiorów tworzy
p∏aski graf.

Tak wi´c ka˝da ziemsko-ksi´˝ycowa

mapa sk∏ada si´ z dwóch oddzielnych
p∏askich map – jednej na Ksi´˝ycu oraz
jednej na Ziemi – i ma gruboÊç dwa. Od-

wrotnie, ka˝dy graf gruboÊci dwa odpo-
wiada ziemsko-ksi´˝ycowej mapie (cho-
cia˝ pewne obszary mogà byç niczyje).

Poniewa˝ ziemsko-ksi´˝ycowy graf

jest specjalnego rodzaju grafem dwu-
-perium, twierdzenie Heawooda suge-
ruje, ˝e do pomalowania dowolnego
ziemsko-ksi´˝ycowego grafu wystarcza
12 kolorów. Lecz nie znaczy to, ˝e 12
kolorów jest koniecznych. A to dlatego,
˝e nie ka˝de dwu-perium odpowiada
ziemsko-ksi´˝ycowej mapie; któreÊ im-
perium w tym dwu-perium mo˝e mieç
oba terytoria na Ziemi.

W rzeczywistoÊci ˝aden ze znanych

grafów dwu-perium, który wymaga 12
kolorów, nie odpowiada ziemsko-ksi´-
˝ycowej mapie. Istnieje zatem mo˝li-
woÊç, ˝e wystarczy mniej ni˝ 12 kolo-
rów na pokolorowanie dowolnego
ziemsko-ksi´˝ycowego grafu. Na przy-
k∏ad grafy zupe∏ne K

9

, K

10

, K

11

oraz K

12

sà

grafami dwu-periów, ale majà one gru-
boÊç trzy i nie mogà byç ziemsko-ksi´-
˝ycowymi grafami. GruboÊç K

n

wyno-

si trzy, gdy n = 9 lub 10, a w pozosta∏ych
przypadkach jest równa najwi´kszej
liczbie ca∏kowitej nie przekraczajàcej
(n + 7)/6.

Ostatni graf na rysunku jest grafem

zupe∏nym K

8

, tak wi´c K

8

ma gruboÊç

dwa. Oznacza to, ˝e mo˝na go przed-
stawiç w formie ziemsko-ksi´˝ycowego
grafu, dowodzàc, i˝ potrzeba co najmniej
oÊmiu kolorów, by rozwiàzaç nasz ziem-
sko-ksi´˝ycowy problem. Rolf Sulanke
z Uniwersytetu Humboldta w Berlinie
podwy˝szy∏ to dolne ograniczenie do
dziewi´ciu, pokazujàc, ˝e graf przedsta-
wiony powy˝ej ma gruboÊç dwa, a jego
liczba chromatyczna wynosi dziewi´ç.
Tak wi´c problem ziemsko-ksi´˝ycowy
nie ma jednoznacznej odpowiedzi: jest
to 9, 10, 11 albo 12.

Mo˝na tak˝e przymierzyç si´ do pro-

blemu Ziemia-Ksi´˝yc-Mars, gdzie ka˝-
dy w∏adca ma trzy terytoria, po jednym
na ka˝dej z planet. Te mapy sà szcze-
gólnego typu mapami trzy-periów i ich
grafy zawsze majà gruboÊç trzy.

Problem kolorowania map tego typu

jest dobrà zabawà, ale jego znaczenie
praktyczne jest niewielkie. W nast´p-
nym odcinku poka˝´, jak poj´cie gru-
boÊci grafu stosuje si´ do testowania ob-
wodów scalonych.

T∏umaczyli

Zdzis∏aw Pogoda i Robert Wolak

* W j´zyku angielskim nazwa ta jest grà s∏ów:
„m-pire” brzmi tak samo jak „empire”, czyli
imperium (przyp. t∏um.).