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čilnostiUredi
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 je krepkoregularen za vsak .
Nash-Williamsov izrek pravi, da ima vsak k-regularni graf na točkah Hamiltonov cikel.
3-regularni graf (kubični graf)
Polni graf K5
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.
Pogoja za obstojUredi
Dobro je znano, da sta potrebna in zadostna pogoja za obstoj -regularnega grafa reda , da velja in, da je produkt sod. Tedaj je lahko skonstruirati regularne grafe z upoštevanjem ustreznih parametrov cirkulantnih grafov.
Algebrske značilnostiUredi
Naj je A matrika sosednosti grafa. Potem je graf regularen, če in samo če je lastni vektor A.[2] Njegova [flastna vrednost]] bo konstantna stopnja grafa. Lastni vektorji, ki odgovarjajo drugim lastnim vrednostim, so pravokotni na , tako da za vsak tak lastni vektor velja .
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 , 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 . Če G ni dvodelen, velja:
Število neizomorfnih regularnih grafovUredi
Š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 grafovUredi
Regularni grafi se lahko ustvarjajo s programom GenReg.[5]
Glej tudiUredi
SkliciUredi
- ↑ Chen (1997), str. 29.
- ↑ 2,0 2,1 Cvetković; Doob; Sachs (1998).
- ↑ Curtin (2005).
- ↑ Quenell (1992).
- ↑ Meringer (1999).
ViriUredi
- Chen, Wai-Kai (1997), Graph Theory and its Engineering Applications, World Scientific, ISBN 978-981-02-1859-1
- Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2–3): 241–248, doi:10.1007/s10623-004-4857-4, MR 2128333
- Cvetković, Dragoš M.; Doob, M.; Sachs, H. (1998), Spectra of Graphs: Theory and Applications (3. rd rev. enl. izd.), New York: Wiley
- Meringer, Markus (1999), "Fast generation of regular graphs and construction of cages" (PDF), Journal of Graph Theory, 30 (2): 137–146, doi:10.1002/(SICI)1097-0118(199902)30:2<>1.0.CO;2-G
- Quenell, Gregory (1992), Spectral diameter estimates for k-regular graphs (PDF) (angleščina), arhivirano iz prvotnega spletišča (PDF) dne 2014-01-06, pridobljeno dne 2016-06-29
Zunanje povezaveUredi
- Weisstein, Eric W. "Regular Graph". MathWorld.
- Weisstein, Eric W. "Strongly Regular Graph". MathWorld.
- GenReg – program in podatki, Meringer, Markus (angleško)
- Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report (angleščina), Waterloo, Ontario: University of Waterloo