Fórum: Hamilton-kör

reguláris

Párszor olvastam, hallottam és mondtam már, mégsem tudom helyesen leírni, vannak olyan szavak, ahol összeszoktam keverni a betűket.

reguláris. Legalább egyszer, plíííz!

"Azt hiszem, én itt elvesztettem a fonalat."

Nyugi, tökéletesen értem, hogy hibás a [14]-ben leírt bizonyítás, és miután megmutattad, látom azt is hol.

Amit a [16]-ban írok, az már csak megjegyzés és feltevések, nem bizonyítás.

Leírom a feltevéseimet érthetőbben. A négyszín-tétel kimondja, hogy bármely G síkbarajzolható gráf jól színezhető legfeljebb 4 színnel, ezt bizonyították számítógéppel.

Színezzük G-t 4 színnel, legyenek ezek fehér, fekete, kék, piros, ekkor, feltevésem szerint, létezik olyan színezés, hogy ha 4 színből kiválasztunk 2 párt, mondjuk a=(fehér, fekete) és b=(kék, piros), és töröljük azokat az éleket, melyek egyik vége a-hoz, másik vége b-hez tartozik, akkor két darab erdőt kapunk.

Ha van olyan eljárás a kezemben, amivel biztosan megtalálom ezt a két erdőt, (anélkül, hogy használnám a tételt, hiszen pont azt akarom bizonyítani), akkor ha az előbbit leírjuk logikailag visszafelé haladva, kapunk egy bizonyítást a négyszín-tételre. A feladat tehát megmutatni, hogy a [14]-ben leírt eljárás működik nem 3-regurális gráfokra is. Az is lehet, hogy nem működik, vagy csak akkor, ha új lépésekkel finomítjuk.

"Már csak az érdekelne, mit keres ez az egész a Hamilton-kör témában?"

Ez a téma a gráfokról szól.

Azt hiszem, én itt elvesztettem a fonalat. Már csak az érdekelne, mit keres ez az egész a Hamilton-kör témában?

"Tehát ezek az erdők nem kellenek." Akkor nem kellenek, ha van olyan síkbarajzolható gráf, melynek minden csúcsa legalább 3 fokú, hogy bármely feszitő fájára alkalmazva az eljárást, nem találunk két feszítő erdőt. Ha létezik bármely síkbarajzolható gráfnak ilyen kifeszítése, akkor kellenek.

A négyszín-tétel miatt bármely G síkbarajzolható gráfnak, melynek minden csúcsa legalább 3 fokú, létezik ilyen kifeszítése. Ez megfordítva is igaz, tehát a feladat belátni, hogy létezik ilyen kifeszítés

Ha G-nek van olyan feszítő fája, hogy alkalmazva az eljárást, F₂-nek nincs éle, azaz izolált pontokból áll, akkor G három színnel jól színezhető.

"Ha a régi poliéder jól színezhető, akkor az új is, tehát elég csak a 3-regurális gráfokat vizsgálni." Itt logikailag az kellene, hogy ha az új jól színezhető, akkor a régi is. Ez meg nem igaz. (Egyébként az, hogy egy 3-reguláris gráf 4 színnel színezhető, triviális, mivel egyesével színezhetjük a csúcsokat, és minden lépésnél legfeljebb 3 kizárt szín van. Tehát ezek az erdők nem kellenek.)

Feladat. Adott G egyszerű, összefüggő, 3-regurális gráf és egyik feszítő fája F. Színezzük G minden csúcsát és F minden élét "1" színűre, majd színezzük az "2" színnel G azon éleinek egyik végét, melyeket F nem tartalmaz, azután töröljük G minden olyan élét, mely különböző színű csúcsok között fut és végül színezzük "2"-vel azokat az éleket, melyek mindkét vége "2" színű .

Igazoljuk, hogy a fenti eljárással két különböző színű erdőt kapunk F₁-et és F₂-t, melyek kifeszítik G-t!

Megoldás. (i) F₁ erdő. Valóban, F fa, és ha töröljük a fa egy csúcsát a rá illeszkedő éllel/élekkel együtt, akkor fát kapunk, ami egy fából álló erdő, ha a törölt csúcs levél, és erdőt, két fát kapunk, ha a törölt csúcs nem levél, F₁-et F-ből csúcs(ok) törlésével kaptuk, tehát erdő.

