Regularni graf

Regularni graf je v teoriji grafov graf brez zank in večkratnih povezav v katerem ima vsaka točka enako število sosednjih točk, oziroma vsaka točka ima enako stopnjo ali valenco. Za regularni usmerjeni graf mora veljati tudi strožji pogoj, da je stopnja vstopajočih povezav enaka stopnji odtekajočih povezav.^[1] Regularni graf s točkami stopnje k se imenuje regularni graf stopnje k ali k-regularni graf.

Osnovne značilnosti

Regularne grafe stopnje vsaj 2 je lahko razvrstiti: 0-regularni graf vsebuje nepovezane točke, 1-regularni graf vsebuje nepovezane povezave, 2-regularni graf pa vsebuje nepovezane cikle.

3-regularni graf je znan kot kubični graf, 4-regularni graf pa kot kvartični graf.

Krepkoregularni graf je regularni graf kjer ima vsak sosednji par točk enako število skupnih sosednjih točk l, in vsak nesosednji par točk enako število skupnih sosednjih točk n. Najmanjša grafa, ki sta regularna, ne pa tudi krepkoregularna, sta cikel in cirkulantni graf na 6-tih točkah.

Polni graf ${\displaystyle K_{m}}$ je krepkoregularen za vsak ${\displaystyle m}$.

Nash-Williamsov izrek pravi, da ima vsak k-regularni graf na ${\displaystyle 2k+1}$ točkah Hamiltonov cikel.

• 
  0-regularni graf
• 
  1-regularni graf
• 
  2-regularni graf
• 
  3-regularni graf (kubični graf)

• 
  Polni graf K₅
  graf 5-celice, najmanjši možni 4-regularni graf (kvartični graf)
• 
  Oktaedrski graf
  (graf trikotniške antiprizme). Edini kvartični graf na 6-ih točkah.
• 
  Cirkulantni graf ${\displaystyle C_{7}(1,2)\,}$
• 
  Cirkulantni graf ${\displaystyle C_{7}(1,3)\,}$
• 
  Kvartični graf na 7-ih točkah

Pogoja za obstoj

Dobro je znano, da sta potrebna in zadostna pogoja za obstoj ${\displaystyle k}$-regularnega grafa reda ${\displaystyle n}$, da velja ${\displaystyle n\geq k+1}$ in, da je produkt ${\displaystyle nk}$ sod. Tedaj je lahko skonstruirati regularne grafe z upoštevanjem ustreznih parametrov cirkulantnih grafov.

Algebrske značilnosti

Naj je A matrika sosednosti grafa. Potem je graf regularen, če in samo če je ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ lastni vektor A.^[2] Njegova [flastna vrednost]] bo konstantna stopnja grafa. Lastni vektorji, ki odgovarjajo drugim lastnim vrednostim, so pravokotni na ${\displaystyle {\textbf {j}}}$, tako da za vsak tak lastni vektor ${\displaystyle v=(v_{1},\dots ,v_{n})}$ velja ${\displaystyle \sum _{i=1}^{n}v_{i}=0}$.

Regularni graf stopnje k je povezan, če in samo če ima lastna vrednost k multiplikativnost ena. Pogoj je posledica Perron-Frobeniusovega izreka.^[2]

Obstaja tudi kriterij za regularne in povezane grafe: graf je povezan in regularen, če in samo če je matrika enic J, kjer je ${\displaystyle J_{ij}=1}$, algebra sosednosti grafa, kar pomeni, da je linearna kombinacija potenc A.^[3]

Naj je G k-regularni graf s premerom D in lastnimi vrednostmi matrike sosednosti ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}}$. Če G ni dvodelen, velja:

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$^[4]

Število neizomorfnih regularnih grafov

Število možnih neizomorfnih povezanih k-regularnih grafov na n točkah podaja naslednja razpredelnica:

n	3	4	5	6	7	8	9	10	11	12
	A002851	A006820	A006821	A006822	A014377	A014378	A014381	A014382	A014384
0	1	1	1	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0
4	1	0	0	0	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0	0	0
6	2	1	1	0	0	0	0	0	0	0
7	0	2	0	1	0	0	0	0	0	0
8	5	6	3	1	1	0	0	0	0	0
9	0	16	0	4	0	1	0	0	0	0
10	19	59	60	21	5	1	1	0	0	0
11	0	265	0	266	0	6	0	1	0	0
12	85	1544	7848	7849	1547	94	9	1	1	0
13	0	10778	0	367860	0	10786	0	10	0	1
14	509	88168	3459383	21609300	21609301	3459386	88193	540	13	1
15	0	805491	0	1470293675	0	1470293676	0	805579	0	17
16	4060	8037418	2585136675	113314233808	733351105934	733351105935	113314233813	2585136741	8037796	4207
17	0	86221634	0	9799685588936	0		0	9799685588961	0	86223660
18	41301	985870522	2807105250897
19	0	11946487647	0		0		0		0
20	5104891	152808063181
21	0	2056692014474	0		0		0		0
22	7319447	28566273166527

Ustvarjanje regularnih grafov

Regularni grafi se lahko ustvarjajo s programom GenReg.^[5]

Glej tudi

• naključni regularni graf
• krepkoregularni graf
• Mooreov graf
• kletka
• visokoiregularni graf
• kubični graf
• kvartični graf
• kvintični graf