Tato kniha je Vám k dispozici zdarma. Mimo jiné z tohoto důvodu neprošla korekturami a redakčními úpravami nakladatele, stejně tak výsledná elektronická podoba knihy nebyla detailně kontrolována. To znamená, že kniha může obsahovat gramatické, stylistické a jiné chyby. Omlouváme se za ně.

A abychom nezapomněli: to, že je kniha zdarma neznamená, že k ní nemá práva konkrétní autor. Než ji případně zveřejníte na svém webu, tak si to prosím ověřte.

Milan Kunz

Teorie grafů

www.palmknihy.cz

© Palmknihy s.r.o. 2000-2013

Teorie grafů Milan Kunz

* * *

* * *

Osobní úvod

* * *

V předešlých statích, kterým Natura poskytla prostor, jsme se zabývali kombinatorikou. Spojil jsem klasickou kombinatoriku s pojmem přirozeného vektorového prostoru, který jsem chtěl definovat v analogii s přirozenými čísly, což je vlastně jednorozměrný přirozený komplex.

* * *

Při brouzdáním Internetem jsem byl přesvědčován, že mezi přirozená čísla rozhodně nepatří nula, což vlastně není žádné číslo. Byl bych ochoten souhlasit s tím, že nula je zástupný symbol za bod, za "nic", či za bezrozměrný simplex.

Kdysi se pro nulu tento symbol"." (bod) opravdu používal.

* * *

Na druhé straně jsem na Internetu našel tabulku rozkladů přirozených čísel, která začínala od nuly jako moje. Takže i v matematice si můžete vybrat, čemu chcete věřit.

* * *

Svoji geometrickou (topologickou) interpretaci kombinatoriky jsem si nechával mnoho let pro sebe, protože nemám formální matematické školení.

To neplatí o následujících statích, týkající se teorie grafů. Zde se mi většinu výsledků podařilo publikovat v prestižních vědeckých časopisech.

* * *

Jako kluk jsem se rozhodl, že se nechci zabývat vědou (konkrétně chemií), protože jsem se mylně domníval, že všechny jednoduché a zajímavé chemické sloučeniny už byly objeveny. Že jsem se pak chemií živil, za to mohla poválečná situace. Chemie, pomineme-li tažení proti vlnové mechanice (a tu jsem nestudoval) byla klidný kout.

* * *

Když jsem byl v rámci normalizace vyhozen z laboratoře, dostal jsem se pomocí dobrých lidí do oddělení informací. Tam jsem se musel nějak zaměstnávat a tak jsem se začal postupně zajímat o teorií grafů. Mimochodem, mojí prvou publikací o grafech jsem zveřejnil v rámci polemiky s mentionovou teorií profesora Kahudy [1].

* * *

Jednu dobu mi tehdy šéfoval zesnulý RNDr Jan Kotas CSc, který mi věnoval úvodní obrázek.

* * *

* * *

Představuje Královec, kde žil a pracoval geniální matematik Euler. Pod jeho úroveň nebyl zdánlivě triviální problém, zda při nedělní procházce Královcem se dá přejít po všech sedmi mostech v Královci jenom jednou a vrátit se do výchozího místa. Pokud byste neměli dost času, abyste obešli prameny řeky, tak to možné není. Euler založil touto studií nový obor, k jehož významnému uplatnění došlo prakticky až v posledním půlstoletí [2].

K rozvoji teorie grafů přispěla i chemie. Vzorce chemických sloučenin mají formu grafů. Existují však mnohem hlubší souvislosti. Jedna Nobelova cena za chemii byla udělena Hueckelovi, který ukázal, že fyzikální vlastnosti konjugovaných molekul (určité uhlovodíky s dvojnými vazbami) odpovídají vlastním hodnotám matic spojitosti grafu molekuly.

To je však problém už dost abstraktní a vyžaduje hlubší znalosti. Mnohem zajímavější je problém Harry Wienera (nepleťte si jej s jeho slavným jmenovcem Norbertem). Ten koreloval body varů alkanů (methan, ethan, propan, atd.) se součty topologických vzdáleností (počty vazeb) mezi uhlíkovými atomy.

To jsou opravdu základní kupecké počty. Nakreslíte si uhlíkovou kostru (to je technický termín, teorie grafů je názorná disciplína, tak zná jako pojmy kostry, stromy, kořeny, kmeny, větve, listy, cesty) a spočítáte počty vazeb mezi všemi páry atomů. Potom je sečtete a výsledné číslo porovnáte s teplotou, při které alkan vře.

