[2489] Csimby | 2007-12-07 02:21:30 |
A színezésből látszik, hogy két piros ill. két zöld csúcs között nem megy él, hanem él csak piros és zöld csúcsok között megy. Így bármely úton/körön felváltva kell hogy következzenek a piros ill. zöld csúcsok. De mivel piros csúcsból 8, zöld csúcsból pedig csak 6 van így váltakozó piros-zöld sorozatból legfeljebb csak 13 hosszút tudunk csinálni. Azt pedig, hogy a gráf kétszínnel színezhető - vagyis páros - lehetett megsejteni abból, hogy benne minden kör páros volt, ez a két állítás ekvivalens. Persze csak abból, hogy a gráf páros még nem következik hogy nincs benne Hamilton út, ehhez még kellett, hogy a két osztály (piros és zöld csúcsok) elemszámának a különbsége 2.
|
Előzmény: [2488] szbela, 2007-12-07 01:38:08 |
|
[2488] szbela | 2007-12-07 01:38:08 |
Sziasztok!
Ez egy olyan megoldás lenne, ahol arra a tételre hivatkozol, hogy ha van a gráfban Hamilton-kör, akkor k csúcs és az ezekből induló élek elhagyásával a gráf legfeljebb k komponensre esik szét? A zöld (6db) pontok elhagyásával a gráf 8 db komponensre esik szét, azaz nincs Hamilton-köre.
|
Előzmény: [2485] jonas, 2007-12-06 19:41:31 |
|
|
|
|
[2484] Csimby | 2007-12-06 19:30:59 |
Nem kell program. Van "szép" megoldás is, tehát nem ilyen esetszétválasztgatós. Mondjuk nekem hogy rájöjjek kellett valami amit véges matekon tanultunk az egyetemen.
|
|
[2483] jonas | 2007-12-06 19:22:38 |
Lefuttattam rá egy kimerítő keresést. Nem volt nehéz, mivel csak 14 csúcs van, és minden csúcsból csak legfeljebb három irányba lehet továbbmenni.
Ha helyes a programom, akkor nincs benne Hamilton-út.
Ha megengedjük, hogy egy csúcsot kihagyjunk, akkor pl. a következő útvonal jó: ACHMNLKIJFGBD.
|
Előzmény: [2467] Csimby, 2007-12-04 01:26:25 |
|
|
|
[2480] Enkidu | 2007-12-05 13:41:13 |
A bizonyítás:
Nyolc ember között van olyan, aki legalább négy másikat elvert. Ő lesz a győztesünk. Vizsgáljuk azt a négy embert, akiket megvert. Ezen négyesben van olyan ember, aki a másik három ember közül kettőt elvert, ő lesz a "második". Az a két ember, akiket ez az utóbbi elvert eldöntik egymás között, ki a harmadik és a negyedik. Ezzel kész.
Ha hét emberre vizsgálnánk, akkor már nem feltétlenül teljesül; ha pl (megszámozva a versenyzőket) mindenki elveri a nála 1,2 és 4-gyel nagyobb sorszámút (modulo 7 gondolkozva - ennyi pontatlanság talán belefér:)), akkor az egy ellenpélda.
|
Előzmény: [2466] Csimby, 2007-12-04 01:19:45 |
|