Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Графни бўяш
Графни бўяш масаласида граф чегарасини бир неча рангларга бутун сон билан рақамланган бўяшнинг шундай йўлини топиш керакки, ҳар қайси икки қўшни чўққилар турли рангларга бўялсин. Қарор қабул қилиш шундан иборатки, кўрсатилган талабларга риоя қилган ҳолда чўққиларни с ёки ундан кам рангга бўяш, оптималлаштириш эса – рангларнинг зарур минимал сонини аниқлаш.
Детерминалланмаган босқичда мумкин бўлган чўққилар рўйхати ва уларга берилган ранглар пайдо бўлади. Айнан шу босқичда нечта ранг ишлатилиши ҳал қиланади, шунинг учун назорат босқичи танланган ранглар сонига жавоб бермайди. Ечимни танлашда детерминалланмаган босқич С ранглар билан қаноатланади. Оптималлаштириш масаласида у рангларнинг сонини кетма-кет камайтириб, талаб этилувчи бўяш давом этгунча рангларнинг ката сонидан бошлаши мумкин. Графни х ранга бўяш мумкин эмаслигига ишонч ҳосил қилгач, биз х+1 рангга бўяш минимал даражада мумкин деб ҳисоблаймиз.
Қуйидаги алгоритм ҳосил бўлган бўяшни амалга ошириш мумкинлигини текширади. Бўялаётган граф туташувлар қуймаси кўринишида берилган, бу рўйхатнинг graph [j] элементи графнинг j чўққисини кўрсатади, бу элементнинг graph [j] .edgeCount майдони ундан чиқадиган қирралар сонини, graph [j] .edge майдони j чўққисига қўшни бўлган чўққилар сақланувчи массивни ҳисобланади.
boolean ValidColoring(graph,N,colors)
graph //туташувлар рўйхати
N //графдаги чўққилар сони
colors //ҳар бир чўққига унинг рангини солиштирувчи массив
for j=1 to N do
for k=1 to graph[j].edgeCount do
if (colors[j]=colors[graph[j].edge[k]]) then
return //йўқ
end if end for k end for j return //ҳа
Кўриниб турибдики, бу алгоритм бўяшнинг мос келишини тўғри текширади. У ҳамма чўққилардан ўтади ва агар чўққи бошқа шу рангдаги чўққи билан бевосита боғлиқ бўлса, алгоритм тўхтайди ва нотўғри жавобни қайтаради. Агар қўшни чўққиларнинг ҳам жуфтликлари турли рангларга бўялган бўлса, жавоб тўғри бўлади. Бу алгоритмнинг вақт бўйича мураккаблигига келсак, for ташқи цикл N ўтишни бажаради. Икки циклда Ушбу чўққидан чиқувчи ҳар бир қирра кўздан кечирилади. Шунинг учун солиштиришларнинг умумий сони қирралар сонига тенг бўлади, яъни алгоритмнинг мураккаблиги O(edges) га тенг – полиномиал баҳо аниқ, чунки графдаги қирралар сони N² дан ошади. Шундай экан, шубҳасиз талаб бажарилади.