Санҷиш барои дудолӣ

Санҷиш барои дудолӣ

Санҷиш барои дудолӣ

Шарт

Ба шумо графи беравона дода шудааст. Санҷед, ки оё он дудолӣ аст, ва агар ҳа — тарафҳои онро бароред.

Ҳал

Теорема вуҷуд дорад: граф дудолӣ аст танҳо ва танҳо вақте ки ҳамаи даврҳои он дарозии ҷуфт доранд.
Аммо дар амал истифода бурдани формулировкаи дигар қулайтар аст: граф дудолӣ аст танҳо ва танҳо вақте ки он дуқабата аст.

DFS-ро истифода мебарем (ҳамчунин, мисли масъалаи қаблӣ, метавон BFS-ро истифода бурд), аз ҳар қуллае оғоз карда, ки ҳанӯз боздид нашудааст. Дар ҳар ҷустуҷӯ қуллаеро, ки аз он оғоз мекунем, ба тарафи 1 (масалан, бо ранги 0) таъин мекунем. Ҳар дафъа, ки мо ҳамсояи ҳанӯз боздиднашудаи қуллаи як тарафро боздид мекунем, ӯро ба тарафи дигар таъин мекунем.

Агар мо кӯшиш кунем ба ҳамсояе гузарем, ки аллакай боздид шудааст, месанҷем, ки ӯ дар тарафи дигар бошад. Агар ӯ дар ҳамон тараф баромад, хулоса мекунем, ки граф не дудолӣ аст.

Пас аз он ки мо ҳамаи қуллаҳоро боздид кардем ва онҳоро бо муваффақият ба тарафҳо тақсим намудем, мо медонем, ки граф дудолӣ аст, ва тақсимбандии онро сохтем.