A gráfelméletről IV.
2007/11/21 08:00
656 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.
A korábbi írásaink után, most egy újabb probléma vizsgálata hozza meg annak lehetőségét, hogy továbblépjünk a gráfelmélet alapjainak tanulmányozásában.

A probléma:

Egy iskolai kirándulás 28 résztvevőjét megkérdezték, hogy hány osztálytársa van a kirándulók között. Az első tizenöt válaszoló közül nyolcan mondtak 5-öt, ketten 4-et és 5-en hármat.

Mi lehetett a hiányzó 13 válasz, ha mindenkinek volt osztálytársa a kiránduláson?

1. ábra

Azoknak a tanulóknak az osztályából, akiknek öt osztálytársuk van a kirándulók között, hat gyerek érkezett. Ha egy gráf pontjai jelölik a gyerekeket, és az élei pedig az „osztálytársa” relációt, akkor az egy ilyen osztályból érkezettek egymáshoz való viszonyát az 1. ábra mutatja.

Kérdés az, hogy hány ilyen „hatos” van a kirándulók között.

Egynél biztosan több, mert nyolc kiránduló biztosan ilyen hatosoknak eleme.

2. ábra

Azoknak a tanulóknak az osztályából, akiknek négy osztálytársuk van a kirándulók között, öt gyerek érkezett. Egy ilyen osztályból érkezettek egymáshoz való viszonyát a 2. ábra mutatja.

Kérdés az, hogy hány ilyen „ötös” van a kirándulók között.

Legalább egy biztosan van, mert ketten megjelöltek négy kiránduló osztálytársat az első tizenöt válaszoló közül.

3. ábra

Azoknak a tanulóknak az osztályából, akiknek három osztálytársuk van a kirándulók között, négy tanuló érkezett. Egy ilyen osztályból érkezettek egymáshoz való viszonyát a 3. ábrán szemléltetjük.

Hány ilyen „négyes” van a kirándulók között?

Legalább kettő biztosan van, mert öten már úgy nyilatkoztak, hogy négy kiránduló osztálytársuk van.

Legyen most már a „hatosok” száma h, az „ötösök” száma o, és a „négyesek” száma n! Ekkor teljesülni kell a következő egyenlőtlenségnek:

ahol h legalább 2 és n legalább 2.

Az adott feltételek az egyenlőtlenség megoldásai h = 2, o = 1 és n = 2.

Ezek szerint a hiányzó 13 válasz között 4 darab 5-ös, 3 darab 4-es és három darab 3-as. Maradt még három gyerek, de mivel mindenkinek volt osztálytársa a kirándulók között ők egy osztályból érkeztek, és így mindhármuknak két osztálytársa volt a kirándulók között.

A megoldás közben bemutatott „hatosok”, „ötösök” és „négyesek” olyan egyszerű gráfok, amelyeknek bármely pontja bármely pont szomszédja. Az ilyen gráfokat teljes gráfoknak nevezzük.

Egy kérdés az olvasóhoz:

Hány éle van egy n pontú teljes gráfnak?

Irodalom:Irodalom:

  1. 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
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek