A gráfelméletről III.
Tarcsay Tamás
2007/11/20 13:48
780 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Az előző írásunkban eljutottunk az egyszerű gráf fogalmáig, és egy problémát tűztünk ki. Most ennek megoldásával lépünk tovább.

Ha van ilyen társaság, akkor ez jellemezhető egy olyan egyszerű gráffal, amelynek fokszám sorozata: 4, 4, 6, 7, 8, 8, 8, 9, 9, 9. (Az, hogy ilyen fokszám sorozattal rendelkező gráf leétezik, az előző írás alapján már nyilvánvaló.) Kérdés, hogy létezik-e ilyen egyszerű gráf.

A három 9 fokszámú pont éllel van összekötve (szomszédok) az összes, tőlük különböző ponttal, így a két 4 fokszámúnak mondottal is. Így a két 4 fokszámúnak mondott pont már három – három pontnak szomszédja.

A három 8 fokszámú pontnak szomszédja egy kivételével az összes tőlük különböző pont, így az egyik 4 fokszámúnak mondott pont két 8 fokszámúnak szomszédja, azaz akkor a korábbi három mellé még két fokszámot kapna, ami ellentmondást jelent.

Kaptuk tehát, hogy ilyen társaság (egyszerű gráf) nem létezik.

Látható, hogy az „egyszerű” feltétel nem is olyan egyszerű, komoly korlátokat hordoz.

Az eddig vizsgált gráfjaink közül melyek voltak egyszerűek? A „Kovács uras” gráfok mindegyike ilyen volt, a „buszos gráf” és a Königsbergi hidakat szemléltető gráf nem egyszerű gráf.

Ha a „Kovács uras” gráfok pontjainak fokszámait vizsgáljuk, mindegyikben találhatunk egyenlő fokszámú pontokat. Természetes gondolat az, hogy keressünk olyan egyszerű gráfot, amelyben nincsenek egyenlő fokszámú pontok.

A próbálkozások nem vezetnek eredményre, így újabb sejtés fogalmazódhat meg:

Sejtés: Minden egyszerű gráfnak van legalább két egyenlő fokszámú pontja.

Egy n pontú egy szerű gráf pontjainak fokszámai a {0, 1, …. ,n – 1}, n elemű halmaznak lehetnek elemei. Egyszerre nem fordulhat elő egy 0 és egy n-1 fokszámú pont, mert az n-1 fokszámú pontnak minden tőle különböző pont szomszédja.

Ezek szerint az n pont fokszámait n-1 lehetőség közül kell választani, így kell, hogy legyen legalább két azonos fokszámú pont.

Irodalom:

  • Barabás Boglárka: Gráfelméleti feladatgyűjtemény (Szakdolgozat, készült a SZTE Bolyai Intézetében)

Tarcsay Tamás

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
All you need is code Minden a kódolás tanulásához
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek