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

6. Az 1930-as évek

6. Az 1930-as évek

Két gráfot izomorfnak nevezünk, ha pontjaik között létesíthető olyan kölcsönösen egyértelmű megfeleltetés, mely szomszédos pontokat szomszédosba, nem szomszédos pontokat nem szomszédosba visz. Például a 18. ábrán látható három hatpontú gráf közül az első kettő izomorf: feleltessük meg az A , B , C , D , E , F pontokat rendre az 1 , 3 , 5 , 2 , 4 , 6 pontoknak, és ellenőrizzük, hogy pl. A szomszédos D -vel, de nem szomszédos B -vel, és ennek megfelelően 1 szomszédos 2-vel, de nem szomszédos 3-mal. Ugyanakkor az ábra első és harmadik gráfja nem izomorf: utóbbiban van három olyan pont, melyek közül bármely kettő szomszédos, az elsőben nincs. Kevésbé pontosan fogalmazva az izomorfia azt jelenti, hogy „tulajdonképpen ugyanarról a gráfról van szó, csak esetleg másképp adtuk meg”.

18. ábra.

Az előző szakaszban írottak – kellő pontosítás után – a Boole-algebrák elméletében vezetnének el egy dualitáselvhez. A matematika egyéb, itt nem tárgyalt területein is számos dualitás jellegű fogalmat vezettek be, és hallgatólagosan elvárták, hogy a dualitást kétszer alkalmazva visszajussunk az eredetihez (pontosabban, ha bizonyos matematikai objektumok között definiálunk egy „dualitást”, akkor a duális duálisa legyen izomorf az eredetivel), valamint, hogy ha két objektum duálisa izomorf, akkor az eredeti két objektum is legyen izomorf.

19. ábra.

Whitney vette észre 1930 körül, hogy a síkbarajzolható gráfok dualitására ez egyáltalán nincs így! Tekintsük például a 19. ábra alsó sorában látható gráfokat. Nyilván nem izomorfak, hisz a baloldaliban van másodfokú pont, a jobboldaliban nincs. Ha azonban a második szakaszban leírt módon megszerkesztjük a duálisaikat (felső sor), akkor izomorf gráfokhoz jutunk. Az „ellentmondásnak” nyilván az a magyarázata, hogy a duális gráf megszerkesztésére adott eljárásunk igazából nem a gráfra, hanem a gráf konkrét síkbarajzolására vonatkozott: ha másképp rajzoljuk le ugyanazt a gráfot, akkor másféleképp keletkeznek tartományok, így egész más „duálist” kaphatunk.

Ezen a problémán elvileg kétféleképp segíthetnénk. Vagy „erősíthetnénk” az izomorfia definícióját, tehát nem tekintenénk „lényegileg azonosnak” két gráfot, ha másképp van lerajzolva (mint a 19. ábra felső két gráfja), vagy „gyengíthetnénk”, vagyis még a 19. ábra alsó két gráfját is valamilyen értelemben egyformán kezelnénk. Az előbbi megoldás elfogadhatatlan, hisz az egész gráfelméletnek az a lényege, hogy a rajzok csak szemléltetésül szolgálnak, maga a gráf csak a logikai kapcsolatok rendszere (az lényeges, hogy mi mivel van összekötve, de az nem, hogy hogyan). Mi lehetne akkor az utóbbi megoldás kiindulópontja?

Feltehetőleg Whitney a gráfokat, mint villamos hálózatok összekapcsolásának modelljeit tekintette (ahol tehát a Kirchhoff-féle törvények uralkodnak, vagyis csak az számít, hogy bizonyos élek kört alkotnak-e, az nem, hogy milyen sorrendben), mert erre a kérdésre az alábbi választ adta.

Nevezzünk két gráfot gyengén izomorfnak, ha éleik között létesíthető olyan, kölcsönösen egyértelmű megfeleltetés, mely köröket körökbe, vágásokat vágásokba visz. A 19. ábra alsó két gráfja ilyen és az éleiket úgy számoztuk, hogy rögtön a kívánt megfeleltetést adja: például az { 1 , 3 , 4 , 5 } halmaz mindkét gráfban kör, az { 1 , 2 , 4 } halmaz mindkét gráfban vágás. Tehát például ez a két gráf gyengén izomorf, de nem izomorf, másrészt nyilvánvaló, hogy ha két gráf izomorf, akkor gyengén izomorf is.

Ez a fajta izomorfia már teljesíti a szakasz elején megfogalmazott követelményeket. Belátható, hogy egy síkbarajzolható gráf különböző síkbarajzolásaiból képzett duálisok gyengén izomorfak és ennek segítségével az is, hogy egy síkbarajzolható gráf duálisának a duálisa gyengén izomorf az eredetivel, valamint az, hogy ha két síkbarajzolható gráf duálisa izomorf (vagy akárcsak gyengén izomorf), akkor már az eredetiek is legalább gyengén izomorfak voltak.

Ebből a gondolatból kiindulva Whitney egy sokkal fontosabb fogalom felismeréséhez is eljutott, ehhez azonban előzetesen egy kis kitérőt kell tennünk.