Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

Teljes gráfok felbontásairól

Teljes gráfok felbontásairól

Gyárfás, András

Hraskó, András


Teljes gráfnak nevezünk egy n elemű halmazt (pontok halmaza) különböző elemeiből képzett párjaival (élek halmaza). A pontokat általában { 1 , 2 , , n } = [ n ] jelöli, az éleket i j és a teljes gráfra a K n jelölés szokásos. Tehát K n -nek n 2 = n ( n - 1 ) 2 éle van. Ebben a cikkben teljes gráfok felbontásaival kapcsolatos eredményeket mutatok be, lehetőleg érdekes és máshol is hasznosítható bizonyításokkal. Felbontáson azt értjük, hogy K n teljes gráfot előállítjuk olyan részgráfok egyesítéseként, amelyeknek nincs közös élük. Egy híres példa K 7 felbontása hét K 3 -ra (Fano-sík) ami lényegében egyértelmű és az { 1 , 2 , 4 } egész eltolásaival kapható mod 7 aritmetikával számolva.

A sakkot ketten, az ultit hárman, a bridzset négyen játsszák. Gráfok felbontása helyett játszhatunk is…

1. Programok egy hétre

Sokszor szemléletesebb pontok helyett emberekről beszélni, az előző állítás például azt mondja, hogy hét játékos hét ultipartit szervezhet hét napra úgy, hogy bármely két játékos pontosan egyszer játszik együtt.

1. ábra. Ultipartik a Fano-sík alapján: a hét játékos a hét pont, a hét parti a hét, egy vonalra (szakaszra, ill. körre) eső ponthármas

2. ábra. Ultipartik mod 7 aritmetikában: a hét játékos a hét szám, a hét parti az { 1 , 2 , 4 } hármas és annak eltoltjai mod 7

Hétfőn játszik 1 , 2 , 4 , kedden 2 , 3 , 5 , és így tovább, vasárnap 0 , 1 , 3 . Minden nap hárman játszanak, a többiek szabadok.

1. feladat. Bizonyítsuk be, hogy 15 játékosnak is lehet hét napra ultipartikat szervezni úgy, hogy bármely két játékos pontosan egyszer játsszon együtt!

Ehhez öt asztal kell (három-három székkel), minden nap mindenki játszik. Nem egyszerű megszervezni az ültetést… Persze könnyű elkezdeni, az első asztal beosztása hét napra lehet 1 , 2 , 3 ; 1 , 4 , 5 ; 1 , 6 , 7 ; …; 1 , 14 , 15 . Próbáljuk megtervezni a másik négy asztal beosztását is! Ezt a problémát Kirkman tiszteletes tűzte ki 1847-ben egy angol magazinban – persze nem ultiról szólt, hanem 15 iskolásleány sétájáról hét napon hármas sorokban…

Egy könnyebb probléma:

2. feladat. Készítsük el 8 bridzsező ültetési tervét hét napra két asztalhoz (négy-négy székkel) úgy, hogy bármely három pontosan egyszer üljön közös asztalnál!

Végül a legkönnyebb:

3. feladat. Készítsük el 8 sakkozó ültetési tervét hét napra négy asztalhoz (két-két székkel) úgy, hogy bármely kettő pontosan egyszer üljön közös asztalnál. Erre hamarosan látunk megoldásokat…