Feladat: A.355 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2004/október, 425. oldal  PDF  |  MathML 
Témakör(ök): Irányított gráfok, Nehéz feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az MO űrvárosban 100 űrállomás van. Bármely kettőt alagút köt össze. Az alagutak közül 100-ban kétirányú, a többiben egyirányú a közlekedés. 4 űrállomást szorosan kapcsolódónak nevezünk, ha bármelyikükről eljuthatunk a többi háromba a 4 állomás közti alagutakon keresztül. Tervezzük meg az MO várost úgy, hogy abban a lehető legtöbb szorosan kapcsolódó négyes legyen. Adjuk meg a maximumot, és bizonyítsuk is be.