V pavučině sítí - v říši náhody I

rubrika: Populárně naučný koutek


Elementární základy teorie sítí se datují někdy do první poloviny 18. století a zasloužil se o to nejlepší matematik tohoto století Leonhard Paul Euler. Euler, původem Švýcar, který strávil svou profesionální dráhu v Berlíně a v Petěrburgu, měl zcela výjimečný vliv na všechny oblasti matematiky, fyziky a techniky. Nejenže význam jeho objevů nemá obdoby, ale už pouhé jejich množství je nesmírné. Eulerovy sebrané spisy obnášejí dnes téměř 80 stostránkových svazků.

Lucifer


Posledních sedmnáct let jeho života, od návratu do Petěrburgu roku 1776 do jeho smrti ve věku šestasedmdesáti let, představovalo dosti neklidné období. A přesto, navzdory mnoha osobním tragédiím vytvořil v těchto letech zhruba polovinu svého díla, například pojednání o pohybu Měsíce v rozsahu 775 stran, široce užívanou učebnici algebry, třísvazkové pojednání o integrálním počtu, a přitom všem stále publikoval jeden matematický článek týdně v časopise petěrburské Akademie věd. Úžasné na tom je, že v té době stěží napsal nebo přečetl řádek textu. Brzy po svém návratu do Petěrburgu přišel částečně o zrak a po neúspěšné operaci šedého zákalu roku 1771 oslepl úplně. Všechny ty tisíce stran matematických formulí diktoval zpaměti.

O třicet let dříve, když mu zrak ještě sloužil, sepsal krátký článek, v němž se zabýval zábavným problémem, který vznikl v Královci (dnes Kaliningrad). Královec, kvetoucí metropole východního Pruska, nemohl na počátku 18. století vědět, jaký smutný a válkou poznamenaný osud jej čeká jakožto dějiště jedné z nejkrutějších bitev 2. světové války. Na soudobých leptech je vidět prosperující město na březích řeky Pregel (Pregola), kde čilý námořní ruch a směna zboží poskytovaly pohodlné živobytí místním obchodníkům a jejich rodinám. Zdravé hospodářství umožnilo městské radě postavit přes řeku hned sedm mostů. Pět z nich spojovalo elegantní ostrov Kneiphof, vklíněný mezi dvěma rameny řeky, s ostatními částmi města. Další dva mosty překračovaly dvě říční ramena (viz obrázek). Obyvatelé Královce, ukolébaní obdobím míru a prosperity, se rádi bavili různými hlavolamy, a jeden z nich zněl takto: Je možné přejít všech sedm mostů a nejít po žádném z nich dvakrát? Nikomu se nepodařilo takovou cestu najít, dokud v roce 1875 nepostavili ještě další most.

Téměř 150 let před stavbou nového mostu, roku 1736, předložil Euler přesný matematický důkaz, že v případě sedmi mostů žádná taková cesta neexistuje. Nejenže vyřešil královecký hlavolam, ale ve svém článku i nevědomky založil nesmírně rozsáhlý matematický obor, teorii grafů. Dnes je teorie grafů základem našich úvah o sítích. Eulerův důkaz je jednoduchý a elegantní a pochopí ho i ten, kdo nestudoval matematiku. Do historie se však nezapsal ani tak samotný důkaz, jako spíš jeden jeho krok, který Euler učinil, aby dospěl k řešení. Eulerova převratná idea spočívala v tom, že si představil Královec s jeho mosty jako graf neboli soubor uzlů spojených vlákny neboli hranami. Provedl to tak, že každou ze čtyř oblastí pevniny, oddělených řekou, reprezentoval jedním uzlem, a označil si je písmeny A, B, C, D. Pak nakreslil mosty jakožto vlákna a spojil jimi ty oblasti souše, které navzájem spojoval most, čímž vznikl graf (viz obrázek).

(Poznámka: Anglický termín link se podle kontextu překládá různým způsobem, kupříkladu jako spoj, vazba nebo odkaz. V případě grafů se také dá použít termín vlákno, česká matematická literatura však výhradně používá termín hrana. Překladatel zdroje se přiklonil k hranám, já se však přikloním k vláknům, protože tento termín lépe odpovídá pavučině sítí.)

Eulerův důkaz, že v Královci není žádná cesta, která by procházela všemi mosty a každým právě jednou, se zakládal na jednoduchém pozorování. Uzly, z nichž vychází lichý počet vláken, musí být buď počátečním, nebo koncovým bodem procházky. Souvislá cesta, která prochází všemi mosty, může mít pouze jeden počáteční a jeden koncový bod. Taková cesta tedy nemůže existovat v grafu, který má víc než dva uzly s lichým počtem vláken. A protože graf města Královce má takové uzly čtyři, požadovanou cestu není možné najít.

