Tento text je automatický (t.j. pokusne) formátovaný do HTML! Konvertor je optimalizovaný na texty, ktoré sa dajú rozdeliť na odstavce (dva konce riadku a podobne). Okrem odstavcov sa snaží dostať priamu reč na začiatok riadka.


LABYRINT
ci
DISKRETNA ROZPRAVKA

Kde bolo - tam bolo, v jednej dalekej diskretnej mnozine zila stara Relacia, ktora mala 4 dcery - Reflexiu, Symetriu, Antisymetriu a Tranzitivnost. Sestry spolu nazivali v podstate svorne, s vynimkou Symetrie a Antisymetrie, ktore spolu v jednej mnozine nikdy dlho nevydrzali a vzdy sa rozhodli bud pre Ciastocne usporiadanie alebo Ekvivalenciu, vzdy opacne, ako si vybrala ta druha. Obe radi nicili tej druhej tazko vytvorene mnoziny. Reflexia bola vsadebolka; mnoziny sa o nu trhali len aby boli plne reflexivne a Tranzitivnost sa uplatnovala ako psychologicka, ktora hladala priame vztahy medzi prvkami mnoziny, ktore boli od seba vzdialene.

Jedneho dna sa Relacia rozhodla, ze sa dcery uz ucia diskretnu matematiku dostatocne dlho a ze posle dcery do zloziteho grafu, aby vedela, ktora z nich je schopna najst jeho kostru a najkratsiu cestu k vrcholu K pomocou algoritmu prehladavania stromu do hlbky a Xovho algoritmu. A tak aj urobila ...

Dcery sa vybrali do grafu a rozdelili si ulohy. Symetriu poverili pamatanim si linky, aby sa mohli vratit spat po tej istej ceste, ked prehladavanie do hlbky skonci na mrtvom bode a Reflexia dostala za ulohu tipovat si pomocou metody "pozriem a vidim" vrcholy, ktore pouziju pri hladani cesty. Ako sa tak vydali na cestu, okolo nich sa presuva banda dalsich turistov, ktori prave skusaju stastie pomocou algoritmu prehladavania do sirky. Reflexia so Symetriou uspesne spolupracovali a coskoro mali za sebou polovicu grafu ...

Tu lepsiu ...

Relacie a ani Relacia nemohla vediet, ze graf, v ktorom vykonavali svoje povinnosti zil svojim vlastnym zivotom. Akoby aj nie, ved v jeho psychike sa odrazala cela zlomyselnost a logika najmocnejsej a najhorsej vladkyne - Triedy J, krycim menom Teta. Preto sa graf aktivoval a zacal sa zacyklovat az bol z neho labyrint.

Po niekolkych cykloch relacie vedeli, ze nenajdu nielen kostru grafu, ale ani akukolvek cestu k vrcholu K, pri ktorom, ako im povedala Relacia, malo byt pripravenych aj zopar krasnych logickych uloh z Diskretnej matematiky. Antisymetria sa uz tesila, ze sa (opat) vrhne do riesenia problemu Alenky pred dverami a zahady 7 mostov a verila si, ze sa jej to tentokrat uz podari. No vrcholy okolo boli oznacovane cislami a ked indexy dosiahli dvojbajtovu hodnotu, zacala Reflexia pochybovat, ze su na spravnej ceste. Strom, ktory starostlivo zaznacovali do prirucnej Carnaughovej mapy uz nadobudol charakter najvacsieho pralesa, aky kedy kto vymyslel. Zabludili ... a aj ked ich na konci necakal netvor, nebolo iste, ci ma labyrint vobec koniec.

Medzi sestrami vypukol mensi chaos. Symetria a Antisymetria sa zasa zacali hadat a ani Tranzitivnost medzi nimi nemohla spravit poriadok. Uz sa zdalo, ze ostanu naveky stiesnene pri vrchole A332445, kde sa ozvala Reflexia:
"Ticho tu bude!" Sestry posluchli. Boli na to zvyknute.
"Musime sa dostat von a pouzijeme nato vsetky prostriedky! Skusili ste uz rozmyslat nad tym, co by sa asi stalo, keby sme pouzili Kruskalov algoritmus ???" Sestry neodpovedali. Nemali ani najmensej potuchy, o com Reflexia hovori a preto sa zatvarili velmi hamblivo a sklopili zrak. Reflexia si ulahcene vydychla. Tiez nemala potuchy, co za algoritmus to prave spomenula, ale bola to jedna z mala veci, ktore si este zo skoly pamatala. A musela predsa nastolit poriadok!


