Dukolora grafeo

En grafeoteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn ${\displaystyle U}$ kaj ${\displaystyle V}$, en kiu ĉiu eĝo ligas verticon en ${\displaystyle U}$ al vertico en ${\displaystyle V}$. Verticaro ${\displaystyle U}$ kaj ${\displaystyle V}$ ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo.^[1][2]

La artikolo estas parto de serio pri grafeoteorio.

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 grafeoGlosaro de grafeoteorio

vidi • diskuti • redakti

La du partojn ${\displaystyle U}$, ${\displaystyle V}$ oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en ${\displaystyle U}$ estu bluaj, kaj verticoj en ${\displaystyle V}$ 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 ${\displaystyle G=(U,V,E)}$ por signifi dukolora grafeo kun partoj ${\displaystyle U}$ kun ${\displaystyle V}$, kaj ${\displaystyle E}$ signas la eĝaro. Se dukolora grafeo ne estas konekteca, ĝi eble havas plurajn dukoloradojn;^[5] tiel,  ${\displaystyle (U,V,E)}$ povas signi unu el la dukoloradoj utila por la nuna problemo. Se ${\displaystyle |U|=|V|}$, t.e. la du partoj enhavas same da elementoj, ${\displaystyle G}$ nomiĝas ekvilibra dukolora grafeo.^[3] Se ĉiuj verticoj en ambaŭ partoj havas saman gradon, ${\displaystyle G}$ nomiĝas duregula.