Regularny wykres

Rodziny grafów zdefiniowane przez ich automorfizmy
przechodnie na odległość	→	odległość regularna	←	mocno regularny
↓
symetryczny (przechodni łuku)	←	t -przechodnia, t ≥ 2		skośno-symetryczny
↓
(jeśli jest połączony) wierzchołki i krawędzie przechodnie	→	przechodnie krawędziowe i regularne	→	przechodnie krawędziowe
↓		↓		↓
przechodnie wierzchołków	→	regularny	→	(jeśli dwustronny) dwuregularny
↑
Wykres Cayleya	←	zero-symetryczny		asymetryczny

W teorii grafów graf regularny to graf , w którym każdy wierzchołek ma taką samą liczbę sąsiadów; tj. każdy wierzchołek ma ten sam stopień lub wartościowość. Regularny graf skierowany musi również spełniać silniejszy warunek, że stopień wejściowy i zewnętrzny każdego wierzchołka wewnętrznego są sobie równe. Graf regularny o wierzchołkach stopnia k nazywamy grafem k ‑regularnym lub grafem regularnym stopnia k . Ponadto z lematu o uzgadnianiu wynika , że ​​graf regularny zawiera parzystą liczbę wierzchołków o nieparzystym stopniu.

Grafy regularne stopnia co najwyżej 2 są łatwe do sklasyfikowania: graf 0-regularny składa się z rozłączonych wierzchołków, graf 1-regularny składa się z niepołączonych krawędzi, a graf 2-regularny składa się z rozłącznej sumy cykli i nieskończonych łańcuchów.

Graf 3-regularny jest znany jako graf sześcienny .

Graf silnie regularny to graf regularny, w którym każda sąsiednia para wierzchołków ma taką samą liczbę wspólnych sąsiadów l , a każda niesąsiadująca para wierzchołków ma taką samą liczbę wspólnych sąsiadów n . Najmniejsze grafy, które są regularne, ale niezbyt regularne, to wykres cyklu i wykres cyrkulacyjny na 6 wierzchołkach.

Pełny wykres K _m jest silnie regularny dla dowolnego m .

Twierdzenie Nasha-Williamsa mówi, że każdy k graf regularny na 2 k + 1 wierzchołkach ma cykl Hamiltona .

• 

  0-regularny wykres

• 

  1-regularny wykres

• 

  2-regularny wykres

• 

  3-regularny wykres

Istnienie

Powszechnie wiadomo, że warunkiem koniecznym i wystarczającym istnienia regularnego wykresu rzędu jest to $,$$n \ geq k + 1}$$Displaystyle$ że ${\ displaystyle nk}$ jest parzysta.

Dowód: Jak wiemy, pełny graf ma każdą parę odrębnych wierzchołków połączonych ze sobą unikalną krawędzią. Więc krawędzie są maksymalne na pełnym wykresie, a liczba krawędzi wynosi ${\ Displaystyle {\ binom {n} {2}} = {\ dfrac {n (n-1)}} 2}}}$ , a stopień tutaj wynosi ${\ displaystyle n-1}$ . Więc ${\ displaystyle k = n-1, n = k + 1}$ . Jest to minimum $}$ konkretnego . ${\ displaystyle k$ . Zauważ też $musi$ że jeśli jakikolwiek regularny wykres ma rząd $to$ liczba krawędzi jest więc ${\ displaystyle nk}$ być parzysta. W takim przypadku łatwo jest skonstruować grafy regularne biorąc pod uwagę odpowiednie parametry grafów cyrkulacyjnych .

Właściwości algebraiczne

Niech A będzie macierzą sąsiedztwa grafu. Wtedy wykres $_$ regularny i tylko wtedy _ Jego wartością własną będzie stały stopień wykresu. Wektory własne odpowiadające innym wartościom własnym $są$ do , więc dla takich wektorów własnych ${\ Displaystyle v = (v_ {1}, \ kropki, v_ {n})}$ mamy ${\ Displaystyle \ suma _ {i = 1} ^{n}v_{i}=0}$ .

Regularny wykres stopnia k jest spójny wtedy i tylko wtedy, gdy wartość własna k ma krotność jeden. Kierunek „tylko jeśli” jest konsekwencją twierdzenia Perrona – Frobeniusa .

Istnieje również kryterium dla grafów regularnych i spójnych: wykres jest spójny i regularny wtedy i tylko wtedy, gdy macierz $1}$ = 1 { \ displaystyle J_ wykres (czyli jest to liniowa kombinacja potęg A ).

Niech G będzie k -regularnym wykresem o średnicy D i wartościach własnych macierzy sąsiedztwa ${\ Displaystyle k = \ lambda _ {0}> \ lambda _ {1} \ geq \ cdots \geq \lambda _{n-1}}$ . Jeśli G nie jest dwudzielny, to

${\ Displaystyle D \ równoważnik {\ Frac {\ log {(n-1)}} {\ log (\ lambda _ {0} /\lambda_{1})}}+1.}$

Pokolenie

Istnieją szybkie algorytmy do wyliczania, aż do izomorfizmu, wszystkich grafów regularnych o danym stopniu i liczbie wierzchołków.

Zobacz też

• Losowy regularny wykres
• Mocno regularny wykres
• Wykres Moore'a
• Wykres klatki
• Wysoce nieregularny wykres

Linki zewnętrzne

• Weisstein, Eric W. „Wykres regularny” . MathWorld .
• Weisstein, Eric W. „Wykres silnie regularny” . MathWorld .
• GenReg autorstwa Markusa Meringera.
• Nash-Williams, Crispin (1969), Sekwencje walencyjne, które wymuszają na grafach posiadanie obwodów hamiltonowskich , University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo