Regula grafeo

Ŝablono:Grafeoteorio 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 $K_m$ estas regulega por $m$

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

A estu la apudeca matrico de grafeo. Do la grafeo estas regula se kaj nur se  $\mathbf{\text{j}}=(1,\dots ,1)$ estas ajgenvektoro de A. Ĝia ajgenvaloroj estas la konstanta grado de la grafeo. Ajgenvektoroj respektive al aliaj ajgenvaloroj estas orta al $\mathbf{\text{j}}$, do por tiuj ajgenvektoroj $v=(v_1,\dots ,v_n)$ veras $\sum _{i=1}^n{v}_i=0$.

Generado

Regulan grafeon povas generi la programo GenReg.

Eksteraj ligioj

• GenReg programo farita de Markus Meringer.