Loading AI tools
Från Wikipedia, den fria encyklopedin
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.[1] 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 Km ä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.[2]
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.
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.[3] Dess egenvärde är grafens konstanta grad. Egenvektorer som motsvarar andra egenvärden är ortogonala mot j så för sådana egenvektorer v=(v1,...,vn) har vi .
En reguljär graf av grad k är sammanhängande om och endast om egenvärdet k har multipliciteten ett.[3] Det finns också ett villkor för reguljära sammanhängande grafer: En graf är sammanhängande om och endast om ettmatrisen J, med Jij = 1, finns i grafens "sidoalgebra" (det vill säga att den är en linjärkombination av potenser av A)[4]
Låt G vara en k-reguljär graf med diametern D och med grannmatrisens egenvärden . Om G inte är bipartit så
där .[5]
Reguljära grafer kan tillverkas med hjälp av programmet GenReg.[6]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.