Arthur király udvarában

Lovász László et al
Részlet a Diszkrét matematika című kötetből
matematika, diszkrét matematika, komplexitáselmélet, algoritmuselmélet, véges struktúrák, polinomiális idő, NP-tulajdonság
szóelválasztás

Arthur király udvarában 150 nőtlen lovag és 150 hajadon vendégeskedett. A király elhatározta, hogy összeházasítja őket. A világraszóló lakodalom azonban komoly akadályba ütközött: a hölgyek és urak némelyike ki nem állhatta egymást, így közöttük nemhogy házasság, de még egy beszélgetés sem jöhetett szóba. Arthur többször is próbálkozott, de minden alkalommal kudarcot vallott. Előhívta hát Merlint, a varázslót, és megparancsolta neki: házasítsa össze a vendégeket úgy, hogy a frigy egyetlen párnak se legyen ellenére. A természetfölötti képességekkel rendelkező mágus egy pillantás alatt átlátta, hogy a 150!1 lehetséges párosítás mindegyikében akadnak össze nem férő felek, és ezt azon nyomban közölte is a királlyal. Mivel azonban Merlin nem csupán nagy varázsló, de meglehetősen kétes alak hírében is állt, a király csak fenntartásokkal bízott benne:

– Találj egy jó párosítást – követelte ellentmondást nem tűrve, – különben életed végéig egy barlangban fogsz raboskodni!

  • 1. 150! (150 faktoriális) = 1 · 2 · 3 · … · 150 – A szerk.

Merlinnek ez alkalommal szerencséje volt: természetfeletti képességeit latba vetve áttekintette a huszadik század elején megjelent szakirodalmat, és talált egy jó érvet, amely – egyszerű földi halandók számára is – alátámasztotta, hogy a nagyszabású terv nem valósítható meg. Visszatért hát a királyhoz, ahol éppen minden vendég jelen volt. Merlin kiválasztott 56 hölgyet, hogy álljon a terem egyik oldalára, a másik oldalra pedig 95 lovagot szólított ki, és megkérdezte:

– Szép hölgyek, van-e köztetek, aki ezen lovagok valamelyikéhez szívesen férjhez menne?

– Nincs! – felelték egyhangúan a hölgyek.

Merlin erre Arthurhoz fordult:

– Felséges király, hogy kívánhatod tőlem, hogy ennek az 56 hölgynek férjet találjak, amikor már csak 55 lovag jöhet szóba potenciális párként?

Így aztán a király, aki kiváló képzésben részesült, minek következtében a skatulyaelvet is jól ismerte, azonnal belátta, hogy lehetetlent kíván, és kegyesen útjára bocsátotta a varázslót.

Nem telt bele sok idő azonban, és a királyi koponyában újabb ötlet fogant. Észrevette ugyanis, hogy a híres kerek asztalnál felszolgált vacsorákat a 150 lovag soha nem tudta békésen végigülni, a szomszédok állandóan – gyakran a szó szoros értelmében is – hajba kaptak valamin. Arthur nem tudott efelett napirendre térni, újra magához rendelte tehát Merlint, és megparancsolta: találjon ki olyan ültetési rendet, amelyben mindenki két jó barátja között foglal helyet. A természetfeletti képességekkel rendelkező varázsló egy szempillantás alatt átlátta, hogy a 150! lehetséges ültetési rend egyike sem megfelelő, és ezt azonmód jelentette is a királynak. Mikor Arthur magyarázatot követelt, Merlin széttárta a karját:

– Uram, királyom, én lennék a legboldogabb, ha létezne egyszerű magyarázat, de csak azt tudom megerősíteni: lehetetlent kívánsz. Ti halandók ezt nem érthetitek meg, legfeljebb úgy, ha hátralévő életetek egészét az érveim hallgatásának szentelitek.

A királynak más tervei voltak hátralévő éveit illetően, így aztán beváltotta fenyegetését: Merlin azóta is befalazva sínylődik egy sötét barlangban – az alkalmazott matematikusok legnagyobb bánatára!

A mese tanulsága, hogy vannak a gráfoknak olyan tulajdonságai, amelyeknek fennállása – megfelelő „prezentációval” könnyen ellenőrizhető. Azt, hogy egy gráfban van teljes párosítás vagy Hamilton-kör,2 legkönnyebben úgy „bizonyíthatjuk be”, hogy mutatunk egyet. Azt, hogy egy páros gráfban nincs teljes párosítás, úgy „bizonyíthatjuk”, hogy megadjuk az egyik „oldal” pontjainak olyan X részhalmazát, amelynek – együttesen – a másik oldalon |X|-nél3 kevesebb szomszédja van. Az Olvasónak és a szigorú Arthur királynak egyaránt az alábbi ábrát ajánljuk figyelmébe.

Egy teljes párosítással rendelkező és egy anélküli páros gráf

