Výčet grafů - Graph enumeration

Kompletní seznam všech volných stromů na 2,3,4 označených vrcholech: ${displaystyle 2 ^ {2-2} = 1}$ strom se 2 vrcholy, ${displaystyle 3 ^ {3-2} = 3}$ stromy se 3 vrcholy a ${displaystyle 4 ^ {4-2} = 16}$ stromy se 4 vrcholy.

v kombinatorika, oblast matematika, výčet grafů popisuje třídu kombinatorický výčet problémy, se kterými se musí počítat neorientovaný nebo řízené grafy určitých typů, obvykle jako funkce počtu vrcholů grafu.^[1] Tyto problémy lze vyřešit buď přesně (jako algebraický výčet problém) nebo asymptoticky Průkopníky v této oblasti matematiky byli George Pólya,^[2] Arthur Cayley ^[3] a J. Howard Redfield.^[4]

Problémy se štítkem a bez štítku

V některých problémech s grafickým výčtem jsou vrcholy grafu považovány za označeno takovým způsobem, aby bylo možné je od sebe odlišit, zatímco u jiných problémů je jakákoli permutace vrcholů považována za stejný graf, takže vrcholy jsou považovány za identické nebo neoznačený. Obecně platí, že označené problémy bývají snazší.^[5] Stejně jako u kombinatorického výčtu obecně platí Věta o výčtu Pólya je důležitým nástrojem pro snížení problémů bez označení na problémy se štítkem: každá třída bez označení je považována za třídu symetrie označených objektů.

Přesné výčetové vzorce

Mezi důležité výsledky v této oblasti patří následující.

• Počet označených n-vertex jednoduché neorientované grafy jsou 2^{n(n − 1)/2}.^[6]
• Počet označených n-vertexové jednoduché směrované grafy jsou 2^n(n − 1).^[7]
• Číslo C_n z připojeno označeno n-vertexové neorientované grafy splňují relace opakování^[8]

${displaystyle C_ {n} = 2 ^ {n vyberte 2} - {frac {1} {n}} součet _ {k = 1} ^ {n-1} k {n vyberte k} 2 ^ {nk vyberte 2} C_ {k}.}$

ze kterého lze snadno vypočítat, pro n = 1, 2, 3, ..., že hodnoty pro C_n jsou

1, 1, 4, 38, 728, 26704, 1866256, ... (sekvence A001187 v OEIS )

• Počet označených n-vrchol volné stromy je n^n − 2 (Cayleyův vzorec ).
• Počet neoznačených n-vrchol housenky je^[9]

${displaystyle 2 ^ {n-4} + 2 ^ {lfloor (n-4) / 2floor}.}$

Databáze grafů

Různé výzkumné skupiny poskytly prohledávatelnou databázi, která uvádí grafy s určitými vlastnostmi malé velikosti. Například

• Dům grafů
• Malá grafická databáze

Reference