Tízezer processzor szövetsége

Egy grazi matematikus-csoport az elmúlt év végén egyenleteket dolgozott ki, melyekkel meghatározható a síkgráfok éleinek minimális kereszteződési száma. Sikerükön világszerte tízezer számítógép dolgozott.

Aichholzert és társait eredetileg teljesen más érdekelte. Egy teljes, sík, egyenes élű gráf különböző formáinak számát akarták meghatározni bizonyos csomószám esetén. 1, 2 és 3 csomót tartalmazó gráfok esetében mindig csak egyetlen forma létezik. 4 pontot tartalmazó gráf esetében található először két forma. Az egyikben a 4 csomó egy konvex négyszög sarkain helyezkedik el, a hat él pedig a síkidom négy oldalát és két átlóját adja. A két átló egy pontban keresztezi egymást. A másik forma esetében 3 csomó és a köztük húzott élek háromszöget képeznek, a negyedik csomó pedig ennek a belsejében van. Ekkor az összesen hat lehetséges él sehol sem keresztezi egymást.

Nagyobb csomószám esetén ez a szám gyorsan növekszik. 10 pontnál már 14 millió gráf lehetséges. Aichholzer csoportja ezek mindegyikét szisztematikusan rendszerezte, és ennek mintegy melléktermékeként kimutatta, hogy a kereszteződési pontok legkisebb lehetséges száma 62, ami a 14 millió közül csak két különböző gráfnál lehetséges. Minden más forma több kereszteződési pontot tartalmaz.

Síkgráfok

A siker felbátorította őket, és módszerüket a 11 csomót tartalmazó gráfra is alkalmazták. Ennél több mint kétmilliárd különböző gráfot találtak, és felfedezték, hogy a kereszteződési szám 102. Ezzel az eredménnyel módszerük lehetőségei kimerültek. Tizenegynél nagyobb csomószám esetén a lehetséges gráfok száma már akkora, hogy szisztematikus feltárásukra a világ legnagyobb teljesítményű számítógépével sincs lehetőség. Aichholzer és csoportja ezért finomított módszerén, és eleve kizárhatóvá tett jelentős számú olyan formát, melyben a kereszteződési szám a minimálisnál magasabb. Csakhogy még a maradék vizsgálathoz is olyan nagy teljesítményű számítógépre volt szükség, amilyet a grazi egyetem nem tudott beszerezni.

2004-ben Aichholzer ezért életre hívta a "Rectilinear Crossing Number Project"-et, melynek keretében ki-ki az interneten keresztül bocsáthatja a program rendelkezésére komputerének számítókapacitását. A projekten immár hétezer-ötszáz számítógép dolgozik a világ nyolcvan országában. A kutatás közel volt a sikerhez. A következő két évben sikerült a kereszteződési számot 12-17 csomót tartalmazó gráfokban meghatározni: ez 12 esetében 153, 13-nál 229, 14-nél 324, 15-nél 447, 16-nál 603 és 17-nél 798. Sajnos ez még korántsem volt elegendő olyan egyenlet felállításához, melynek segítségével bármilyen számú csomó esetén megállapítható a kereszteződési szám. Végül azonban ez is sikerült: Aichholzer olyan egyenleteket fejlesztett ki, melyekkel meghatározható a kereszteződési számok alsó határa. A 19 és 21 csomóból álló gráfoknál olyan példákat talált, melyeknek kereszteződési száma pontosan megegyezett az alsó határral. 19 csomó esetében ez a szám 1318, 21 csomó esetében pedig 2055. Végül tavaly decemberben a matematikus-team világszerte tízezer processzor napi kapacitásával meghatározta a kereszteződési számot a 18 csomóból álló gráfnál: ez 1029. Januárban az eredményt számításokkal is ellenőrizték.

Forrás: Frankfurter Allgemeine Zeitung