Dukolora grafeo
La artikolo estas parto de serio pri grafeoteorio.
|
Plej gravaj terminoj Elektitaj klasoj de grafeoj Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
En grafeoteorio, 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]- ↑ Diestel, Reinard. (2005) Graph Theory, Grad. Texts in Math. Springer. ISBN 978-3-642-14278-9.
- ↑ 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,0 3,1 Asratian, Denley & Häggkvist (1998), p. 7.
- ↑ . ISBN 9780840049421.
- ↑ . ISBN 9781584888000..