Fruchts graf

Frucht-graf

Fruchts graf
Antall hjørner 12
Antall kanter 18
Gradsfordeling 3- vanlig
Stråle 3
Diameter 4
Mesh 3
Automorfismer 1 ({ id })
Kromatisk nummer 3
Kromatisk indeks 3
Eiendommer Kubikk
Hamiltonian
Planar
Asymmetrisk

Den Frucht grafen er, i grafteori , en 3-regulær graf med 12 hjørner og 18 kanter. Det er den minste kubiske grafen hvis automatiseringsgruppe bare inneholder det nøytrale elementet. Det er med andre ord den minste vanlige grafen i grad tre som er en asymmetrisk graf . Det ble først beskrevet i 1939 av Robert Frucht , derav navnet.

Eiendommer

Generelle egenskaper

Frucht-grafen er plan og Hamiltonian . Det er også et tilfelle av Halin-graf .

Den diameteren av den Frucht grafen, er den maksimale eksentrisitet av dens topp-punkt, er 4, dens radius , den minimale eksentrisiteten av dens topp-punkt, er 3 og dens mesh , er lengden av den korteste syklus , er 3. Det er av et 3- toppunkt -tilkoblet graf og en 3 -kantstilkoblet graf , dvs. at den er koblet til, og for å gjøre den frakoblet, må den fratas minst 3 hjørner eller 3 kanter.

Fargelegging

Det kromatiske tallet i Frucht-grafen er 3. Det vil si at det er mulig å fargelegge det med 3 farger slik at to hjørner forbundet med en kant alltid har forskjellige farger, men dette tallet er minimalt. Det er ingen gyldig 2-farging av grafen.

Den kromatiske indeksen til Frucht-grafen er 3. Det er derfor en trefarging av kantene på grafen slik at to kanter som rammer de samme hjørnene alltid har forskjellige farger. Dette tallet er minimalt.

Det er mulig å telle de forskjellige fargene i en graf. Dette gir en funksjon avhengig av antall tillatte farger. Denne funksjonen er polynom og er kvalifisert som kromatisk polynom i grafen. Dette polynom har røtter alle positive heltall eller null strengt mindre enn 3 ° og 12. Det er lik: .

Algebraiske egenskaper

Den automorphism gruppe av Frucht grafen inneholder kun den nøytrale element. Det er derfor i orden 1. Dette gjør Fruchts graf til en asymmetrisk graf .

Den karakteristiske polynom av naboskapsmatrisen av Frucht grafen er: .

Galleri

Se også

Interne lenker

Referanser

  1. (en) Weisstein, Eric W "Frucht Graph." Fra MathWorld - En Wolfram-nettressurs
  2. (i) Skiena S. gjennomførings Diskret matematikk: Kombinatorikk og grafteori med Mathematica. Reading, MA: Addison-Wesley, 1990
  3. (de) "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Komp. Matte. 6, 239-250, 1939