Eden od najpogostejših problemov v teoriji grafov je problem iskanja močno povezanih komponent usmerjenega grafa. Razgradnja samega usmerjenega grafa v močno povezane komponente predstavlja pomembno orodje v teoriji grafov, ki je uporabno pri analizi prevajalnikov, podatkovnem rudarjenju in na ostalih področjih. V matematični teoriji pravimo, da je graf močno povezan, če za vsaki dve njegovi vozlišči velja, da sta dosegljivi med seboj. Prav tako mora za vsako od močno povezanih komponent poljubnega usmerjenega grafa veljati, da tudi sama predstavlja močno povezan graf. V tem diplomskem delu bomo podrobno predstavili zgoraj omenjeni problem. Preko njegove aplikacije bomo poskušali razumeti njegov pomen. Nato bomo raziskali različne pristope za iskanje močno povezanih komponent usmerjenih grafov. Na koncu bomo s primerjavo preučili njihove prednosti in pomanjkljivosti ter iz tega sklepali, kateri algoritem je ustrezen v določeni situaciji.
|