Takové počítání je tak elementární, že zcela uspokojilo můj smysl pro jednoduchost. Až do té doby, když jsem dokázal, že Wienerova čísla jsou součty vlastní hodnot jistých inverzních matic dané molekuly [3], případně se objeví i jako vlastní hodnota zobecněné inverzní matice k matici molekuly známé pod jménem Laplace-Kirchhoffova (Laplace ji použil jako prvý pro nebeskou mechaniku, Kirchhoff ji využil k řešení vodivosti elektrických obvodů). Při tomto problému by se měla Laplace- Kirchhoffova matice invertovat.

Incidenční matice a grafy

Posloupnost symbolů, třeba aaba, se dá formálně zapsat jako naivní matice A. Jiná posloupnost symbolů, třeba babb, se dá formálně zapsat jako naivní matice B. Teď se budeme zabývat problémem, jak matici A převést na matici B. Jedna možnost je násobení základní matice A zleva a zprava vhodnými (jednotkovými permutačními) maticemi. To se dá provést jen v případě, že výchozí i konečná matice jsou stejného typu a leží na stejné orbitě. Druhou možností je konstrukce aditivního operátoru S s těmito vlastnostmi: A + S = B Co tento operátor S musí provést? Nejprve musí vynulovat matici A a zapsat na volné místo matici B. V našem příkladu operátor S má tvar S = B - A Když si nakreslíme dva body s koordinátami (1, 0) a (0, 1), pak vektor řádek (-1, 1), bude tento vektor paralelní se spojnicí této dvojice bodů a můžeme si jej představovat a zakreslovat jako vektor směřující přímo z bodu a do bodu b. Při zakreslování vektoru řádku (-1, 1) jde vektor nejprve z bodu a do počátku koordinát a odtud do bodu b. Proto jeho ztotožnění s orientovanou spojnicí bodů, hranou, je zcela oprávněné. Řádky operátoru S (0, 0) představují smyčku vracející původní stav. K operátoru S můžeme zkonstruovat analogicky aditivní operátor G, který má tvar: G = B + A Pro náš příklad operátor G má tvar Po této jednoduché definici incidenčních matic jenom připomeneme, že do našeho grafového prostoru budou patřit i obě kvadratické formy incidenčních matic S a G (STS, SST, GTG a GGT) a také kombinace typu STG a GTS. Pro jednoduchost můžeme nejprve definičně připustit, že se každá hrana může v incidenčních maticích objevit pouze jedenkrát. Tak dostaneme prosté grafy. Opět se budeme zabývat kombinatorickými problémy, jako je počet různých grafů s n vrcholy a m hranami. Tento problém bude jednodušší, když si vrcholy označíme. Neoznačené grafy vytvoří v novém prostoru orbity a jejich počty se musí složitě určovat. Obecně jsou problémy spojené s enumerací grafů mnohem složitější než klasické kombinatorické Úplné grafy K_n mají podobu plošných simplexů. N vrcholů je spojeno hranami se všemi ostatními hranami. Jako kanonický tvar incidenčních matic S_n úplných grafů K_n zvolíme ten, který odpovídá postupnému přidávání vrcholů a hran k menším grafům: Incidenční matice S_n a G_n úplných grafů K_n, které mají n sloupců a n(n-1)/2 řádků, jsou důležité operátory, které zobrazí n(n-1)/2 rozměrnou čtvercovou matici M na čtvercovou matici jen n rozměrnou: STMS nebo GTMG. Každý prvek matice M se objeví v matici STMS nebo GTMG dvakrát. Jednou na diagonále, podruhé jako mimodiagonální prvek, který je kladný u matice GTMG a záporný u matice STMS. Vedle těchto matic je možné grafům přiřadit i tak zvané Petrieho matice, jejichž definice je uvedena v přílohách ([T1],[E1]). Na závěr si dovolím jednu otázku. V Athénách bylo zvykem se při filozofických disputacích procházet. Jak jsem uvedl, základy teorie grafů jsou názorné a elementární. Proč nenapadlo athénské matematiky zabývat se grafy? Co jim chybělo, aby přišli na základy této teorie? Těch sedm mostů z Královce, nebo to bylo něco jiného? Literatura: [1]. Kunz M.: Psychoenergetika nebo psychoenergetismus?, Čas. [2]. Sedláček J.: Úvod do teorie grafů., Academia, Praha, 1981. [3]. M. Kunz: Path and walk matrices of trees, Coll. Czech. Chem. [4]. M. Kunz: A Moebius inversion of the Ulam subgraphs conjecture, J. Math. Chem., 9 (1992) 297-305. [5]. M. Kunz: Inverting Laplace-Kirchhoff matrices from their roots, J. Chem. Inform. Comput. Sci., 1996, 36, 822-824. [6]. M. Kunz: Distance matrices yielding angles between arcs of the graphs, J. Chem. Inform. Comput. Sci., 34, (1994) 957-959.