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. 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.

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.

 Algebra propraĵo 
A estu la apudeca matrico de grafeo. Do la grafeo estas regula se kaj nur se   estas ajgenvektoro de A.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed.  Ĝia ajgenvaloroj estas la konstanta grado de la grafeo. Ajgenvektoroj respektive al aliaj ajgenvaloroj estas orta al , do por tiuj ajgenvektoroj  veras .

 Generado 
Regulan grafeon povas generi la programo GenReg. 

 Referencoj 

 Eksteraj ligioj 
 GenReg programo farita de Markus Meringer.

Kategorio:Grafeteorio