Galerie pojmenovaných grafů - Gallery of named graphs
Tato stránka používá mnoho obrázků. Tuto stránku se nedoporučuje zobrazovat lidem s pomalým připojením k internetu. |
Některé z konečných struktur uvažovaných v teorie grafů mít jména, někdy inspirovaná topologií grafu, a někdy po jejich objeviteli. Slavným příkladem je Petersenův graf, konkrétní graf na 10 vrcholech, který se jeví jako minimální příklad nebo protiklad v mnoha různých kontextech.
Jednotlivé grafy
Vysoce symetrické grafy
Silně pravidelné grafy
The silně pravidelný graf na proti vrcholy a pozice k se obvykle označuje srg (v, k, λ, μ).
Paleyův graf objednávky 13
Symetrické grafy
A symetrický graf je symetrie (automatický graf ) převzetí kteréhokoli objednaného páru sousedních vrcholů na jakýkoli jiný objednaný pár; the Podporovat sčítání lidu seznam všech malých symetrických 3 pravidelných grafů. Každý silně pravidelný graf je symetrický, ale ne naopak.
The Rado graf
Polosymetrické grafy
Grafové rodiny
Kompletní grafy
The kompletní graf na vrcholy se často nazývá -klika a obvykle označeny , z němčiny komplett.[1]
Kompletní bipartitní grafy
The kompletní bipartitní graf se obvykle označuje . Pro viz část o hvězdných grafech. Graf se rovná 4-cyklu (čtverec) představený níže.
Cykly
The graf cyklu na vrcholy se nazývá n-cyklus a obvykle označeny . Také se tomu říká a cyklický graf, a polygon nebo n-gon. Zvláštní případy jsou trojúhelník , náměstí , a pak několik s řeckým pojmenováním Pentagon , šestiúhelník , atd.
Grafy přátelství
The graf přátelství Fn lze sestavit spojením n kopie graf cyklu C3 se společným vrcholem.[2]

Fullerenové grafy
V teorii grafů termín fulleren označuje jakoukoli 3-pravidelný, rovinný graf se všemi plochami velikosti 5 nebo 6 (včetně vnější plochy). Vyplývá to z Eulerův mnohostěnný vzorec, PROTI – E + F = 2 (kde PROTI, E, F označte počet vrcholů, hran a ploch), že ve fullerenu je přesně 12 pětiúhelníků a h = PROTI/ 2 - 10 šestiúhelníků. Proto PROTI = 20 + 2h; E = 30 + 3h. Fullerenové grafy jsou Schlegel reprezentace odpovídajících fullerenových sloučenin.
20-fulleren (dodekahedrál graf)
24-fulleren (Šestihranný zkrácený lichoběžník graf)
60-fulleren (zkrácený icosahedral graf)
70-fulleren
Algoritmus pro generování všech neizomorfních fullerenů s daným počtem šestihranných ploch byl vyvinut G. Brinkmannem a A. Dressem.[3] G. Brinkmann také poskytl volně dostupnou implementaci, tzv plný.
Platonické pevné látky
The kompletní graf na čtyřech vrcholech tvoří kostru čtyřstěn a obecněji celé grafy tvoří kostry jednoduchosti. The hyperkrychlové grafy jsou také kostry vyšších dimenzionálních pravidel polytopes.
Zkrácené pevné látky
Snarks
A pusť se je bez můstku kubický graf to vyžaduje čtyři barvy v každém správném zbarvení hran. Nejmenší snark je Petersenův graf, již je uvedeno výše.
Hvězda
A hvězda Sk je kompletní bipartitní graf K.1,k. Hvězda S3 se nazývá drápový graf.

Grafy kol
The graf kola Žn je graf na n vrcholy vytvořené spojením jednoho vrcholu ke každému vrcholu v (n - 1) -cyklus.

Reference
- ^ David Gries a Fred B. Schneider, Logický přístup k diskrétní matematice, Springer, 1993, s. 436.
- ^ Gallian, J. A. „Dynamic Survey DS6: Graph Labeling.“ Electronic Journal of Combinatorics, DS6, 1-58, 3. ledna 2007. [1] Archivováno 2012-01-31 na Wayback Machine.
- ^ Brinkmann, Gunnar; Šaty, Andreas W. M. (1997). "Konstruktivní výčet fullerenů". Journal of Algorithms. 23 (2): 345–358. doi:10.1006 / jagm.1996.0806. PAN 1441972.