Enumerace je ošklivé slovo pro zajímavý problém počítání různých objektů, samozřejmě i grafů. V tomto případě znamená počítání všech různých možností existence grafů různě definovaných. Je to poměrně mladý obor teorie grafů [1] a podnětem pro jeho rozvoj byly z počátku praktické problémy chemie.

Existují různé chemické sloučeniny se stejným zastoupením základních atomů a stejným souhrnným vzorcem, které se liší svou strukturou, tedy tím, jak jsou atomy v molekule uspořádány. Takovým sloučeninám se říká isomery. Určitou výhodou při hledání počtů isomerů, jak se takovým sloučeninám říká, je omezení vaznosti atomů, které isomerní sloučeniny tvoří, nejčastěji na čtyři vazby u sloučenin uhlíku, kde je tento problém nejčastější. Toto omezení však na druhé straně může komplikovat nalezené matematické vztahy, místo obecně platných vzorců je třeba hledat specifické tvary.

Počty isomerů se nejprve zjišťovaly jednoduchým postupem, badatel si kreslil všechny možnosti, jak kombinovat atomy, a po nalezení všech isomerů pro počátky různých řad se pokoušel nalézt pravidelnosti v rozvoji řad a potom je dokázat. Tento postup je stále aktuální, jen se do podobného hledání zapojují počítače.

Podobně jako v klasické kombinatorice, existují při počítání počtů grafů různé možnosti, jaké prvky grafu budeme považovat za rozlišitelné či shodné.

Základem jsou počty různých grafů, u nichž ani vrcholy, ani hrany nejsou nijak označeny. Tyto počty odpovídají orbitám v přirozeném vektorovém prostoru, rozkladům čísla m na n sčítanců. Číslo n je počet vrcholů grafu. Číslo m představuje počet hran nebo jinak chemických vazeb. Vzhledem k tomu, že u každého vrcholu počítáme většinou všechny incidentní hrany, počítá se každá hrana dvakrát a proto číslo m je v tomto případě dvojnásobek skutečného počtu hran. U orientovaných grafů se můžeme zajímat zvláště o počty orientovaných hran vcházejících a vycházejících z jednotlivých vrcholů. Takovým grafům se říká turnaje, protože znázorňují vztahy mezi účastníky turnajů.

Součet počtu incidentní hran u jednotlivých vrcholů je vždy sudé číslo. Na jednom rozkladu může být umístěno více různých grafů. Tak třeba rozklad (2, 2, 2, 2, 2, 2) může znamenat jeden cykl délky 6, nebo dva cykly délky 3, pokud uvažujeme jen prosté grafy (s jednoduchými vazbami).

Další možnosti počítání různých kombinací jsou grafy, u nichž jsou označeny buď vrcholy nebo hrany, nebo oba prvky. Při tom označení může být úplné, ke každému prvku se přiřadí zvláštní symbol, nebo částečné, kdy vždy několik prvků má stejné označení (různé chemické prvky).

Pro částečné značení se někdy užívá pojem barvení grafu. Tak třeba se můžeme pokusit označit vrcholy grafu dvěma (případně třemi a více) barvami takovým způsobem, aby nikdy dva vrcholy se stejnou barvou neměly společnou hranu, jinak řečeno, aby spolu nesousedily. Pokud se nějaký graf podaří takto označit, říká se mu potom dvojdílný (trojdílný atd.). Takové grafy mají určité specifické vlastnosti.

Problém značení hran barvami je znám také jako problém map, protože u rovinného grafu udává nejmenší počet potřebných barev pro vybarvení grafu, aby se nikdy nesetkaly dvě různá území se stejnou barvou.

Některé příklady

Nejjednodušším případem enumerace grafů je nalezení počtu prostých grafů s indexovanými vrcholy. V tom případě jsou všechny hrany rozlišitelné a stačí jen hledat možnosti, kolika způsoby lze vybrat k objektů (hran) z n(n - 1)/2 objektů. Tyto možnosti jsou dány binomickými koeficienty (viz [1], [2]) takže počty všech takto označených grafů jsou mocniny čísla 2.

Dalším jednoduchým případem je enumerace stromů s indexovanými vrcholy. Strom s n vrcholy má (n-1) hran.

