|
Feladat: |
N.119 |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Bérczi Gergely , Braun Gábor , Frenkel Péter , Gyenes Zoltán , Hesz Zoltán , Juhász András , Kun Gábor , Lippner Gábor , Mátrai Tamás , Pap Gyula , Szabó Jácint , Vizer Máté |
Füzet: |
1997/április,
230 - 231. oldal |
PDF | MathML |
Témakör(ök): |
Gráfelmélet, Indirekt bizonyítási mód, Nehéz feladat |
Hivatkozás(ok): | Feladatok: 1996/november: N.119 |
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. I. megoldás. Minden pozitív egészre konstruálunk olyan háromszögmentes gráfot, amely nem színezhető ki színnel. Ha , akkor a két pontú, egy élű gráf megfelelő. Tegyük fel, hogy már megkonstruáltuk -et; most megkonstruáljuk -t. Legyen pontjainak száma , és legyen pozitív egész ( pontos értékét később határozzuk meg), vegyünk fel egy -elemű ponthalmazt, valamint darab, -gyel izomorf gráfot, legyenek ezek , , . Mindegyik -nek feleltessük meg egy -elemű részhalmazát, és kössük össze minden pontját a megfelelő részhalmaz egy-egy pontjával. Azt állítjuk, hogy az így kapott gráf háromszögmentes, és megfelelő esetén nem színezhető ki színnel. Ha lenne háromszög, akkor annak legfeljebb egy csúcsa lehet -ban, mert -beli pontok között nincs él. Nem lehetnek csúcsai különböző -kben sem, mert az ilyenek között sincs él. Nem lehet mindhárom pont ugyanabban a -ben sem, mert háromszögmentes. Már csak az az eset maradt, hogy egy csúcsa -ban van, a másik kettő pedig ugyanabban a -ben. Viszont -beli pontból legfeljebb egy -beli pontba megy él. Tegyük fel, hogy a gráfot kiszíneztük színnel. Ha elég nagy, például , akkor -ban van darab egyszínű pont, legyen ezek színe piros. Az ezeknek megfelelő -ben nem szerepelhet a piros szín, ez viszont ellentmond annak, hogy legalább szín szükséges a színezéséhez.
II. megoldás. Egy másik konstrukciót mutatunk. Tegyük ismét fel, hogy már létezik, pontjai legyenek , , . Vegyük még fel a , , és pontokat. Kössük össze -t -vel, ha és össze van kötve, továbbá kössük össze -et mindegyik -vel. Ha az így kapott gráfban lenne háromszög, annak legfeljebb egy csúcsa lehet a -k között, mert a -k között nem fut él; ebből kifolyólag sem szerepel háromszögben. Ha pedig , és háromszöget alkot, akkor , és is, ami ellentmond annak, hogy háromszögmentes. Tegyük fel, hogy a gráf kiszínezhető színnel. Legyen színe piros. Megadjuk a , , pontok egy jó színezését színnel. Ez ellent fog mondani annak, hogy színezéséhez legalább szín kell. Minden egyes piros -t változtassuk színére. A pontok között nem szerepel a piros szín, mert közös szomszédjuk, piros. A -ket tehát csak legfeljebb színnel színeztük. Ha és között fut él, akkor vagy mindkettő színét változatlanul hagytuk, és emiatt különbözőek maradtak, vagy az egyikük piros volt (mondjuk ), és annak színét színére változtattuk. Viszont és között van él, és színe különböző volt, tehát a módosított színezésben is és különböző színű.
|
|