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. Egy csúcs fokán értjük a csúcsból kiinduló élek számát. A gráf egy körén értjük a gráf csúcsainak egy olyan sorozatát, amelyben az utolsó csúcs megegyezik az elsővel, és mindegyik csúcsot él köt össze a rákövetkezővel. Egy kör hosszán a benne felsorolt csúcsok számát értjük (tehát az első csúcsot vagy csak az "elején'', vagy csak a "végén'' számítjuk). Egy kör minimális, ha az első és utolsó csúcson kívül egyik csúcs sem szerepel kétszer.
A feladatban szereplő leképezés (úgynevezett gráfhomomorfizmus) nyilván kört körbe visz. Az viszont nem feltétlenül igaz, hogy minimális kört minimális körbe visz. Nézzünk egy , , , , , , kört. Ha a homomorfizmus -t az -ba, -t és -t -be viszi, akkor a fenti kör képe , , , , , , lesz, ami nem minimális. Világos, hogy ez tartalmaz egy , , alakú kört; amelyet elhagyva egy , , , , alakú kör marad. A fenti módon minden kör képe minimális körök egyesítése lesz. Természetesen e kör hossza megegyezik a fellépő minimális körök hosszának az összegével. Mivel homomorfizmusnál a kör hossza nem változik, ezért igaz a következő: Páratlan hosszúságú kör képe tartalmaz minimális páratlan hosszúságú kört. Az ábrán a harmadfokú csúcsokat , , , -vel jelöltük. Ha egy körre hivatkozunk, akkor a benne szereplő betűk közé mindig azt az utat kell (gondolatban) tenni, amelyikben több harmadfokú csúcs nem szerepel (és a többi csúcs is csak egyszer lép fel). Az adott gráfban a következő páratlan minimális körök vannak: , , és . (Páros minimális körök vannak: pl. ilyen az vagy az kör.) Egyszerűen megszámolható, hogy az első három kör hossza hét, a negyediké pedig kilenc. Eleve nincs kikötve, hogy különböző csúcsok képe is különböző, vagy, hogy minden csúcs fellép képként; ezért nem biztos, hogy harmadfokú csúcs képe is harmadfokú. Ezt csak közvetve tudjuk bizonyítani. A hét hosszúságú (minimális) körök képe felbomlik minimális körökre, amelyek között van páratlan hosszúságú (hiszen páros számok összege nem lehet páratlan). Mivel , , az összes hét-hosszúságú minimális páratlan kör, ezért a leképezésnél ezek mindegyike valamelyikükbe megy át. (Eleve nem is biztos, hogy különböző körök képe különböző.) Tekintsük a fenti három kör bármelyikét. Mivel ennek a képe is egy hét-hosszúságú kör, ezért e kör két különböző csúcsának a képe is különböző. Tekintsük bármely két szomszédját. Ezek egy hét-hosszúságú kör különböző csúcsai, ezért képeik is különbözőek. Így képe is harmadfokú csúcs. Megmutatjuk, hogy képe csak önmaga lehet. Tegyük fel, hogy képe például volna. Ekkor valamelyik két szomszédjának a képe -nek az a két szomszédja volna, amelyek és , illetve és közé esnek. A figyelembe vett hét-hosszúságú kör három csúcsának a képe tehát a körre esik, ami lehetetlen, mert nincs olyan hét-hosszúságú kör, amelyhez e csúcsok mindegyike hozzátartozik. Ugyanilyen meggondolással látható be, hogy képe sem , sem nem lehet; s mivel e kép harmadfokú, ezért valóban csak lehet. Mivel három szomszédjának a képe három különböző csúcs, a három hét-hosszúságú kör képe is három különböző hét-hosszúságú kör. Így a gráf minden csúcsa előáll képként (hiszen minden csúcs hozzátartozik valamelyik hét-hosszúságú körhöz), aminek következtében különböző csúcsok képe biztosan különböző. Ebből viszont azonnal adódik, hogy a leképezésnél a csúcsok fokszáma nem változik meg. Más szóval , és képe , és lesz ‐ valamilyen sorrendben. Mivel és össze vannak kötve, ezért képeik is összekötöttek; így képe is csak önmaga lehet. Mivel -hoz és -hez található olyan csúcs, amelyik mindkettőjükkel összekötött (és más harmadfokú csúcsokból képezett pár nem rendelkezik ezzel a tulajdonsággal!), ezért -nek is csak önmaga lehet a képe. Ekkor viszont a negyedik harmadfokú csúcs is csak önmagára képződhet. Most megmutatjuk, hogy a többi csúcsnak is fixen kell maradnia. Ehhez az alábbi könnyen belátható egyszerű állításokat használjuk fel, amelyek minden olyan (véges) gráfhomomorfizmusra igazak, amelynél különböző elemek képe különböző: Ha egy csúcs, és egy kivételével minden szomszédja fixen marad, akkor az az egy szomszéd is fixen marad. Ha egy másodfokú csúcs két szomszédja fixen marad, és nincs több olyan másodfokú csúcs, amely ugyanezekkel a szomszédokkal van összekötve, akkor fixen marad ez a csúcs is. Ha egy másodfokú csúcs és annak egyik szomszédja fixen marad, akkor fixen marad a másik szomszédja is. A eset alapján fixen marad az és , valamint a és közötti csúcs. Az eset alapján fixen marad az és közötti, -hoz és a és közötti, -hez közelebbi csúcs. Most a esetet használjuk. Ebből először azt kapjuk, hogy az és közötti, -hez közelebbi, illetve a és közötti, középen levő csúcs; és újbóli alkalmazással, hogy a -hez közelebbi csúcs is fixen marad. A hiányzó két csúcs fixen maradása következik most már például az eset alapján. Így a kívánt leképezés csak az identitás lehet. Megjegyzés. A beküldött dolgozatokkal ellentétben a megoldás során nem használhattuk, hogy a szóban forgó leképezés a gráfot önmagára, hanem csak annyit, hogy önmagába képezi. Ezért ‐ ellentétben a 2632. feladattal ‐ azt sem tehettük fel, hogy egy csúcs képének a foka megegyezik az eredeti fokával. Ha a gráf egyik csúcsába egy "hurkot'' tettünk volna (azaz e csúcsot összekötöttük volna önmagával), akkor már nem csupán egyetlen gráfhomomorfizmusa lenne, mert minden csúcsot e kiválasztottra képezve egy gráfhomomorfizmust kapnánk. Az viszont igaz maradna, hogy az új gráfot sem lehetne a kívánt módon önmagára leképezni az identitástól eltérő módon. A feladat megoldásának éppen az az értékelhető része, amely azt bizonyítja, hogy a szereplő gráf minden gráfhomomorfizmusa egy-egyértelmű (és így "foktartó''). Ilyen dolgozat azonban nem volt. Az olyan gráfokat, amelyeket csak az identikus gráfhomomorfizmus vihet önmagába, merev gráfoknak nevezik. Az itt bemutatott merev gráf nem a legkisebb; de a legkisebb olyan, amelyik bizonyos speciális tulajdonságai miatt igen fontos. |