Důkaz našel Prüfer. Stromy se algoritmicky osekají na základní větev se dvěma vrcholy a postup osekávání určuje označení stromu: Každý strom má alespoň dva listy, což jsou vrcholy s hodnotou 1. Vybere se list s nejnižším indexem, odsekne se a poznamená se index vrcholu, ke kterému byl odseknutý list připojen. Tak se postupuje k posledním dvěma vrcholům. Dostanou se všechny posloupnosti n symbolů délky (n-2).

Příklady: Hvězda S(5) s kořenem 3 dá posloupnost 3,3,3. Lineární řetězec L(5) 1-5-4-3-2 dá posloupnost 5, 3, 4, protože nejprve odsekneme vrchol 1 připojený k vrcholu 5, potom vrchol 2 připojený k vrcholu 3 a nakonec vrchol 3 připojený k vrcholu 4. Řetězec 2-1-4-3-5 dát podobně posloupnost 1, 4, 3.

Stromy můžeme také spočítat podobně jako naivní matice, když vezmeme v úvahu, že počet hran u všech vrcholů je (2n-2), přičemž n jednotek je vázáno podmínkou vaznosti stromu, takže jen (n-2) jednotek je volných pro rozdělování. Zde je nevýhodou, že na jednotlivých orbitách se počítají různé stromy.

Zde pro zajímavost můžeme zmínit obrácený postup, že se naivní matice N mohou rozšířit na incidenční matice grafu G nebo S, tím, že k naivní matici N přidáme jako blok jednotkovou diagonální matici I. Takové incidenční matice jsou matice hvězdných lesů, kde kořeny jednotlivých stromů jsou představované n symboly a jednotlivé výskyty symbolů jsou listy stromu [2].

Pokud se budeme zabývat enumerací grafů hlouběji, pak můžeme vycházet ze základního schématu, které jsme použili u naivních matic. Matice se násobí zprava i zleva jednotkovými permutačními maticemi potřebného rozměru (n zprava a m zleva) představujícími symetrické grupy S(n) a S(m). Postačí násobení jen představiteli jednotlivých podgrup. Pokud hrany nejsou označeny, násobení grupou S(m) je nadbytečné a postačuje jen násobení grupou S(n).

Po provedení všech násobení se najdou počty rozlišitelných výsledků. Tento počet ukazuje symetrii daného grafu představovaného maticí sousedství grafu G (neorientovaný graf) a S (orientovaný graf). V obou maticích jsou v každém řádku dva jednotkové prvky, u orientovaného grafu jeden z nich má kladné a druhý záporné znaménko. Vzhledem k tomu nejsou výsledky násobení zcela nezávislé, ale jedná se o spletenec grup symetrie.

Nebo se problém pokusíme vysvětlit jinak. Permutace n sloupců působí na hrany grafu, což je až n(n-1)/2 prvků. Délka cyklu však nemůže být větší než n. To vede k tomu, že symetrie grafu je omezená jen na některé prvky grupy S(n(n-1)/2). Nesmí obsahovat cykly delší než s n prvky a také cykly s délkou, která není dělitelem n.

Výsledky násobení lze předvídat, protože byla odhalena pravidla určující výsledky násobení. Zasloužili se o to v třicátých letech dva matematici, Polya [3] a Redfield [4]. Redfield měl smůlu. Jeho prvá práce zcela zapadla, druhou se mu vůbec nepodařilo uveřejnit. Redfieldovy články byly znovu objeveny a jejich význam oceněn až po padesáti letech.

Odhalení těchto vztahů umožnilo použít pro enumeraci grafů podobné vztahy jako pro enumeraci prvků grupy.

Dosazení do těchto vztahů opět není zcela jednoduché (viz přílohy TEX a ESO [T1], [E1]), ale dává po vyčíslení požadované počty neznačených grafů.

Literatura:

[1] F. Harary, E. M. Palmer, Graphical Enumeration, Academic Press, New York, 1973.

[2] M. Kunz: Entropies and information indices of star forests, Coll. Czech. Chem. Commun., 51 (1986) 1856-1863.

[3] F. Harary, E. M. Palmer, R. W. Robinson, R.C. Read: Polya's contribution to chemical enumeration. V. Balaban AT (Ed.) Chemical applications of graph theory, Academic Press, New York, str. 1211.

[4] E. K. Lloyd, Redfield's papers and their relevance to counting isomers and isomerisation, Discrete Appl. Math., 19 (1988) 289-304.

časopis o přírodě, vědě a civilizaci