Omkreds (grafteori)

Omkreds i grafteori er længden af den mindste cyklus indeholdt i en given graf [1] . Hvis grafen ikke indeholder cyklusser (det vil sige, det er en acyklisk graf), er dens omkreds per definition lig med uendelig [2] . For eksempel har en 4-cyklus (firkant) omkreds 4. Et kvadratisk gitter har også omkreds 4, og et trekantet gitter har omkreds 3. En graf med omkreds fire eller mere har ingen trekanter .

Celler

Kubiske grafer (alle hjørner har grad tre) med så lidt omkreds som muligt er kendt som -celler (eller som (3, )-celler). Petersen-grafen er den eneste 5-celle (den mindste kubiske graf med omkreds 5), Heawood-grafen er den eneste 6-celle, McGee-grafen er den eneste 7-celle, og Tutt-Coxeter-grafen er den eneste 8- celle [3] . Der kan være flere (graf-)celler for en given omkreds. For eksempel er der tre ikke-isomorfe 10-celler, hver med 70 hjørner - Balaban-10-cellen , Harris-grafen og Harris-Wong-grafen . $g$ $g$ $g$

Petersen-grafen har omkreds 5
Heawood-grafen har omkreds 6
Earl McGee har en omkreds på 7
Tutta-Coxeter grafen ( Tattas 8-celle ) har omkreds 8

Omkreds og farvning af grafen

For ethvert positivt heltal er der en graf med omkreds og kromatisk tal . For eksempel er Grötzsch -grafen en trekantfri graf og har kromatisk nummer 4, og gentagelse af den Myzelskianske konstruktion, der blev brugt til at skabe Grötzsch-grafen mange gange, producerer trekantfrie grafer med vilkårligt store kromatiske tal. Pal Erdős beviste denne sætning ved hjælp af den probabilistiske metode [4] . $k$ $G$ $g(G)\geq k$ $\chi (G)\geq k$

Bevisplan . Vi kalder cyklusser af længde højst korte og mængder med eller flere hjørner store. For at bevise sætningen er det tilstrækkeligt at finde en graf uden korte cyklusser og store uafhængige sæt af toppunkter. Så vil sæt af farver i farvningen ikke være store, og som et resultat vil der være behov for farver til farvning. $k$ $|G|/k$ $G$ $k$

For at finde en sådan graf vil vi fastsætte sandsynligheden for valg lig med . For lille v forekommer kun et lille antal korte cyklusser. Hvis vi nu fjerner et toppunkt fra hver sådan cyklus, vil den resulterende graf ikke have korte cyklusser, og dens uafhængighedstal vil ikke være mindre end grafens [1] . $s$ $n^{\epsilon -1}$ $\epsilon$ $G$ $H$ $G$

Relaterede begreber

Den ulige omkreds og lige omkreds af en graf er længderne af henholdsvis den mindste ulige cyklus og lige cyklus.

Omkredsen af en graf er længden af den længste cyklus, ikke den korteste.

At tænke på længden af den mindste ikke-trivielle cyklus kan ses som en generalisering af 1-systole eller større systole i systolisk geometri .

Noter

↑ 1 2 Reinhard Distel. Grafteori. - Novosibirsk: Matematisk Instituts Publishing House, 2002.
↑ Omkreds -- Wolfram MathWorld.
↑ Andries E. Brouwer. bure. Elektronisk supplement til bogen Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
↑ Paul Erdős. Grafteori og sandsynlighed // Canadian Journal of Mathematics. - 1959. - T. 11 . - S. 34-38 . - doi : 10.4153/CJM-1959-003-9 .