Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. A 19. század közepe – térképek

2. A 19. század közepe – térképek

Közismert, hogy a politikai térképeken a szomszédos országokat különböző színnel ábrázolják, hogy az országok közti határok jól láthatóak legyenek. (Eltekintünk attól, hogy egyes országok több, nem összefüggő részből is állhatnak.) Térképészek már rég észrevették, hogy ehhez 4 szín mindig elég, és mintegy másfél évszázada jöttek rá, hogy ennek a „sejtésnek” a bizonyítása nem az ő tudományuktól, hanem a matematikától várható. Már a 19. században be tudták bizonyítani, hogy 5 színnél több nem kell, de az eredeti sejtés bizonyítására kb. 1975-ig várni kellett.

5. ábra.

Az e kérdéssel foglalkozó művek általában azzal kezdik vizsgálataikat, hogy áttérnek egy másik gráfra: szemléletesen úgy képzelhetjük el, hogy minden országban bejelöljük a fővárost, majd a szomszédos országok fővárosait olyan vasútvonalakkal kötjük össze, melyek csak a két ország közös határát metszik át. (Ezt mutatja az 5. ábra, bár e sorok írásakor (2000. elején) Budapestről Ljubljanába még csak Horvátországon keresztül lehetett utazni, egy élt az ábra második és harmadik részén látható gráfban megelőlegeztünk…) Így a térképek tartományainak (országainak) színezése helyett a síkbarajzolható gráfok (ld. alább) pontjainak a színezésével foglalkoznak, vagyis azzal, hogy hány szín kell egy gráf pontjainak megszínezéséhez, ha szomszédos (azaz éllel összekötött) pontok nem kaphatnak azonos színt.

Ez a konstrukció nagyon hasonlít az első szakaszban leírtakhoz, mert itt is kölcsönösen egyértelmű megfeleltetés létesíthető a két gráf (a „politikai” és a „vasúti” térkép) élei között. Annyival általánosabb azonban, hogy itt a „vasúti” térképek vizsgálata során olyan gráfokkal is találkozhatunk, melyekben első- vagy másodfokú pontok is vannak – gondoljunk olyan országokra, pl. Vatikán, ill. Mongólia, melyek csak egy, ill. két országgal szomszédosak.

6. ábra.

Szemléltessük az első ábrán látható szabályos poliéderek élhálóját a 6. ábrán látható módon - ezzel a különleges „vetítéssel” síkbarajzolható gráfokhoz jutunk, tehát olyanokhoz, melyek az élek kereszteződése nélkül lerajzolhatóak. (Ugyanakkor például nem síkbarajzolható az a gráf, melynek öt pontja van és bármelyik kettőt össze kell kötnünk.) A síkbarajzolás során a gráf élei a síkot tartományokra osztják, ezek felelnek meg az eredeti poliéderek lapjainak (ne feledkezzünk meg a poliéder „alsó” lapjából adódó „külső”, nem korlátos tartományról sem).

Most már az első szakasz végén mondottakat átfogalmazhatjuk: Legyen G 1 egy síkbarajzolható gráf valamely konkrét síkbarajzolása, melynek során a T 1 , T 2 , T t tartományok keletkeztek. Ezek után definiálhatunk egy G 2 gráfot, melynek P 1 , P 2 , P t pontjai megfelelnek G 1 tartományainak, és a G 2 gráfban akkor kötünk össze éllel két P i , P j pontot, ha G 1 vizsgált síkbarajzolásakor a T i és T j tartományoknak volt közös határoló éle. Az új gráfot a régi gráf duálisának nevezték – majd a 6. szakaszban fogjuk látni, hogy ezzel az elnevezéssel kapcsolatban fél évszázaddal később problémák vetődtek fel.

7. ábra.

Ez az új konstrukció még a jelen szakaszban fentebb tárgyaltnál is általánosabb, hisz egy síkbarajzolható gráf tartalmazhat hurokéleket, többszörös éleket, első- és másodfokú pontokat is, holott (amellett, hogy poliéderek „vetítésekor” ezek egyike sem keletkezhetne) a „politikai” térképeken sincsenek első vagy másodfokú pontok. A 7. ábra baloldali gráfja mindezeket a „patológikus” elemeket tartalmazza – a középső rajz mutatja az új gráf berajzolását szaggatott élekkel, míg a jobboldali rajz csak az új gráfot külön.