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.

A matematikus gyakran foglalkozik olyan problémákkal, melyeknek látszólag semmi köze a való élethez. Ilyen például a gráfelmélet. A gráf olyan alakzat, amely csak pontokból és azokat összekötő vonalakból áll. A pontokat csomóknak, a vonalakat pedig éleknek nevezzük. A matematikus számára pusztán a gráf topológiai rendezésének van jelentősége, az elemek pontos hozzárendelésének nincs. A csomók ilyen értelemben gyöngyszemekhez hasonlítanak, az élek pedig gumifonalakhoz. A gyöngyök hozzárendelése tetszőleges, a fonalak pedig tetszés szerint összefonhatók: a gráfon ez mit sem változtat. Ezért előfordul, hogy két gráf teljesen másképpen néz ki, a valóságban azonban egy és ugyanazon gráf kétféle ábrázolásáról van szó.

Ha egy gráfot közelebbről szemügyre veszünk, elektromos áramkörre emlékeztet. Ennek építőelemei vékony rézrétegekből állnak, melyekbe vezetékeket maratnak. Ezek kötik össze az áramkör egyes elemeit. Matematikus-szemmel a vezetékek tekinthetők egy gráf éleinek, a forrasztási pontok pedig a csomóinak. A vezetékek vezetési irányának, amíg a megfelelő építőelemeket kötik össze, többnyire nincs különösebb jelentősége. Az áramkör-gráfban csak fizikai kereszteződés nem lehet: ez rövidzárlatot okozna a vezetékek között. A matematika sík-, vagyis két dimenziós gráfjainak esetében azonban lehetnek kereszteződési pontok, vagyis az éleknek lehetnek metszéspontjaik. Az elméleti szakembert ezek különösen foglalkoztatják. Az itt felmerülő problémák egyikének megoldása közben a matematikusok a modern számítógép adta lehetőségek határait feszegették.

Síkgráf

Richard K. Guy

Az 1, 2 és 3 csomót tartalmazó gráfokban nem lehetnek kereszteződési pontok. A 4 csomót tartalmazó gráf csomói is rendezhetők úgy, hogy a hat él sehol ne keresztezze egymást. Az 5 csomót tartalmazó az első olyan gráf, melyben elkerülhetetlen legalább egy kereszteződési pont megléte. Ennél nagyobb csomószám esetén a kereszteződési szám meredek emelkedik: 6 csomónál 3, 7 csomónál 9, 8 csomónál 19 és 9 csomónál 36 kereszteződési pont van. A 10 csomós gráf kereszteződési pontjaimak számát 2000-ben a vancouveri University of British Columbia szakemberei, Alex Brodsky, Stephane Durocher és Ellen Gether határozták meg. Tőlük függetlenül és az övékétől eltérő módszerrel ugyanerre az eredményre jutott Oswin Aichholzer, Franz Aurenhammer és Hannes Krasser a grazi Technische Universitäten.