![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/langeo-640px-Simple-bipartite-graph.svg.png&w=640&q=50)
Dukolora grafeo
From Wikipedia, the free encyclopedia
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]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/320px-Simple-bipartite-graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Biclique_K_3_5.svg/220px-Biclique_K_3_5.svg.png)
La artikolo estas parto de serio pri grafeoteorio.
![]() |
Plej gravaj terminoj Elektitaj klasoj de grafeoj pli...
Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
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.