Regulær graf av grad 3

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
skf95
Descartes
Descartes
Innlegg: 421
Registrert: 17/12-2010 14:35

Hvis jeg har en regulær graf av grad 3, bestående av [tex]n[/tex] noder, med omkrets [tex]5[/tex]; er da [tex]n[/tex] delelig med [tex]5[/tex]?

Hvis ikke; er [tex]n[/tex] delelig med [tex]5[/tex] hvis grafen består av kun ringer med omkrets [tex]5[/tex], altså kun består av femkanter (slik som petersen-grafen)?

  • Regulær graf; alle nodene er av samme grad
  • Grad; "antall kanter ut fra noden"
  • Omkrets; korteste "ringen" i grafen
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Det fins en 3-regulær graf med 12 noder der den korteste ringen er 5:

http://en.wikipedia.org/wiki/File:Graph ... 034891.jpg

PS: er du sikker på at omkretsen av en graf er definert som den korteste ringen, og ikke den lengste?

På mathworld er de engelske uttrykkene girth (korteste ring) og circumference (lengste ring)

http://mathworld.wolfram.com/Girth.html

http://mathworld.wolfram.com/GraphCircumference.html
Svar