Gubancok Hajnal P´eter SZTE, Bolyai Int´ ezet
2010
Hajnal P´ eter
Hajnal Imre MT
Bevezet˝o feladat
H´arom h´az – h´arom k´ ut feladat Adott a s´ıkon h´arom h´ az ´es h´ arom k´ ut.
Hajnal P´ eter
Hajnal Imre MT
Bevezet˝o feladat
H´arom h´az – h´arom k´ ut feladat Adott a s´ıkon h´arom h´ az ´es h´ arom k´ ut. H1 , H2 , H3 , K1 , K2 , K3
Hajnal P´ eter
Hajnal Imre MT
Bevezet˝o feladat
H´arom h´az – h´arom k´ ut feladat Adott a s´ıkon h´arom h´ az ´es h´ arom k´ ut. H1 , H2 , H3 , K1 , K2 , K3 Tervezhet˝o-e kilenc u ´t a h´ azak ´es kutak k¨ozt,
Hajnal P´ eter
Hajnal Imre MT
Bevezet˝o feladat
H´arom h´az – h´arom k´ ut feladat Adott a s´ıkon h´arom h´ az ´es h´ arom k´ ut. H1 , H2 , H3 , K1 , K2 , K3 Tervezhet˝o-e kilenc u ´t a h´ azak ´es kutak k¨ozt, H1 K1 , H1 K2 , H1 K3 , H2 K1 , H2 K2 , H2 K3 , H3 K1 , H3 K2 , H3 K3
Hajnal P´ eter
Hajnal Imre MT
Bevezet˝o feladat
H´arom h´az – h´arom k´ ut feladat Adott a s´ıkon h´arom h´ az ´es h´ arom k´ ut. H1 , H2 , H3 , K1 , K2 , K3 Tervezhet˝o-e kilenc u ´t a h´ azak ´es kutak k¨ozt, H1 K1 , H1 K2 , H1 K3 , H2 K1 , H2 K2 , H2 K3 , H3 K1 , H3 K2 , H3 K3 hogy az utak csak k¨oz¨ os v´egpontjukban tal´ alkozzanak?
Hajnal P´ eter
Hajnal Imre MT
Kezdeti ´eszrev´etel
˝ AKKOR HA TERVEZHETO, a bizony´ıt´as egyszer˝ u: fel kell mutatni egy tervrajzot” ”
Hajnal P´ eter
Hajnal Imre MT
Kezdeti ´eszrev´etel
˝ AKKOR HA TERVEZHETO, a bizony´ıt´as egyszer˝ u: fel kell mutatni egy tervrajzot” ”
Csak r¨ ovid a bizony´ıt´as! Hogy hogyan tal´ aljuk meg a tervrajzot, arr´ ol nem sz´oltunk.
Hajnal P´ eter
Hajnal Imre MT
Kezdeti ´eszrev´etel
˝ AKKOR HA NEM TERVEZHETO, A bizony´ıt´ as: ???
Hajnal P´ eter
Hajnal Imre MT
R´eszfeladat Tervezz¨ uk meg a H1 K1 , K1 H2 , H2 K2 , K2 H3 , H3 K3 , K3 H1 utakat.
Hajnal P´ eter
Hajnal Imre MT
R´eszfeladat Tervezz¨ uk meg a H1 K1 , K1 H2 , H2 K2 , K2 H3 , H3 K3 , K3 H1 utakat. Vegy¨ unk fel h´azakat/kutakat. Tervezz¨ unk utakat.
Hajnal P´ eter
Hajnal Imre MT
R´eszfeladatmegold´asa (folytat´as) Tervezz¨ uk meg a H1 K1 , K1 H2 , H2 K2 , K2 H3 , H3 K3 , K3 H1 utakat. Vegy¨ unk fel h´azakat/kutakat. Tervezz¨ unk utakat.
Hajnal P´ eter
Hajnal Imre MT
´ R´eszfeladat MASIK megold´asa Egy m´asik j´o tervrajz:
Hajnal P´ eter
Hajnal Imre MT
L´enyeges (k¨onnyen elhihet˝o, nehezen bizony´ıthat´o) ´eszrev´etel L´enyeg´eben egyetlen megold´ as van.
Hajnal P´ eter
Hajnal Imre MT
L´enyeges (k¨onnyen elhihet˝o, nehezen bizony´ıthat´o) ´eszrev´etel L´enyeg´eben egyetlen megold´ as van. Minden megold´as egyen´ert´ek˝ u a k¨ovetkez˝ o STANDARD ´ megold´assal/LERAJZOLASsal:
Hajnal P´ eter
Hajnal Imre MT
L´enyeges (k¨onnyen elhihet˝o, nehezen bizony´ıthat´o) ´eszrev´etel L´enyeg´eben egyetlen megold´ as van. Minden megold´as egyen´ert´ek˝ u a k¨ovetkez˝ o STANDARD ´ megold´assal/LERAJZOLASsal:
Hajnal P´ eter
Hajnal Imre MT
A h´arom h´az- h´arom k´ut feladat megold´asa
V´alasz: NINCS megfelel˝o lerajzol´ as.
Hajnal P´ eter
Hajnal Imre MT
A h´arom h´az- h´arom k´ut feladat megold´asa
V´alasz: NINCS megfelel˝o lerajzol´ as. INDIREKT bizony´ıt´as.
Hajnal P´ eter
Hajnal Imre MT
A h´arom h´az- h´arom k´ut feladat megold´asa
V´alasz: NINCS megfelel˝o lerajzol´ as. INDIREKT bizony´ıt´as. ˝ hogy a r´esz standard lerajzol´ FELTEHETO, as´ aval kezd¨ unk ´es pr´ ob´aljuk a hi´anyz´o h´arom ´elt berajzolni.
Hajnal P´ eter
Hajnal Imre MT
A h´arom h´az- h´arom k´ut feladat megold´asa
V´alasz: NINCS megfelel˝o lerajzol´ as. INDIREKT bizony´ıt´as. ˝ hogy a r´esz standard lerajzol´ FELTEHETO, as´ aval kezd¨ unk ´es pr´ ob´aljuk a hi´anyz´o h´arom ´elt berajzolni. ¨ ¨ BELULre nem f´er el k´et hi´ anyz´o ´el. K´IVULre sem.
Hajnal P´ eter
Hajnal Imre MT
A h´arom h´az- h´arom k´ut feladat megold´asa
V´alasz: NINCS megfelel˝o lerajzol´ as. INDIREKT bizony´ıt´as. ˝ hogy a r´esz standard lerajzol´ FELTEHETO, as´ aval kezd¨ unk ´es pr´ ob´aljuk a hi´anyz´o h´arom ´elt berajzolni. ¨ ¨ BELULre nem f´er el k´et hi´ anyz´o ´el. K´IVULre sem. ´ ELLENTMONDAS.
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz ´ Elek (E ): Cs´ ucsp´arok halmaza (→ egyszer˝ u gr´ af)
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz ´ Elek (E ): Cs´ ucsp´arok halmaza (→ egyszer˝ u gr´ af) e = {u, v } olvasata: az u ´es v cs´ ucsok szomsz´edosak e ¨osszek¨oti u-t ´es v -t u-nak v szomsz´edja u ´es v az e ´el k´et v´egpontja
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz ´ Elek (E ): Cs´ ucsp´arok halmaza (→ egyszer˝ u gr´ af) e = {u, v } olvasata: az u ´es v cs´ ucsok szomsz´edosak e ¨osszek¨oti u-t ´es v -t u-nak v szomsz´edja u ´es v az e ´el k´et v´egpontja Lerajzol´as: cs´ ucsok helyett pontok, ´elek helyett ´elg¨ orb´ek
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz ´ Elek (E ): Cs´ ucsp´arok halmaza (→ egyszer˝ u gr´ af) e = {u, v } olvasata: az u ´es v cs´ ucsok szomsz´edosak e ¨osszek¨oti u-t ´es v -t u-nak v szomsz´edja u ´es v az e ´el k´et v´egpontja Lerajzol´as: cs´ ucsok helyett pontok, ´elek helyett ´elg¨ orb´ek Sz´ep lerajzol´as: ´elg¨ orb´ek nem metszik ´ at egym´ ast
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve Cs´ ucsok (V ): Egy v´eges halmaz ´ Elek (E ): Cs´ ucsp´arok halmaza (→ egyszer˝ u gr´ af) e = {u, v } olvasata: az u ´es v cs´ ucsok szomsz´edosak e ¨osszek¨oti u-t ´es v -t u-nak v szomsz´edja u ´es v az e ´el k´et v´egpontja Lerajzol´as: cs´ ucsok helyett pontok, ´elek helyett ´elg¨ orb´ek Sz´ep lerajzol´as: ´elg¨ orb´ek nem metszik ´ at egym´ ast S´ıkgr´af: gr´af, ami lerajzolhat´ o sz´epen
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve (folytat´as) K¨or egy gr´afban: olyan r´esze a gr´ afnak, ami lerajzolhat´ ou ´gy, hogy a megfelel˝o ´elg¨ orb´ek egy egyszer˝ u k¨orvonall´ a olvadnak ¨ossze.
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve (folytat´as) K¨or egy gr´afban: olyan r´esze a gr´ afnak, ami lerajzolhat´ ou ´gy, hogy a megfelel˝o ´elg¨ orb´ek egy egyszer˝ u k¨orvonall´ a olvadnak ¨ossze. K¨orgr´af: egy k¨or ´es m´ as semmi.
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve (folytat´as) K¨or egy gr´afban: olyan r´esze a gr´ afnak, ami lerajzolhat´ ou ´gy, hogy a megfelel˝o ´elg¨ orb´ek egy egyszer˝ u k¨orvonall´ a olvadnak ¨ossze. K¨orgr´af: egy k¨or ´es m´ as semmi. Jel¨ol´es: Cn (n pont´ u/´el˝ u gr´ af)
Hajnal P´ eter
Hajnal Imre MT
A gr´afelm´elet nyelve (folytat´as)
Jel¨ol´es: Cn (n pont´ u/´el˝ u gr´ af)
Hajnal P´ eter
Hajnal Imre MT
Egy gr´afelm´eleti t´etel
Euler t´etele G egyszer˝ u s´ıkgr´af. Ekkor |E | < 3|V |.
Hajnal P´ eter
Hajnal Imre MT
Egy m´asik gr´afelm´eleti t´etel
F´ary t´etele (F´ary t´etele) G egyszer˝ u s´ıkgr´af. Ekkor G lerajzolhat´ ou ´gy is, hogy minden ´elg¨ orb´eje EGYENES SZAKASZ.
Hajnal P´ eter
Hajnal Imre MT
Conway-lerajzol´as Defin´ıci´o G egy lerajzol´asa Conway-lerajzol´ as, ha
Hajnal P´ eter
Hajnal Imre MT
Conway-lerajzol´as Defin´ıci´o G egy lerajzol´asa Conway-lerajzol´ as, ha o¨sszefut´o ´elp´arok ´elg¨ orb´ei nem tal´ akoznak (csak a k¨oz¨os v´egpontjukban),
Hajnal P´ eter
Hajnal Imre MT
Conway-lerajzol´as Defin´ıci´o G egy lerajzol´asa Conway-lerajzol´ as, ha o¨sszefut´o ´elp´arok ´elg¨ orb´ei nem tal´ akoznak (csak a k¨oz¨os v´egpontjukban), nem ¨osszefut´o ´elp´ arok ´elg¨ orb´ei pontosan egyszer ´atmetszik egym´ast.
Hajnal P´ eter
Hajnal Imre MT
Conway-lerajzol´as Defin´ıci´o G egy lerajzol´asa Conway-lerajzol´ as, ha o¨sszefut´o ´elp´arok ´elg¨ orb´ei nem tal´ akoznak (csak a k¨oz¨os v´egpontjukban), nem ¨osszefut´o ´elp´ arok ´elg¨ orb´ei pontosan egyszer ´atmetszik egym´ast.
Hajnal P´ eter
Hajnal Imre MT
Gubancok
Defin´ıci´o G egyszer˝ u gr´af gubanc/thrackle, ha van Conway-lerajzol´asa.
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok?
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? C3 gubanc:
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? C3 gubanc:
C5 , C7 , C9 , C11 , . . . gubanc
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as) C4
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as) C4 NEM gubanc.
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as) C4 NEM gubanc.
C6 ?
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as) C4 NEM gubanc.
C6 ? IGEN.
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as)
T´etel Cℓ akkor ´es csak akkor gubanc, ha ℓ NEM 4.
Hajnal P´ eter
Hajnal Imre MT
Gubancok-e a k¨orgr´afok? (folyat´as)
T´etel Cℓ akkor ´es csak akkor gubanc, ha ℓ NEM 4.
´ BIZONY´ITAS:Ha Cℓ gubanc akkor Cℓ+2 is az:
Hajnal P´ eter
Hajnal Imre MT
Betold´as Egy G gr´af ´es gubanc lerajzol´ asa:
Hajnal P´ eter
Hajnal Imre MT
Betold´as (folyat´as) A G gr´af egy e ´el´enek (piros) kijel¨ ol´ese:
Hajnal P´ eter
Hajnal Imre MT
Betold´as (folyat´as) e feloszt´asa k´et u ´j ponttal.
Hajnal P´ eter
Hajnal Imre MT
Betold´as (folyat´as) A toldott gr´af gubanc lerajzol´ asa:
Hajnal P´ eter
Hajnal Imre MT
´ Aghajt´ as Egy G gr´af ´es gubanc lerajzol´ asa:
Hajnal P´ eter
Hajnal Imre MT
´ Aghajt´ as (folyat´as) A G gr´afb´ol egy ´ag (piros e ´el) kihajt´ asa:
Hajnal P´ eter
Hajnal Imre MT
´ Aghajt´ as (folytat´as) Az ´aghajtott gr´af gubanc lerajzol´ asa:
Hajnal P´ eter
Hajnal Imre MT
Lov´asz L´aszl´ o, Pach J´ anos, Szegedy M´ ari´o t´etele A k¨ovetkez˝o gr´af nem gubanc.
Hajnal P´ eter
Hajnal Imre MT
Lov´asz L´aszl´ o, Pach J´ anos, Szegedy M´ ari´o t´etele A k¨ovetkez˝o gr´af nem gubanc.
Meglep˝oen neh´ez.
Hajnal P´ eter
Hajnal Imre MT
Conway-sejt´es
Conway sejt´ese Legyen G egy gubanc. Ekkor |E | ≤ |V |.
Hajnal P´ eter
Hajnal Imre MT
Conway-sejt´es
Conway sejt´ese Legyen G egy gubanc. Ekkor |E | ≤ |V |.
Mi´ert gondolkozzak rajta?
Hajnal P´ eter
Hajnal Imre MT
Conway-sejt´es
Conway sejt´ese Legyen G egy gubanc. Ekkor |E | ≤ |V |.
Mi´ert gondolkozzak rajta?
Els˝ o korrekt megold´ o jutalma: 1000$ + vil´ agh´ır
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancok
Defin´ıci´o Egy gubanc egyenes-gubanc, ha van olyan gubanc lerajzol´asa, ahol minden ´elg¨ orbe egyenes.
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancok
Defin´ıci´o Egy gubanc egyenes-gubanc, ha van olyan gubanc lerajzol´asa, ahol minden ´elg¨ orbe egyenes.
C2ℓ+1 egyenes-gubanc.
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancok
Defin´ıci´o Egy gubanc egyenes-gubanc, ha van olyan gubanc lerajzol´asa, ahol minden ´elg¨ orbe egyenes.
C2ℓ+1 egyenes-gubanc.
C6 NEM egyenes-gubanc.
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancokra igaz a Conway-sejt´es
Lemma Egy egyenes-gubanc minden legal´ abb 3 fok´ u cs´ ucs´anak van 1 fok´ u szomsz´edja.
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancokra igaz a Conway-sejt´es
Lemma Egy egyenes-gubanc minden legal´ abb 3 fok´ u cs´ ucs´anak van 1 fok´ u szomsz´edja. Lemma ´atfogalmazva Egy egyenes-gubancban van 1 fok´ u cs´ ucs vagy minden foksz´am legfeljebb 2.
Hajnal P´ eter
Hajnal Imre MT
Egyenes-gubancokra igaz a Conway-sejt´es
Lemma Egy egyenes-gubanc minden legal´ abb 3 fok´ u cs´ ucs´anak van 1 fok´ u szomsz´edja. Lemma ´atfogalmazva Egy egyenes-gubancban van 1 fok´ u cs´ ucs vagy minden foksz´am legfeljebb 2. ´ BIZONY´ITASA ´ A SEJTES EGYENES GUBANCOKRA: Lemma alapj´an a pontsz´amra vonatkoz´ o teljes indukci´ o.
Hajnal P´ eter
Hajnal Imre MT
Legjobb fels˝o becsl´es gubancok ´elsz´am´ara
T´etel (Lov´asz L´aszl´ o—Pach J´ anos—Szegedy M´ ari´o, G. Cairns—Y. Nikolayevsky, R. Fulek—Pach J´ anos) Ha G egy gubanc, akkor |E | ≤ 1.428 . . . · |V |.
Hajnal P´ eter
Hajnal Imre MT
Hajr´a
Az 1000$-os d´ıj m´eg mindig ´erv´enyes.
Hajnal P´ eter
Hajnal Imre MT
K¨osz¨ on¨ om a figyelmet.
Hajnal P´ eter
Hajnal Imre MT
