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.
Potíž je v tom, že matice je singulární a tedy neexistuje její normální
inversní protiklad [4, 5]. Za mých mladých let se Kirchhoffovův problém
řešil (a možná stále řeší) rozkladem sítě na stromy. Počty vazeb mezi všemi
páry atomů se dají sestavit do matic vzdáleností. To jsou však vzdálenosti
abstraktní, topologické. Skutečné geometrické vzdálenosti v molekulách
jsou však jiné. Takže se dají vypočítat geometrické analogy Wienerova čísla.
Jenomže matice vzdáleností mají ještě jinou zajímavou vlastnost. Z porovnání
vzdáleností se dá určit úhel mezi hranami [6]. A z této interpretace plyne,
že topologické vzdálenosti jsou čtverci skutečných vzdáleností a grafy
se najednou objeví jako objekty v n-rozměrném prostoru. Tento výsledek
je důkaz správnosti mé koncepce plošných simplexů. V literatuře se vyskytují
názory, že grafy jsou bezrozměrné objekty (abstraktní), či jednorozměrné
objekty. Obecně lze říci, že se nikdo tímto problémem vážně nezabýval.
Grafy se dají barvit, třeba tak, že dva vrcholy spojené hranou nesmí mít
stejnou barvu. Nejmenší počet barev nutných o obarvení grafu jsou dvě.
Grafy, které se dají tímto způsobem obarvit, jsou známy jako dvojdílné.
Mají některé zajímavé vlastnosti.
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
| -1 | 1 |
| 0 | 0 |
| 0 | 0 |
| 1 | -1 |
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. V teorii grafů se někdy tyto operátory připouštějí a značí se kruhovou šipkou. Jindy jsou definičně vyloučeny.
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
| 1 | 1 |
| 2 | 0 |
| 0 | 2 |
| 1 | 1 |
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:
| S_{n-1} | 0 |
| I_{n-1} | J |
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. Lék. čes., 118, 1979, 1592-1955.
[2]. Sedláček J.: Úvod do teorie grafů., Academia, Praha, 1981.
[3]. M. Kunz: Path and walk matrices of trees, Coll. Czech. Chem. Commun., 54 (1989) 2148- 2155.
[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.
časopis o přírodě, vědě a civilizaci