Galleri med namngivna grafer

Några av de ändliga strukturerna som betraktas i grafteorin har namn, ibland inspirerade av grafens topologi, och ibland efter deras upptäckare. Ett känt exempel är Petersen-grafen , en konkret graf på 10 hörn som framstår som ett minimalt exempel eller motexempel i många olika sammanhang.

Individuella grafer

Mycket symmetriska grafer

Starkt regelbundna grafer

Den starkt regelbundna grafen på v hörn och rang k betecknas vanligtvis srg( v,k ,λ,μ).

Symmetriska grafer

En symmetrisk graf är en där det finns en symmetri ( grafautomorfism ) som tar ett ordnat par av angränsande hörn till vilket annat ordnat par som helst; Foster -folkräkningen listar alla små symmetriska 3-regelbundna grafer. Varje starkt regelbunden graf är symmetrisk, men inte vice versa.

Semi-symmetriska grafer

Graffamiljer

Kompletta grafer

Den fullständiga grafen på $n$ hörn kallas ofta $n$ -klicken och betecknas vanligtvis $K_{n}$ , från tyska komplett .

$K_{1}$
$K_{2}$
$K_{3}$
$K_{4}$
$K_{5}$
$K_{6}$
$K_{7}$
$K_{8}$

Kompletta tvådelade grafer

Den fullständiga tvådelade grafen betecknas vanligtvis $K_{n,m}$ . För $n=1$ se avsnittet om stjärndiagram. Grafen $K_{2,2}$ är lika med 4-cykelns $C_{4}$ (kvadraten) som introduceras nedan.

$K_{2,3}$
$K_{3,3}$ , verktygsgrafen
$K_{2,4}$
$K_{3,4}$

Cyklar

Cykelgrafen på $n$ hörn kallas n-cykeln och betecknas vanligtvis $\displaystyle C_{n}}$ { . Det kallas också en cyklisk graf , en polygon eller n-gon . Specialfall är triangeln $C_{3}$ , kvadraten $C_{4}$ , och sedan flera med grekiska namn femhörningar $\displaystyle C_{5}}$ { , hexagon $C_{6}$ osv.

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

Vänskapsgrafer

Vänskapsgrafen F _n kan konstrueras genom att sammanfoga n kopior av cykelgrafen C ₃ med en gemensam vertex .

Vänskapsgraferna F ₂ , F ₃ och F ₄ .

Fulleren grafer

I grafteorin hänvisar termen fulleren till varje 3- regelbunden , plan graf med alla ytor av storlek 5 eller 6 (inklusive den yttre ytan). Det följer av Eulers polyederformel , V – E + F = 2 (där V , E , F anger antalet hörn, kanter och ytor), att det finns exakt 12 femhörningar i en fulleren och h = V /2 – 10 hexagoner. Därför V = 20 + 2 h ; E = 30 + 3 timmar . Fullerengrafer är Schlegel-representationer av motsvarande fullerenföreningar.

20-fulleren ( dodekaedrisk graf)
24-fulleren ( Hexagonal trunkerad trapezoedergraf )
26-fulleren graf
60-fulleren ( stympad icosahedral graf)
70-fulleren

En algoritm för att generera alla icke-isomorfa fullerener med ett givet antal hexagonala ytor har utvecklats av G. Brinkmann och A. Dress. G. Brinkmann tillhandahöll också en fritt tillgänglig implementering, kallad fullgen .

Platonska fasta ämnen

Den fullständiga grafen på fyra hörn bildar skelett av tetraedern , och mer allmänt bildar de fullständiga graferna skelett av enkla . Hyperkubgraferna är också skelett av högredimensionella vanliga polytoper .