I grafteori , en gren av matematikk , er en kubisk graf en vanlig graf av grad 3. Med andre ord er det en graf der det er nøyaktig tre innfallende kanter ved hvert toppunkt.
En konsekvens av håndtrykk-lemmaet er at hver kubikkgraf har et jevnt antall hjørner.
I følge Brooks 'teorem kan hjørnene i en kubisk graf bli farget med tre farger (eller mindre) slik at to tilstøtende hjørner ikke er av samme farge, bortsett fra i tilfellet med tetraedrisk graf .
En bikubisk graf er en vanlig tosidig graf av grad 3, det vil si en kubisk graf hvis hjørner kan farges med bare to farger.
Den komplette grafen er den eneste kubiske grafen som krever 4 farger
Farging av Frucht-grafen med 3 farger
er en bikubisk graf, to farger er nok
Kantene på Petersen-grafen, en snark, trenger 4 farger
I følge Vizings teorem kan kanter på en kubisk graf bli farget med 3 eller 4 farger uten at to kanter av samme farge faller inn i samme toppunkt. De snarks er relatert kubikk grafer uten eidet som trenger 4 farger.
Den Petersen teorem sier at noen kubikk graf uten eidet har en perfekt matching .
Med andre ord, hvis en kant i en kubisk graf tilhører en syklus, så eksisterer det et sett med kanter som er innfallende i alle toppunktene, idet hvert toppunkt bare er enden på en av disse kantene.
Denne setningen, en av de eldste innen grafteori, siden i 1891, blir sett på i dag som en anvendelse av Tuttes teorem (i) .
Et eksempel på perfekt samsvar i en ikke-kubisk graf
De røde kantene danner en perfekt kobling av Petersen-grafen.
Teoremet er generalisert: en formodning, formulert av Michael D. Plummer og László Lovász, sier at enhver kubikkgraf uten isthmus har et eksponentielt antall perfekte koblinger . Denne antagelsen ble demonstrert av Esperet, Kardoš, King og Kráľ i 2011.
I en Hamilton-graf kan vi gå gjennom alle toppunktene en gang og bare en gang.
De fleste kubiske grafer er Hamiltonere, men ikke alle: sannsynligheten for å være Hamilton har en tendens til 1 når antall hjørner øker på ubestemt tid.
Kubiske grafer kan til og med være polyhedrale , kubiske og ikke-Hamiltoniske på samme tid , som grafen til Tutte viser . De kan også være både bikubiske og ikke-Hamiltonian, som vist i Horton-grafen eller Ellingham-Horton 54-grafen . Den formodning Barnette (i) , fortsatt uprøvd og ikke ugyldiggjort i dag sier at hver graf både bikubisk polyhedrale og ville Hamilton.
Når en kubikkdiagram er Hamiltonian, tillater LCF-notasjon den å bli representert kortfattet.
En Hamilton-syklus i dodekahedralgrafen
Den Bidiakis kube , representert slik som å markere at det er polyhedrale
Bidiakis-terningen, ordnet annerledes: sirkelen fremhever en Hamilton-syklus