Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

4. AZ ÖTSZÍN PROBLÉMA

4. AZ ÖTSZÍN PROBLÉMA

Most bebizonyítjuk a már említett ötszín tételt, amely szerint: Öt színnel már bármilyen normál térkép jól színezhető a gömbön. Megmutatjuk, hogy ezt az állítást elegendő olyan normál térképekre bizonyítani, amelyeken minden ország elemi felület, és minden csúcspontból pontosan háromfelé indul határvonal. Nevezzük el az ilyen térképeket szabályosaknak!

I. Legyen normál térképünkön L

L egy nem elemi felületország, mint pl. a 7/a. ábrán. Az L L belsejében levő országcsoportokat kössük össze az L L -et körülvevő határvonalhoz vezető útszakaszokkal (szaggatott vonalak). Ezeket a szakaszokat bővítsük ki egy-egy L L -ben fekvő országgá (7/b. ábra). Így L L -ből elemi felület lesz. A felvett új L_1 L 1 és L_2 L 2 ország a többi ország között eredetileg fennálló szomszédosságokat nem szüntette meg, ha tehát az így módosított térkép 5 színnel jól színezhető, akkor az eredeti is.

II. Ha van a normál térképen olyan P

P csúcspont, amelyből háromnál többfelé indul határvonal (8/a. ábra),

akkor rajzoljunk köréje olyan kört, amelybe a P

P csúcsponton kívül más csúcspont nem esik, és amely a P P -ből induló határvonalakat csak egy-egy pontban metszi (8/b. ábra). E kör belsejét csatoljuk az egyik P P körüli országhoz (8/c. ábra). Ezzel szomszédosságot nem szüntettünk meg, esetleg létrehoztunk. Ha tehát az így módosított térkép 5 színnel jól színezhető, akkor az eredeti is. Ez után a módosítás után előfordulhat, hogy egy új él egy országon belül halad; ha pl. egy L L ország a P P pont körül többször is felbukkan (9/a. és 9/b. ábra). Az ilyen él fölösleges, és ezért töröljük (9/c. ábra).

Az I. és II. lépések ismételt alkalmazásával minden normál térkép szabályossá alakítható, és – amint láttuk – az eredeti normál térkép jó színezéséhez sem kell több szín, mint az I. és II. lépések ismételt alkalmazásával nyert szabályos térkép jó színezéséhez.

Megemlítjük, hogy ha a gömb egy szabályos térképén kettőnél több ország van, akkor közöttük nincs olyan, amelynek határvonalán csúcspont ne volna. Ekkor tehát minden határvonal élekből összerakható. Az is igaz, hogy szabályos térképen nincs csupán egy éllel határolt ország. Mindkét állítás belátását az olvasóra bízzuk.

Ezek után azt fogjuk bizonyítani, hogy egy tetszőleges, a gömböt befedő T

T szabályos térkép 5 színnel jól színezhető. Jelöljük T T országainak számát l l -lel, éleinek számát é é -vel és csúcspontjainak számát c c -vel! T T minden országa elemi felület, tehát Euler tétele szerint

l+c=é+2.
l + c = é + 2 .

Számoljuk össze a csúcspontok segítségével az éleket! T

T minden csúcspontjához 3 különböző él illeszkedik. Minden él pontosan két csúcsponthoz illeszkedik, ti. a két végpontjához. Ezért igaz, hogy

3c=2é.
3 c = 2 é .

Ha az Euler-egyenlőség mindkét oldalát 6-tal szorozzuk, és 6c

6 c helyébe 4é 4 é -t írunk, akkor a következőre jutunk:

6l=2é+12.
6 l = 2 é + 12 .

(∗) ( )

Ebből viszont az következik, hogy T

T -nek van 6-nál kevesebb éllel határolt országa. Tegyük fel ugyanis az ellenkezőt! Számozzuk meg az országokat az 1, 2, …, l l számokkal, és jelöljük h_i h i -vel az i i -edik országot határoló élek számát! Minthogy minden él két különböző országnak közös határszakasza, h_1+h_2+…+h_l=2é h 1 + h 2 + + h l = 2 é . Feltevésünk szerint minden i i -re h_i≥6 h i 6 , tehát a bal oldalt nem növeljük, ha minden h_i h i helyett 6-ot írunk. Ekkor azt kapjuk, hogy 6l≤2é 6 l 2 é . Ez pedig lehetetlen, mert (∗) ( ) szerint 2é 2 é 12-vel kevesebb, mint 6l 6 l . Tehát T T tartalmaz 2, 3, 4 vagy 5 éllel határolt országot.

Ha T

T tartalmaz egy kétélű L L országot, akkor azzal pontosan két másik ország szomszédos (10/a. ábra). Csatoljuk L L -et valamelyik szomszédjához, pl. L_1 L 1 -hez (10/b. ábra)!

Így T

T -ből egy szabályos T^′ T térképet állítottunk elő. Elég kimutatni, hogy T^′ T 5 színnel jól színezhető, Ebből ugyanis következik, hogy T T 5 színnel jól színezhető, mert T^′ T színezésekor L_1 L 1 -hez és L_2 L 2 -höz az 5 színből kettőt használunk fel. A többi 3 szín bármelyikével színezhettük az újból visszaállított L L országot, és máris jól színeztük T T -t 5 színnel.

Ha T

T tartalmaz egy háromélű L L országot, akkor azzal pontosan 3 ország szomszédos. Az előbbi utat követve, L L visszaállításakor még mindig 2 szín közül választhatunk.

Ha T

T tartalmaz egy négyélű L L országot, akkor azzal 3 vagy 4 ország lehet szomszédos, amint azt a 11/a. és 11/b. ábra mutatja. Az előbbi utat most is követhetjük, de ahhoz, hogy T^′ T ismét szabályos legyen, a 11/a. ábra esetén L L -et nem szabad L_2 L 2 -höz csatolnunk. A visszaállításkor L L számára még mindig marad 2, ill. 1 szín.

Ha T

T tartalmaz egy ötélű L L országot, akkor a vele szomszédos országok között biztosan van kettő, amelyek nem szomszédosak. Mert ha pl. L L szomszédai L_1 L 1 , L_2 L 2 , L_3 L 3 , L_4 L 4 , L_5 L 5 , és L_2 L 2 szomszédos L_4 L 4 -gyel, akkor a 12. ábrából

látható, hogy L_3

L 3 nem lehet szomszédos sem L_1 L 1 -gyel, sem L_5 L 5 -tel. T^′ T -t most L L két élének törlésével állítjuk elő: L_1 L 1 és L_3 L 3 felé törlünk egy-egy élt. Ha T^′ T jól színezhető 5 színnel, akkor T T is, mert T^′ T színezésekor L L szomszédaihoz mindössze 4 színt használunk fel (L_1 L 1 és L_3 L 3 ugyanazt a színt kapja), és így L L számára a visszaállításkor marad még egy szín.

Okoskodásunk szerint elegendő azt bizonyítanunk, hogy a felsorolt redukciókkal nyert T^′

T jól színezhető 5 színnel. De T^′ T ismét szabályos térkép, tehát érvényes rá a (∗) ( ) összefüggés, amiből viszont következik, hogy T^′ T szintén tartalmaz 2, 3, 4 vagy 5 élű országot. Ennélfogva redukciós eljárásunkat addig folytathatjuk, amíg csupán 5 ország nem marad. Azt 5 színnel tudjuk jól színezni, és így eljárásunkból következik, hogy T T is jól színezhető 5 színnel. Az I. és II. figyelembevételével pedig azt nyertük, hogy bármilyen normál térkép 5 színnel jól színezhető.