Feladat: F.2697 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1988/szeptember, 257 - 259. oldal  PDF file
Témakör(ök): Gráfelmélet, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):Feladatok: 1988/május: F.2697

Hányféleképpen lehet az ábrán látható gráfot önmagába úgy leképezni, hogy csúcs csúcsba, él pedig élbe menjen át?
 
 

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 P, ..., Q, ..., R, ..., P kört. Ha a homomorfizmus P-t az U-ba, Q-t és R-t V-be viszi, akkor a fenti kör képe U, ..., V, ..., V, ..., U lesz, ami nem minimális. Világos, hogy ez tartalmaz egy V, ..., V alakú kört; amelyet elhagyva egy U, ..., V, ..., U 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 A, B, C, D-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: ABCA, ABDA, ACDA és BCDB. (Páros minimális körök vannak: pl. ilyen az ABA vagy az ACBDA 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 ABCA, ABDA, ACDA 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 A 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 A képe is harmadfokú csúcs. Megmutatjuk, hogy A képe csak önmaga lehet. Tegyük fel, hogy A képe például B volna. Ekkor A valamelyik két szomszédjának a képe B-nek az a két szomszédja volna, amelyek B és C, illetve B és D közé esnek. A figyelembe vett hét-hosszúságú kör három csúcsának a képe tehát a BCDB 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 A képe sem C, sem D nem lehet; s mivel e kép harmadfokú, ezért valóban csak A lehet.
Mivel A 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 B, C és D képe B, C és D lesz ‐ valamilyen sorrendben. Mivel A és B össze vannak kötve, ezért képeik is összekötöttek; így B képe is csak önmaga lehet. Mivel A-hoz és C-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 C-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ő:
a) Ha egy csúcs, és egy kivételével minden szomszédja fixen marad, akkor az az egy szomszéd is fixen marad.
b) 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.
c) Ha egy másodfokú csúcs és annak egyik szomszédja fixen marad, akkor fixen marad a másik szomszédja is.
A b) eset alapján fixen marad az A és C, valamint a C és D közötti csúcs. Az a) eset alapján fixen marad az A és D közötti, A-hoz és a C és B közötti, C-hez közelebbi csúcs. Most a c) esetet használjuk. Ebből először azt kapjuk, hogy az A és D közötti, D-hez közelebbi, illetve a C és B közötti, középen levő csúcs; és újbóli alkalmazással, hogy a B-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 a) 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.