Levelezős csapatverseny – 2. feladatsor – megoldások

III. feladat – 10 pont

Néhány nap játék után Jancsi nekilátott felkutatni régi számítógépét. Az indiai diszpécsertől megtudta, hogy a számítógép gyártója egy lengyel logisztikai központba szállítja az átvett gépeket, ahol az alkatrészeket szétválogatják újrahasznosítás céljából. Ezért úgy döntött, hogy vásárol egy repülőjegyet, hogy még a szétszerelés előtt visszaszerezhesse az értékes megoldásokat. Azonban az utazási irodában nagy felfordulás volt, nem tudtak jegyet eladni, amíg nem sikerült a következő naptól kötelező érvényű EU direktívákat teljesítő menetrendet elkészíteni.

Az európai polgárok nem szeretik az átszállást, ezért az Európai Parlament elfogadott határozata alapján 2013. január 1-től a tagállamok légitársaságai kénytelenek úgy közlekedtetni járataikat, hogy bármely repülőtérről bármelyik másikra legfeljebb egy átszállással el lehessen jutni. Továbbá a világgazdasági válság miatt minden repülőtéren legfeljebb 3 járat végállomása lehet. (Egy járat mindig két reptér között ingázik, máshol közben nem száll le.)

III. Legfeljebb hány reptérrel lehet ilyen rendszert működtetni?

Megoldás: Ha kijelölünk egy bázisrepteret, akkor az innen közvetlenül elérhető repterek száma 3.
Ezek mindegyikéről maximum 3 járat indul, de ezek közül az egyik természetesen a bázisreptérre visz vissza, így mindegyikről még kér járat repülhet máshova. Ez maximum 6 újabb reptér. Ezzel beláttuk, hogy maximum 1+3+6=10 reptérrel működhet a rendszer, de azt nem, hogy ennyit meg is lehet csinálni.

Ehhez meg kell adnunk egy konstrukciót, 10 reptérrel, és a közöttük menő járatokkal. (Tulajdonképpen az előző bekezdés 6 db „második generációs repterét” kell egymás között megfelelően összekötögetni), amire jó az ábrán látható. (Megj.: itt tulajdonképpen egy 6 hosszú kört rajzolunk a 6 reptérre. Ha két darab háromszöget rajzolunk, az az ábra majdnem úgyanígy néz ki, de rossz.)



(Második megj.: Ezt a gráfot Petersen-gráfnak hívják, és elég gyakran jó konstrukció vagy ellenpélda)

Miután Jancsi segített a társaságnak megtervezni a menetrendet, az ajándékba kapott jeggyel elutazott számítógépe után. Kisebb nehézségek árán megtalálta a Wroclaw mellett fekvő logisztikai központot.

Vissza a feladatsorhoz | I. feladat | II. feladat | III. feladat | IV. feladat | V. feladat | VI. feladat | VII. feladat

A verseny kereteit a TÁMOP - 4.2.2/B-10/1-2010-0030 „Önálló lépések a tudomány területén” pályázat biztosította.