Dukolora grafeo

Ekzemplo de duparta grafeo sen ciklo

plena dukolora grafeo kun m = 5 kaj n = 3

Ŝablono:Grafeoteorio En grafeoteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn $U$ kaj $V$, en kiu ĉiu eĝo ligas verticon en $U$ al vertico en $V$. Verticaro $U$ kaj $V$ ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo.

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

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