(ii) F₂ azért erdő, mert körmentes. Valóban, tegyük fel, hogy F-nek léteznek csúcsai, melyek F-ben nem lévő élek végpontjai és az F-ben nem lévő élekkel kört alkotnak.

Ekkor sem kapunk "2" színű kört, hiszen az F-ben nem lévő élek végpontjai közül csak az egyiket színeztük "2"-vel, így a körnek csak minden második csúcsa "2" színű, ebből következik, hogy ha a kör páros sok csúcsból áll, akkor izolált "2" színű pontokat kapunk, ha páratlan sok csúcsból, akkor két "2" színű csúcs egymás mellé kerül, ekkor egy élt kell "2"-vel színezni.

Ha több ilyen kör kerül egymás mellé, akkor az "2" színű élek fát alkothatnak. Arra jutottunk, hogy F₂ izolált pontokból és fákból álló erdő.

Hogy miért fontos ez?

Következmény. (Négyszín-tétel) Bármely gömbre rajzolható poliéder (síkbarajzolható gráf) csúcsai színezhetők négy színel úgy, hogy bármely él végpontjai különböző színűek.

Bizonyítás. Ha egy gömbre rajzolható poliéder (síkbarajzolható gráf) tartalmaz 4, vagy annál nagyobb fokszámú csúcsot, akkor levágva azokat, a csúcsok helyén köröket kapunk, az így kapott új poliéder minden csúcsa 3 fokú, az eljárás a megmaradt régi csúcsok színét nem befolyásolja, ha a régi poléder jól színezhető, akkor az új is, tehát elég csak a 3-regurális gráfokat vizsgálni.

A feladat megoldása során beláttuk, hogy bármely 3-regurális G gráf kifeszíthető két erdő segítségével. Színezzük F₁ minden második csúcsát "3"-mal, F₂ minden második csúcsát "4"-gyel, ezt megtehetjük, hiszen minden fa, így minden erdő jól színezhető két színnel.

A két erdő kifeszíti G-t, így az jól színezhető négy színnel. Ezzel beláttuk állításunkat.

Igen, feltételeztem, hogy minden csupa háromszög lapú poliéder felépíthető úgy, hogy minden lépésben az újabb csúcs egy háromszög belsejébe kerül.

Ami az egészből igaz:

Adott kiindulásképp egy gömbre rajzolt tetraéder, minden lépésben valamelyik háromszögbe kerül az új csúcs, az így felépített poliéderek 4 színnel színezhetők, úgy, hogy bármely él végpontjai különböző színűek.

Az így kapott poliéderek visszabonthatók úgy, hogy a színezés ne változzon a következőképp:

(i) bármely él elhagyható,

(ii) bármely csúcs az összes rá illeszkedő él elhagyható.

Kérdés: Előállítható-e bármely poliéder ilyen visszabontással? Elég azt megmutatni, hogy bármely csupa háromszög lapú poliéder előállítható.

Kedves Bily! Sajnos most sem jártál sikerrel. "A törölt csúcs a gömb felszínén egy olyan háromszög belső pontja volt, melynek csúcsai páronként különböző színűek." Ez nem igaz. Legyen például a poliéder egy ikozaéder. Ennek egyik csúcsa sem egy háromszögbe írt pont, hiszen minden pontba 5 él fut be. Így nem tudod alkalmazni az indukciós lépést.

Állítás. Bármely gömbre rajzolható n4 csúcsú poliéder (síkba rajzolható gráf) csúcsai, melynek minden lapja háromszög, színezhetők úgy, hogy bármely él végei különböző színűek.

Bizonyítás. (Teljes indukcióval)

n=4 csúcs esetén az állítás igaz, hiszen a tetraéder csúcsai színezhetők a kívánt módon.

Tegyük fel, hogy n=k-ra igaz az állítás.

n=k+1 csúcs esetén töröljünk egy csúcsot, ekkor egy k csúcsú poliédert kapunk, mely az indukciós feltétel miatt jól színezhető. A törölt csúcs a gömb felszínén egy olyan háromszög belső pontja volt, melynek csúcsai páronként különböző színűek. Helyezzük vissza a k+1-edik csúcsot, és színezzük a negyedik színnel. A k+1-edik csúcsba futó élek végpontjai különböző színűek, így a poliéder minden éle rendelkezik az állításban megfogalmazott tulajdonsággal. k tetszőleges 4-nél nem kisebb természetes szám, ezért az állítás igaz bármely gömbre rajzolható n4 csúcsú poliéderre (síkba rajzolható gráfra), melynek minden lapja háromszög

