Reguljär graf

Inom grafteori är en reguljär graf en graf i vilken alla noder har samma grad eller valens. En reguljär riktad graf måste dessutom uppfylla kravet att ingraden är lika med utgraden. En reguljär graf med noder av graden k kallas en k-reguljär graf (eller helt enkelt en reguljär graf av grad k).

De reguljära graferna med en grad upp till och med två är enkla att klassificera. En 0-reguljär graf består av fria noder, en 1-reguljär graf består av fria kanter och en 2-reguljär graf består av fria cykler och oändliga kedjor.

En 3-reguljär graf kallas kubisk graf

En "starkt reguljär graf" är en reguljär graf i vilken alla par av intilliggande noder har samma antal grann-noder gemensamma och varje par av icke intilligande noder har samma antal gemensamma grann-noder. De minsta graferna som är reguljära men inte starkt reguljära är de cykliska och cirkulanta graferna över sex noder. Den kompletta grafen K_m är starkt reguljär för alla m.

En sats av Crispin Nash-Williams säger att varje k-reguljär graf över 2k + 1 noder har en Hamiltoncykel.

• 
  0-reguljär graf
• 
  1-reguljär graf
• 
  2-reguljär graf
• 
  3-reguljär graf

Existens

Det är välkänt att de nödvändiga och tillräckliga förutsättningarna för att en k-reguljär graf av ordning n skall finnas är att n ≥ k + 1 och att produkten nk är jämn. I sådana fall är det lätt att konstruera reguljära grafer genom att beakta lämpliga parametrar för cirkulanta grafer.

Algebraiska egenskaper

Låt A vara grannmatrisen till en graf. Då är grafen reguljär om och endast om j=(1,1,...,1) är en egenvektor till A. Dess egenvärde är grafens konstanta grad. Egenvektorer som motsvarar andra egenvärden är ortogonala mot j så för sådana egenvektorer v=(v₁,...,v_n) har vi $\sum _{i=1}^{n}v_{i}=0$.

En reguljär graf av grad k är sammanhängande om och endast om egenvärdet k har multipliciteten ett. Det finns också ett villkor för reguljära sammanhängande grafer: En graf är sammanhängande om och endast om ettmatrisen J, med J_ij = 1, finns i grafens "sidoalgebra" (det vill säga att den är en linjärkombination av potenser av A)

Låt G vara en k-reguljär graf med diametern D och med grannmatrisens egenvärden $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{n-1}$. Om G inte är bipartit så

$D\leq {\frac {\log {(n-1)}}{\log(k/\lambda )}}+1$

där $\lambda =\max _{i>0}\{\mid \lambda _{i}\mid \}$.

Generation

Reguljära grafer kan tillverkas med hjälp av programmet GenReg.

Externa länkar

• Wikimedia Commons har media som rör Reguljär graf.
  Bilder & media
• Weisstein, Eric W., "Regular Graph", MathWorld. (engelska)
• Weisstein, Eric W., "Strongly Regular Graph", MathWorld. (engelska)
• GenReg, mjukvara och data av Markus Meringer.
• Nash-Williams, Crispin (1969). ”Valency Sequences which force graphs to have Hamiltonian Circuits”. University of Waterloo Research Report. Waterloo, Ontario: University of Waterloo