Ideja za algoritem

pietro je 1. nov 2011 ob 23:31 izjavil:

stevilo tock z doloceno barvo je natancno doloceno (tocno 8 tock mora biti rumenih, tocno 7 zelenih itd.),

Ne dvomim, da je kakšen boljši postopek, ampak jaz bi na prvo žogo samo "požrešno" barval, pri čemer bi pazil na to, da se barva "prelije" prej v točke z manjšo stopnjo (oz. bi po možnosti začel tudi s posameznim barvanjem v točki stopnje 1). Določena hevristika je lahko to, kako velike podgrafe imaš (hitro lahko ugotoviš, če problem ni rešljiv pa npr. na podgrafu s 7 točkami sploh ne poskušiš barvati z rumeno).

pietro je 1. nov 2011 ob 23:31 izjavil:

barvni pod-grafi sestavljajo nov graf z B tockami in V povezavami (kar pomeni, da ce obstaja povezava "v" med rumeno in zeleno tocko v tem novem grafu, mora vsaj ena rumena tocka iz prvotnega grafa biti soseda vsaj eni zeleni tocki prav tako iz prvotnega grafa).

Tole si predstavljam kot da se točke z enako barvo "zlijejo" v eno samo točko. Ko maš graf ustrezno pobarvan, B itak poznaš, V je pa unija vseh povezav od originalnih točk, ki sestavljajo eno "barvno točko", pri čemer ne šteješ "ciklov dolžine 1" (npr. povezave iz zelene v zeleno).