Galleri med namngivna grafer - Gallery of named graphs

Några av de ändliga strukturerna som beaktas 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å tio hörnpunkter som visas som ett minimalt exempel eller motexempel i många olika sammanhang.

Individuella diagram

Mycket symmetriska grafer

Starkt vanliga diagram

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

Symmetriska grafer

Ett symmetriskt diagram är ett i vilket det finns en symmetri ( grafautorfism ) som tar vilket ordnat par som helst intill varandra till vilket annat ordnat par som helst; de Foster folkräkningen listar alla små symmetriska 3-reguljär graf. Varje starkt regelbunden graf är symmetrisk, men inte tvärtom.

Semisymmetriska grafer

Graffamiljer

Kompletta diagram

Den kompletta grafen på hörn kallas ofta -clique och vanligtvis betecknas från tyska komplett . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle K_ {n}}$

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

Komplett tvåpartsdiagram

Den komplett bipartit graf vanligen betecknas . För se avsnittet om stjärnan grafer. Grafen är lika med 4-cykeln (kvadraten) som presenteras nedan. ${\ displaystyle K_ {n, m}}$ ${\ displaystyle n = 1}$ ${\ displaystyle K_ {2,2}}$ ${\ displaystyle C_ {4}}$

${\ displaystyle K_ {2,3}}$
${\ displaystyle K_ {3,3}}$ , verktygsdiagrammet
${\ displaystyle K_ {2,4}}$
${\ displaystyle K_ {3,4}}$

Cyklar

Den cyklisk graf på vertex kallas n-cykeln och vanligen betecknad . Det kallas också ett cykliskt diagram , en polygon eller n-gon . Särskilda fall är triangeln , kvadraten och sedan flera med grekisk namngivning femkant , hexagon etc. ${\ displaystyle n}$ ${\ displaystyle C_ {n}}$ ${\ displaystyle C_ {3}}$ ${\ displaystyle C_ {4}}$ ${\ displaystyle C_ {5}}$ ${\ displaystyle C_ {6}}$

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

Vänskap diagram

Den väns graf F _n kan konstrueras genom att förena n kopior av cyklisk graf C ₃ med en gemensam spets.

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

Fullerene grafer

I grafteori hänvisar termen fulleren till vilken som helst 3- vanlig , 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 pentagoner i en fulleren och h = V / 2 - 10 sexhörningar. Därför V = 20 + 2 h ; E = 30 + 3 timmar . Fulleren-grafer är Schlegel-representationerna av motsvarande fullerenföreningar.

20-fulleren ( dodekahedral graf)
24-fulleren ( hexagonal trunkerad trapezoederdiagram )
26-fulleren graf
60-fulleren ( trunkerad ikosahedral graf)
70-fulleren

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

Platoniska fasta ämnen

Den kompletta grafen på fyra hörn bildar tetraederns skelett , och mer generellt utgör de fullständiga graferna skelett av enkelheter . De hypercube grafer är också skelett av högre dimensionella regelbundna polytopes .