Következmény.(Négyszín-tétel) Bármely gömbre rajzolható n4csúcsú poliéder (síkba rajzolható gráf) csúcsai színezhetők úgy, hogy bármely él végei különböző színűek.

Bizonyítás. 1. eset: A poliéder minden lapja háromszög, ekkor kész vagyunk, lásd az előbbi bizonyítást.

2. eset: A poliédernek van m>3 m-szög lapja, ekkor illesszünk a gömb felszínén minden ilyen lapba egy új csúcsot. Kössük össze az új csúcsot az m-szög csúcsaival, ekkor olyan poliédert kapunk, melynek minden oldala háromszög. Az új poliéder színezhető a kívánt módon, lásd az előbbi bizonyítást. Szinezzük ki, ezután töröljük az új csúcsokat a beléjük futó élekkel együtt, a megmaradt eredeti poliéder színezhető a kívánt módon, hiszen a csúcsok törlése a megmaradó csúcsok színét nem befolyásolja. Az eredeti poliéder tetszőleges volt, ezért az állítás igaz bármely gömbre rajzolható n4csúcsú poliéderre (síkba rajzolható gráfra).

Kösz szépen,kedves tőled hogy még be is másoltad,így már világos.

A 34. és 35. feladat.

Mivel a megoldás a korábbi feladatokra hivatkozik, képméret korlátok miatt több darabban idemásolom a 11.,12.,34. és 35. feladat szövegét és megoldását.

Azt a könyvet nem tudom elérni és mostmár igazán érdekelne a megoldása.Légy szives ird le nekem.

A feladatot - és megoldását - megtaláltam Andrásfai Béla "Ismerkedés a Gráfelmélettel" c. könyvében: 4. fejezet 35. feladat. Ha nem tudod elérni a könyvet és még érdekel a feladat, leírom a megoldás vázlatát.

Legalább n-élt szerintem lehet úgy rendezni n csúcs között, hogy legyen Hamilton-kör! MIvel élek száma>n-1.

Azt hiszem az állítás igaz, nem sikerült ellenpéldát találnom. Itt egy befejezendő megoldás vázlata. Ha valamelyik nem világos, részletezem:

1)Belátjuk, hogy n=3-ra és 4-re az állítás igaz.

2)n > 4 -re belátjuk, hogy mindig van háromszög - 3 hosszúságú kör

3)Megadunk egy konstruktív bizonyítást: n> 4-re és k< n-1 -re: Ha van k hosszúságú kör, akkor van k+1 hosszúságú is.

Látható, hogy a vége hiányzik, az n-1 hosszúságú kör létezése bizonyítható, de az n hosszúságúé nem.

3) -at egy kicsit részletesen: Legyen egy k hosszúságú körünk, melyet a P₁,P₂,...,P_kcsúcsok alkotnak ebben a sorrendben. A többi csúcs legyen Q₁,Q₂,...,Q_n-k. A kört úgy bővítjük, hogy az egyik P_i-P_i+1(P_k+1=P₁) él helyére beillesztjük a P_i-Q_jésQ_j-P_i+1éleket. Ez csak akkor nem lenne megvalósítható, ha nem lehetne olyan Qj -t találni, amelyik valamelyik P_i-P_i+1 él mindkét végpontjával össze van kötve. Belátható, hogy ehhez minden Q-ból legalább k/2 hiányzó él kell, az (n-k) darab Q csúcsból tehát legalább (n-k) * k/2. Belátható, hogy n-k> 1-re ez több, mint n-3. Vagyis a bővítés mindig végrehajtható, ha k < n-1.

Köszi,majd még próbálkozom a bizonyítással.Ha neked sikülne hamarabb légyszi írj!Szerinted érvényes az állítás?

Egyelőre tényleg csak ötlet.

1.) A kifejezést a teljes gráf éleinek n.(n-1)/2 számából levonva azt kapjuk, hogy legfeljebb n-3 él hiányzik.

2.) Ha a hiányzó élek ugyanahhoz a csúcshoz illeszkednek, akkor sem marad elsőfokú cúcs.

Valaki kérem segítsen bebizonyítani:ha egy n csúcsú egyszerü gráfnak legalább (n-1).(n-2)/2+2 éle van,akkor van Hamilton-köre.Valami ötlet?