A jobb oldali gráfban van teljes párosítás (vastag vonalak jelölik), a bal oldaliban viszont nincs. Az utóbbi tényről a négy fekete pont (és szomszédsága) vizsgálatával győződhetünk meg.
  • 2Egy C kör egy G gráfban Hamilton-kör, ha C a G gráf valamennyi csúcsán áthalad. – A szerk.
  • 3|X| az X halmaz elemeinek száma – A szerk.

A legtöbb gráfelméleti tulajdonság ilyen logikai struktúrával rendelkezik. Ha a tulajdonság fennállása könnyen bizonyítható (demonstrálható), akkor a számítógéptudósok a szóban forgó jellemzőt NP-tulajdonságnak nevezik.4 A Merlinnek feladott két probléma – a teljes párosításé és a Hamilton-köré – nyilvánvalóan NP-tulajdonságok. Ilyen tulajdonságokkal természetesen nemcsak a gráfelméletben, de a matematika szinte minden területén találkozunk. A természetes számok igen-igen fontos NP-tulajdonsága például az, hogy összetettek-e: ha egy n szám összetett, azt legkönnyebben egy n = ab felbontás megadásával támaszthatjuk alá (ahol természetesen a, b > 1).

  • 4Ha valaki kíváncsi rá, az NP a nemdeterminisztikus polinomiális idő kifejezést rövidíti, ennek a különösen érdekes fogalomnak az értelmezését mindazonáltal ehelyütt inkább mellőzzük.

Eddigi megjegyzéseink alapján nyilvánvaló, hogy miként kerülheti el Merlin a bezáratást azokban az esetekben, amelyekben a számára kitűzött feladatnak van megoldása. Tegyük fel például, hogy sikerült találnia a lovagok számára egy jó ültetési rendet. Ekkor nagyon könnyen meggyőzheti Arthurt, hogy valóban megoldotta a feladatot: le kell ültetni a lovagokat, és mindegyiktől meg kell kérdezni, elégedett-e e szomszédaival (vagy kivárni, hogy rendbontás nélkül ér-e véget a vacsora). Mindez pontosan annak felel meg, hogy a „baráti viszonyok gráfjának” az a tulajdonsága, hogy van benne Hamilton-kör, NP-tulajdonság. De akkor hogy lehet, hogy a házassági ügyben a varázsló megmenekült a bebörtönzéstől, az ültetés ügyében viszont kudarcot vallott, és őt magát ültették le (méghozzá örökre) – holott a két feladat közül egyiknek sem volt megoldása? Mi a különbség a teljes párosítás és a Hamilton-kör nemlétezése között? A mese alapján nyilván az Olvasó is kitalálta a választ: a teljes párosítás nemlétezése egy páros gráfnak NP-tulajdonsága, az viszont, hogy egy gráfban nincs Hamilton-kör, az a gráfnak nem NP-tulajdonsága. (Hogy pontosak legyünk: az utóbbi tényt egyelőre senki sem bizonyította be, de erős érvek szólnak amellett, hogy a helyzet a jövőben sem változik meg.)

Vannak tehát olyan NP-tulajdonságok, amelyeknek a fenn-nem-állása is NP-tulajdonság. Azokat a tételeket, amelyek egy NP-tulajdonság fennállásának és egy másik NP-tulajdonság fenn-nem-állásának ekvivalenciáját mondják ki, jó jellemzésnek nevezzük. Nevezetes jó jellemzésekkel a gráfelméletben és a matematika más területein is találkozhatunk.

Sok olyan NP-tulajdonság van, amely még ennél is kellemesebben viselkedik. A lovagok és a hölgyek összeházasításának problémájáról (mondjuk ennek a könyvnek az elolvasása után) akár maga Arthur is eldöntheti, hogy megoldható-e: nem kell mást tennie, mint követni a 10.4. alfejezetben leírt algoritmust. Ez persze sok időt és fáradságot kíván, de közönséges földi halandók is elvégezhetik, Merlin természetfeletti képességeire nincs hozzá szükség. Az efféle, effektív módon eldönthető tulajdonságokat P osztálybeli tulajdonságoknak nevezzük (a P a polinomiális időt rövidíti, ami az effektív módon való kiszámíthatóság pontos, de meglehetősen technikai jellemzése). Ebbe az osztályba tartozik gráfok több más – ebben a könyvben is vizsgált – tulajdonsága is, mint például az összefüggőség vagy egy kör létezése. Annak eldöntése, hogy egy szám prímszám-e vagy sem, szintén ilyen probléma – ezt nem sokkal e könyv nyomdába kerülése előtt sikerült bebizonyítani!

A polinomiális idő és az NP-tulajdonság fogalmának bevezetése jelenti a modern komplexitáselmélet kezdeteit. Az elmélet a tiszta és az alkalmazott matematika számos területét áthatja. A következő alfejezetekben bemutatjuk, miként alkalmazhatók a komplexitáselmélet gondolatai a kriptográfiában,5 az elméleti számítástudomány egyik legfontosabb területén.
  • 5kriptográfia – titkosításelmélet; a titkosítás tudománya
