Dukolora grafeo

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search
Ekzemplo de duparta grafeo sen ciklo
plena dukolora grafeo kun m = 5 kaj n = 3
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, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn kaj , en kiu ĉiu eĝo ligas verticon en al vertico en . Verticaro kaj ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo.[1][2]

La du partojn , oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en estu bluaj, kaj verticoj en  verdaj. Do la randoj de ĉiu eĝo havas malsamajn kolorojn.[3][4] Kontraste, ĉi tia kolorado ne eblas en ne-dukolora grafeo, ekzemple unu triangulo.

Oni ofte skribas por signifi dukolora grafeo kun partoj kun , kaj signas la eĝaro. Se dukolora grafeo ne estas konekteca, ĝi eble havas plurajn dukoloradojn;[5] tiel,  povas signi unu el la dukoloradoj utila por la nuna problemo. Se , t.e. la du partoj enhavas same da elementoj,  nomiĝas ekvilibra dukolora grafeo.[3] Se ĉiuj verticoj en ambaŭ partoj havas saman gradon nomiĝas duregula.

Referencoj[redakti | redakti fonton]

  1. DIESTEL, Reinard. (2005) Graph Theory, Grad. Texts in Math. Springer. ISBN 978-3-642-14278-9.
  2. Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458 .
  3. 3,0 3,1 Asratian, Denley & Häggkvist (1998), p. 7.
  4. . ISBN 9780840049421.
  5. . ISBN 9781584888000..