Regula grafeo
En grafeoteorio, regula grafeo estas grafeo tia, ke ĉiu vertico havas la saman nombron de najbaroj; t.e. ĉiu vertico havas la saman gradon. En direkta grafeo, ĉiu vertico devas havi la saman engradon kaj elgradon.[1] Regula grafeo kun kies verticoj havas gradon k nomiĝas k‑regula grafeo aŭ regula grafeo kun grado k. Parenteze, laŭ la manprema lemo, regula grafeo kun nepara grado havas paran nombron da verticoj.
La artikolo estas parto de serio pri grafeoteorio.
![]() |
Plej gravaj terminoj Elektitaj klasoj de grafeoj Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
Regula grafeo kun grado ĝis 2 estas facile por klasi: 0-regula grafeo estas seneĝa; 1-regula grafeo disajn eĝojn; 2-regula grafeo havas malkoneksa ciklojn kaj malfiniajn ĉenojn.
Plena grafeo estas regulega por
Teoremo de Nash-Williams asertas ke ĉiu k‑regula grafeo kun 2k + 1 verticoj havas Hamiltonian ciklon.
-
0-regula grafeo
-
1-regula grafeo
-
2-regula grafeo
-
3-regula grafeo
Algebra propraĵo redakti
A estu la apudeca matrico de grafeo. Do la grafeo estas regula se kaj nur se estas ajgenvektoro de A.[2] Ĝia ajgenvaloroj estas la konstanta grado de la grafeo. Ajgenvektoroj respektive al aliaj ajgenvaloroj estas orta al , do por tiuj ajgenvektoroj veras .
Generado redakti
Regulan grafeon povas generi la programo GenReg.[3]
Referencoj redakti
- ↑ Graph Theory and Its Engineering Applications. ISBN 978-981-02-1859-1.
- ↑ Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed.
- ↑ Wai-Kai Chen . “Fast Generation of Regular Graphs and Construction of Cages”. doi:[[doi:10.1002%2F%28SICI%291097-0118%28199902%2930%3A2%3C%3E1.0.CO%3B2-G|10.1002/(SICI)1097-0118(199902)30:2<>1.0.CO;2-G]].
Eksteraj ligioj redakti
- GenReg programo farita de Markus Meringer.