Regula grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
La artikolo estas parto de serio pri grafeteorio.




Plej gravaj terminoj
grafeo
arbo
subgrafeo
ciklo
kliko
grado de vertico
grado de grafeo


Elektitaj klasoj de grafeoj
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudividebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa


Grafeaj algoritmoj
A*
Bellman-Ford
Dijkstry
Fleury
Floyd-Warshall
Johnson
Kruskal
Prim
traserĉado de grafeo
en larĝeco
en profundo
plej proksima najbaro


Problemoj prezentataj kiel grafeaj
problemo de vojaĝisto
problemo de ĉina leteristo
problemo de marŝrutigado
problemo de kunigado de geedzoj


Aliaj
kodo de Gray
diagramo de Hasse
kodo de Prüfer


Reprezentado de grafeo Glosaro de grafeteorio


vidi  diskuti  redakti

En grafeteorio, 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.

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[redakti | redakti fonton]

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 | redakti fonton]

Regulan grafeon povas generi la programo GenReg.[3]

Referencoj[redakti | redakti fonton]

  1. Graph Theory and Its Engineering Applications. ISBN 978-981-02-1859-1.
  2. Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed.
  3. 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 | redakti fonton]

  • GenReg programo farita de Markus Meringer.