Vegyünk egy tetszőleges embert, legyen ő A1. Legyen egy ismerőse A2, legyen továbbá A2-nek egy A1-tol különböző ismerőse A3, és általában legyen Ak+1-nek egy Ak-tól különböző ismerőse Ak+2. Ilyen van, hiszen mindenkinek van legalább két ismerőse. Így kapjuk az embereknek egy A1A2…Am… végtelen sorozatát, ahol mindenki ismeri az elotte és utána következőt. Ez a sorozat azonban egy idő után biztosan tartalmaz ismétlődést, hiszen a társaságnak csak véges sok tagja van. Legyen Am+1 az első olyan ember, aki már szerepelt a sorozatban előbb is, mondjuk az n-edik helyen: Am+1=An (n<m). Ekkor An-et, An+1-et, An+2-et, …, Am-et ilyen sorrendben leültetve az asztal köré mindenki két ismerőse között fog ülni. (Ez igaz Am-re is, mert Am+1=An.)
A feladatot és megoldását átfogalmazhatjuk gráfelméleti nyelvre.
A gráf csúcsainak egy A1A2…AmAm+1 sorozatát, amelyben minden Ai-t él köt össze az utána következő Ai+1-gyel, a gráf egy sétájának nevezzük.
Ha minden Ai csúcs különböző, akkor útnak nevezzük.
Ha minden Ai különböző, csak Am+1=A1, akkor (gráfelméleti) körnek nevezzük.
Az út, illetve a kör hossza m(vagyis a szomszédos csúcsokat összekötő élek száma), de szokták ehelyett a csúcsok számát is az út, illetve a kör hosszának tekinteni. A kör esetében mindkettő azonos, az út esetében egy a különbség. Megjegyezzük még, hogy a két pontból (tehát egy élből) álló út is út, viszont a legrövidebb körnek is legalább három csúcsa (és három éle) van.
Fogalmazzuk át az 1. feladat állítását ezeknek a gráfelméleti fogalmaknak a segítségével!
| TARTALOMJEGYZÉK |