Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Hamilton-kör

Szeretnél hozzászólni? Jelentkezz be.
[20] bily712012-04-20 20:14:23

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.

Előzmény: [19] SmallPotato, 2012-04-20 08:37:57
[19] SmallPotato2012-04-20 08:37:57

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

Előzmény: [18] bily71, 2012-04-20 08:13:33
[18] bily712012-04-20 08:13:33

"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.

Előzmény: [17] Tóbi, 2012-04-20 00:30:36
[17] Tóbi2012-04-20 00:30:36

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?

Előzmény: [16] bily71, 2012-04-19 23:25:05
[16] bily712012-04-19 23:25:05

"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, F2-nek nincs éle, azaz izolált pontokból áll, akkor G három színnel jól színezhető.

Előzmény: [15] Tóbi, 2012-04-19 20:36:31
[15] Tóbi2012-04-19 20:36:31

"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.)

Előzmény: [14] bily71, 2012-04-19 19:06:45
[14] bily712012-04-19 19:06:45

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 F1-et és F2-t, melyek kifeszítik G-t!

Megoldás. (i) F1 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, F1-et F-ből csúcs(ok) törlésével kaptuk, tehát erdő.

(ii) F2 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 F2 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 F1 minden második csúcsát "3"-mal, F2 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.

[13] bily712012-04-14 16:55:23

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ó.

Előzmény: [12] Tóbi, 2012-04-14 14:24:24
[12] Tóbi2012-04-14 14:24:24

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.

Előzmény: [11] bily71, 2012-04-14 12:10:38
[11] bily712012-04-14 12:10:38

Állítás. Bármely gömbre rajzolható n\ge4 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ó n\ge4 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ó n\ge4csú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ó n\ge4csúcsú poliéderre (síkba rajzolható gráfra).

[10] Kati2007-08-15 19:27:20

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

Előzmény: [9] HoA, 2007-08-06 11:51:13
[9] HoA2007-08-06 11:51:13

A 34. és 35. feladat.

Előzmény: [8] HoA, 2007-08-06 11:40:13
[8] HoA2007-08-06 11:40:13

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.

Előzmény: [7] Kati, 2007-07-24 22:50:53
[7] Kati2007-07-24 22:50:53

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

Előzmény: [6] HoA, 2007-07-02 08:33:43
[6] HoA2007-07-02 08:33:43

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.

Előzmény: [3] Kati, 2007-04-21 16:36:50
[5] mrmorotz2007-06-13 00:53:10

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.

Előzmény: [1] Kati, 2007-04-21 13:47:33
[4] HoA2007-04-24 12:30:48

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 P1,P2,...,Pkcsúcsok alkotnak ebben a sorrendben. A többi csúcs legyen Q1,Q2,...,Qn-k. A kört úgy bővítjük, hogy az egyik Pi-Pi+1(Pk+1=P1) él helyére beillesztjük a Pi-QjésQj-Pi+1éleket. Ez csak akkor nem lenne megvalósítható, ha nem lehetne olyan Qj -t találni, amelyik valamelyik Pi-Pi+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.

Előzmény: [3] Kati, 2007-04-21 16:36:50
[3] Kati2007-04-21 16:36:50

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?

Előzmény: [2] HoA, 2007-04-21 14:44:04
[2] HoA2007-04-21 14:44:04

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.

Előzmény: [1] Kati, 2007-04-21 13:47:33
[1] Kati2007-04-21 13:47:33

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?