For faster navigation, this Iframe is preloading the Wikiwand page for Regula grafeo.

Regula grafeo

El Vikipedio, la libera enciklopedio

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

pli...

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.

  • 0-regula grafeo
    0-regula grafeo
  • 1-regula grafeo
    1-regula grafeo
  • 2-regula grafeo
    2-regula grafeo
  • 3-regula grafeo
    3-regula grafeo

Algebra propraĵo

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

Regulan grafeon povas generi la programo GenReg.[3]

Referencoj

  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

  • GenReg programo farita de Markus Meringer.
{{bottomLinkPreText}} {{bottomLinkText}}
Regula grafeo
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.