Pro nás je na Eulerově důkazu nejdůležitější to, že existence cesty nezávisí na tom, jak důmyslně ji hledáme - jde o vlastnost samotného grafu. Jakmile je jednou dáno schéma královeckých mostů, pak i kdybychom byli sebechytřejší, nepodaří se nám nikdy žádanou cestu najít. Obyvatelé Královce nakonec dali Eulerovi za pravdu, zanechali neplodných pokusů a roku 1875 postavili mezi oblastmi B a C nový most, čímž zvýšili počet vláken u těchto uzlů na čtyři. Nyní zbývaly už jen dva uzly (A a D) s lichým počtem vláken. Pak už bylo docela snadné najít požadovanou cestu.

Podíváme-li se zpět, uvidíme poučení, které sám Euler nezamýšlel: v konstrukci grafů či sítí se skrývají některé vlastnosti, které nás omezují či nám naopak pomáhají, když tyto sítě chceme k něčemu používat. Stavba a struktura grafů či sítí je klíčem k pochopení komplexního světa kolem nás. Malá změna topologie, týkající se pouze několika málo uzlů nebo vláken, může otevřít skryté dveře a uvolnit prostor novým možnostem.

Teorie grafů po Eulerovi zažila prudký rozmach a přispěli k ní takoví matematičtí velikáni, jako byli Augustin-Louis Cauchy, William Hamilton, Arthur Cayley, Gustaff Kirchhoff a George Pólya. Objevili skoro všechno, co je dnes známo o velkých uspořádaných grafech, jako jsou mřížky vytvářené atomy v krystalu či šestiúhelníkové mřížky, které skládají včely, když dělají plástev. Až do poloviny 20. století byl cíl teorie grafů jednoduchý: snažila se objevit a katalogizovat vlastnosti různých typů grafů. Mezi slavné problémy patřilo hledání únikové cesty z bludiště či labyrintu, což bylo poprvé vyřešeno roku 1873, nebo hledání posloupnosti kroků jezdce na šachovnici tak, aby každé políčko bylo navštíveno právě jednou a aby se jezdec vrátil zpět do své výchozí pozice. Některé z obtížnějších problémů zůstávaly oříškem celá staletí.

Od Eulerovy inspirující práce uběhla dvě století, než matematici přešli od studia vlastností nejrůznějších grafů k tomu, aby si položili naprosto zásadní otázku, jak grafy, či obecněji sítě, vznikají. Tyto otázky, a také první odpovědi na ně, se objevily teprve v padesátých letech 20. století, když dva maďarští matematici provedli v teorii grafů revoluci.

A o tom bude druhá část této kapitoly z pavučiny sítí, v níž se rovněž dozvíte, proč se v jejím názvu nachází slovní spojení "v říši náhody".

Zdroj: Albert-László Barabási, V pavučině sítí


komentářů: 4         



Komentáře (4)


Vložení nového příspěvku
Jméno
E-mail  (není povinné)
Název  (není povinné)
Příspěvek 
PlačícíÚžasnýKřičícíMrkajícíNerozhodnýS vyplazeným jazykemPřekvapenýUsmívající seMlčícíJe na prachySmějící seLíbajícíNevinnýZamračenýŠlápnul vedleRozpačitýOspalýAhojZamilovaný
Kontrolní kód_   

« strana 1 »

EvaO
4
EvaO * 21.07.2012, 21:04:07
Dlouhý název obvykle signalizuje i náročnější téma. Lucifer prostě své vědecké zaměření nezapře. I přes dlouhý název jsem si článek přečetla. Nejsem vědecký typ, přírodní témata jsou mi bližší. Nepochybuju ale o tom, že článek si své duše spřízněné najde.

Axina
3
Axina * 21.07.2012, 14:45:55
A není to málo Antone Pavloviči ...? Mrkající

Lucifer
2
Lucifer * 21.07.2012, 14:39:02
Název "Sedm mostů města Královce" je stále ještě příliš dlouhý. Kloním se k japonské miniaturizaci "Graf I" anebo ještě lépe "G I", to už by snad nemělo nikoho od četby odradit Úžasný

Axina
1
Axina * 21.07.2012, 13:40:34
Lucifere, mám iniciativní připomínku: Neměly by články mít kratší a přitažlivější název? Třeba ten dnešní bych nazvala "Sedm mostů města Královce". Já vím, že je to na úkor přesnosti, protože článek je obecnější, než jen na téma toho vyřešeného matematického problému. Ale ono se asi schyluje ke článku "V pavučině sítí - v říši náhody II". Takže chci varovat. Jen si vzpomeň na EvuO. Jak se článek jmenuje "Postbiologická inteligence III - Umělá inteligence II", tak ho ani nezačne číst S vyplazeným jazykem

«     1     »