Arthur király
(Winchester-kastély, Winchester)
Merlin verset diktál. (Illusztráció egy 13. századi francia kódexből)
Merlin
(19. századi fametszet)
Függelék

A jóslás a görög mitológia szerint sem volt mindig hálás mesterség. Erről árulkodnak Sztrabón és Apollodórosz feljegyzései:

27. Azután a Gallésion-hegy következik, majd az ión Kolophón városa, s előtte a klarosi Apollón ligete egy régi jósdával. Mint mondják, Kalkhas jós Amphilokhosszal, Amphiaraos fiával, a Trójából való visszatérés közben ide gyalogolt, minthogy azonban Klarosban magánál különb jósra talált, Mopsosra, Mantónak, Teiresias lányának a fiára, bánatában meghalt. Hésiodos ilyenformán adja elő ezt a mondát: Kalkhas a következő kérdést adta föl Mopsosnak:

Bámulatos, hogy e vadfügefán mily sok füge termett,
Bár alacsony, mondd meg, ha tudod, hogy hány füge van rajt’?

Az pedig így felelt:

Tízszer ezer megszámlálva, ha méred, telve a véka; Egy kimarad mégis, de te azt nem igen veheted le.

Így szólt az; mérték és szám, mint mondta, olyan volt. És akkor Kalkhasra leszállt a halálnak az álma.

Fragmentum 160. Rzach

(C643) Pherekidés szerint azonban Kalkhas egy terhes kocát adott föl, hogy annak hány malaca van, Mopsos pedig így felelt: három, de közülük egy nőstény. Minthogy ez valónak bizonyult, bánatában meghalt. Némelyek úgy adják elő, hogy Kalkhas a kocát adta föl, Mopsos pedig a vadfügét, és az utóbbi eltalálta az igazat, ő azonban nem, s így bánatában és egy jóslat értelmében meghalt. Sophoklés ugyanis »Heléné visszakövetelésé«-ben azt mondja, hogy a végzet rendelése szerint meg kell halnia, ha magánál különb jósra talál. Ez azonban Kilikiába viszi át a vetélkedést és Kalkhas halálát. Ilyenek a régi mondák.

Strabón: Geógraphika. Fordította Földy József. Lektorálta és az előszót írta Balázs János. Budapest: Gondolat, 1977. XIV. I., 674–675. p.

2. Amphilokhosz, Kalkhasz, Leonteusz, Podaleiriosz és Polüpoitész, hajóikat Ilionban hagyva, gyalogszerrel Kolophónba utaztak; ott temették el Kalkhaszt, akinek az volt a végzete, hogy nyomban meghal, ha nálánál bölcsebb jóssal találkozik.

3. Nos, Mopszosz, a jós adott nekik szállást, Apollón és Mantó fia, s ez a Mopszosz vitába keveredett Kalkhasszal a jóslás tudományáról. Nőtt ott egy vadfügefa; Kalkhasz megkérdezte, hány füge van rajta. Mopszosz azt felelte, hogy tízezer meg egy vékányi és a tetejében még egy. És csakugyan annyit számoltak össze.

4. Aztán, egy vemhes koca láttán, Mopszosz kérdezte meg Kalkhaszt, hogy hány malac van a hasában, és mikor fog elleni. Mikor Kalkhasz azt válaszolta, hogy nyolc, Mopszosz mosolyogva jegyezte meg: »Kalkhasz jóslata nem pontos, én azonban, Apollón és Mantó fia, bővében vagyok a pontos jósláshoz szükséges éleslátásnak, tehát megjósolom: nem nyolc malac van a hasában, mint Kalkhasz állítja, hanem kilenc, mind kan lesz, és semmi kétség, holnap a hatodik órában fog megelleni.« Így is történt. Kalkhasz belehalt a bánatba; Notionban temették el.

Apollodórosz: Mitológia. Fordította Horváth Judit. Az utószót írta Szepessy Tibor. (Az Ókori Irodalom Kiskönyvtára.) Budapest: Európa, 1977. Kivonatok VI. 2–4, 143–144. p.

Azt persze nagyon nehéz elképzelni, hogy tízezer-egy fügét hiba nélkül megszámoltak, azt viszont annál inkább, hogy megpróbálták valószínűsíteni a jóslat eredményét. Ennek lehetséges módja a következő: a jóslat után, titokban leszakítanak három fügét a fáról, majd újra felkérik Mopszoszt a fán található fügék számának meghatározására. Nem kétséges, hogy ha az első érték helyes volt, akkor most három fügével kevesebb lesz az eredmény.

Forrás

Lovász László–Pelikán József–Vesztergombi Katalin: Diszkrét matematika. Budapest: TypoTex, 2006. 15.1 fejezet.


Az alfejezetet, amely eredetileg a Yale Egyetemen tartott előadások segédanyaga volt, (kis módosításokkal) Lovász László és M. D. Plummer Matching Theory című könyvéből (Akadémiai Kiadó, North Holland, Budapest, 1986) vettük át, Mike Plummer szíves engedélyével.