"Zacneme pekne po poriadku! Symetria! Zisti, ako daleho sa mozeme dostat tou cestou, ktorou sme prisli!" prikazala Reflexia a sestra sa vydala na cestu. Mala vzacnu orientacnu schopnost, kvoli ktorej sa z kazdej cesty vedela dostat spat, co sa jej v mnozinach uz tolkokrat zislo a tym predcila Antisymetriu, ktora mala naopak mizernu pamat. A tento velky graf nebol v sirsej podstate nic ine, ako velka mnozina. Reflexia potom poverila Tranzitivnost, aby od vrchola A332445 zistila, co bude v jej silach a sama sa zatial poobzerala po okoli. Ked sa onedlho zasa zisli, Symetria hlasila, ze cesta spat je ista len do vzdialenosti 5 vrcholov, pricom udala aj presnu vzdialenost podla ohodnotenych hran grafu. To vsak Reflexiu prilis nezaujimalo. Vyhlasila, ze naspat je cesta nemozna.

Tranzitivnost zistila, ze vrchol A332445 nie je prilis inteligentny, no podarilo sa jej vymamit smer k mudrejsiemu a skusenejsiemu vrcholu. A tak sa vydali na cestu. Symetria si znovu zacala zapamatavat okolie.

Pomocou algoritmu prehladavania sa konecne dostali na jedinu cestu, ktora nebola zakoncena slepym vrcholom uz po sestdesiatej zakrute a Tranzitivnost spoznala vrchol A546785, o ktorom uz bola rec.
"Ahoj A546785!"
"Ahoj, kto ste ? Co potrebujete ?" ozval sa vrchol privetivym hlasom.
"Ako sa dostaneme k vrcholu K?" opytala sa Tranzitivnost nenapadne.
"K ?? V zivote som o nom nepocul. To bude zrejme niekde v okoli hrany 43." odpovedal vrchol.
"A ako sa tam dostaneme?" opytala sa Reflexia.
"Skuste po hrane 3354 na dalsej krizovatke. Zahnete doprava a ..." Cesta, ktoru vrchol nadiktoval, nebola ani prilis dlha. Ale aj tak plne vytazila pamat Symetrie. Relacie sa podakovali a vydali sa na cestu.

Na konci dlhocizneho zoznamu vrcholov a hran sa zaskvel vrchol A12 a relacie zaplesali. Ich ciel nemohol byt daleko. No predsa sa pred nimi zjavila nepredstavitelna prekazka.

Krizovatka pred nimi ukazovala dve uplne rovnake hrany a po beznom preskumani okolia kazdej z nich dospeli relacie k zaveru, ze su presnymi zrkadlovymi kopiami. No sil mali uz malo, ved uz davno nevideli a neuvadzali do relacie prvky nejakej mnoziny. Dokonca aj Reflexia zacala stracat sebavedomie. Kam sa vydat ? Pravdepodobnost bola 50% ...

Vtedy sa ozval nervydrasajuci rev a Antisymetria sa rozbehla priamo k vrcholu.
"Koniec symetrie!!" zrevala a vrazila do geometrickeho stredu hran, priamo do vrchola a rozcesla graf na dve casti. Relacie nasiroko otvarali oci - priamo pred nimi sa zjavil vrchol K a lakave prvky mnoziny pripravene akoby len a len pre relacie ...

Ked sa relacie dosyta narelaciovali, pomocou mapky ziskanej od starej dobrej Uplnej Normalnej Konjuktivnej Formy, ktora sice nebola nic viac ako konjukcia elementarnych disjunkcii, ale aspon byvala nedaleko vrchola K sa vybrali do svojej mnoziny. Stara Relacia bola stastna, ze sa jej dcery vratili zive a zdrave a pochvalila ich za ich vykony. Neskor sa po mnozine rozsirilo, ze graf sa celkom rozsypal a relacie celej diskretnej mnoziny mali s byvalymi vrcholmi prijemnu pracu cely semester.

A tak pracuju a tesia sa, kym Trieda J dalsi graf nevymysli.

[ (c) VIX 6/8/96 ]
All rights reserved ;-)) PS - akakolvek podobnost s nazvami z DM je ciste nahodna ... ;-))

Tu môžete ohodnotiť poviedku:


vix-libris, 27/1/2002-0.84 (beta)
(c) VIX 2001-2002
Generated: 21/09/2019, 09:55:24