Maximum flow’ni topish uchun Ford-Fulkerson algoritmi
Avvalgi maqolada maximum flow allaqachon topilgan graph’ni ko’rib o’tdik. Endi flow’ni qanday hisoblash haqida so’z yuritamiz.
Digraph’da minimum cut va maximum flow masalalari
Graph processing masalalarini o’rganishni davom ettiramiz. Minimum cut – graph’ni ikkiga shunday bo’lish kerakki, uning bo’linish edge’lari bir-biriga eng kam (kuchsiz) bog’langan joyi bo’lsin. Oddiyroq aytganda, graph’ni ikkiga bo’lish uchun eng kam harajat / kuch talab etilsin.
Digraph’da negativ weight’lar
Ushbu maqolada biz negativ (manfiy) weight’larning graph’da shortest path’ni topishdagi ta’sirini ko’rib chiqamiz. Avvaldan aytib o’tish kerakki, negativ weight’lari bor graph’lar uchun bir ko’rib o’tgan Dijkstra algoritmi ishlamaydi.
Shortest’ path’ni topish uchun Dijkstra algoritmi
Dijkstra’ning algoritmi graph’dagi bir vertex’dan boshqa har bir vertex’ga qisqa yo’lni topish uchun ishlatiladi.
Shortest path – digraph’da qisqa yo’llar haqida
Biz o’tgan mavzularda ko’rib o’tganimiz, minimum spanning tree – edge’lari weight’ga ega undirected graph’dagi barcha vertex’larni o’z ichiga olgan qisqa yo’lni topishga bag’ishlangan edi. Edge-weight’li directed graph uchun esa shortest path (qisqa yo’l) algoritmlari bilan tanishib chiqamiz.
Minimum spanning tree’ni topish uchun Prim algoritmi
Minimum spanning tree’ni topishning yana bir klassik algoritmlaridan biri – Prim algoritmi ishlash tartibi quyidagicha…
Minimum spanning tree’ni topish uchun Kruskal algoritmi
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
Greedy algoritmi
Minimum spanning tree (MST) algoritmlarini boshlashdan avval biz ular uchun umumiy algoritm – Greedy algoritmi nazariyasini ko’rib chiqamiz. Greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi.
Minimum spanning tree
Minimum spanning tree (MST) – undirected graph’dagi barcha o’zaro bog’langan vertex’larni o’z ichiga olgan (spanning) va aylana bo’lmagan (acyclic) sub-graph’lar ichidan minimum weight’li sub-graph.
Directed graph’da kuchli bog’langan komponentlar
Kuchli bog’langan komponentlar (strongly connected components, SCC) connected components’ning directed graph uchun mo’ljallangan ko’rinishi bo’lib, yagona farqi – strongly connected components’da vertex’lar ikki taraflama bog’langan bo’lishi kerak.