Kategoriya

Algoritmlar

Noyabr 25, 2020by Sherzod Shermukhamedov

Weight'ga ega DAGlarda shortest path'ni topiş

Endi biz DAGlar (directed acyclic graph) uçun shortest path'ni topişni körib çiqamiz. Aslida DAGlar uçun Dijkstra'ning algoritmi ham işlayveradi, ammo bizdagi graph'ning acyclic, ya'ni aylanasi yöq ekanligini bilar ekanmiz, bu bizga shortest path'ni topiş işini yengillaştiradimi?

Noyabr 24, 2020by Sherzod Shermukhamedov

Shortest' path'ni topiş uçun Dijkstra algoritmi

Dijkstra'ning algoritmi graph'dagi bir vertex'dan boşqa har bir vertex'ga qisqa yölni topiş uçun işlatiladi.

Noyabr 19, 2020by Sherzod Shermukhamedov

Shortest path - digraph'da qisqa yöllar haqida

Biz ötgan mavzularda körib ötganimiz, minimum spanning tree - edge'lari weight'ga ega undirected graph'dagi barça vertex'larni öz içiga olgan qisqa yölni topişga bağişlangan edi. Edge-weight'li directed graph uçun esa shortest path (qisqa yöl) algoritmlari bilan tanişib çiqamiz.

Noyabr 18, 2020by Sherzod Shermukhamedov

Minimum spanning tree'ni topiş uçun Prim algoritmi

Minimum spanning tree'ni topişning yana bir klassik algoritmlaridan biri - Prim algoritmi işlaş tartibi quyidagiça...

Noyabr 17, 2020by Sherzod Shermukhamedov

Minimum spanning tree'ni topiş uçun Kruskal algoritmi

Graph'dagi minimum spanning tree'ni topişning klassik algoritmlaridan biri - Kruskal algoritmi ğoyasi tuşunişga oson. Uning işlaş tartibi...

Noyabr 16, 2020by Sherzod Shermukhamedov

Greedy algoritmi

Minimum spanning tree (MST) algoritmlarini boşlaşdan avval biz ular uçun umumiy algoritm - Greedy algoritmi nazariyasini körib çiqamiz. Greedy har bir qadamda optimal variantni tanlab, muammoni yeçişning optimal yölini topişga urinadi.

Noyabr 15, 2020by Sherzod Shermukhamedov

Minimum spanning tree

Minimum spanning tree (MST) - undirected graph'dagi barça özaro boğlangan vertex'larni öz içiga olgan (spanning) va aylana bölmagan (acyclic) sub-graph'lar içidan minimum weight'li sub-graph.

Noyabr 14, 2020by Sherzod Shermukhamedov

Directed graph'da kuçli boğlangan komponentlar

Kuçli boğlangan komponentlar (strongly connected components, SCC) connected components'ning directed graph uçun möljallangan körinişi bölib, yagona farqi - strongly connected components'da vertex'lar ikki taraflama boğlangan bölişi kerak.

Noyabr 13, 2020by Sherzod Shermukhamedov

Topological sort

Biz ötgan graph masalalarida asosan undirected graph'larni körib çiqdik. Aslida undirected graph directed graph'dan kodda ifodalanganda bor yöği graph'dagi barça vertex'larning ikki tomonlama (ikki yönalişli) boğlangani bilan farq qiladi. Şuning uçun undirected graph masalalaridagi yeçimlar yoki alg

Noyabr 12, 2020by Sherzod Shermukhamedov

Kenigsbergning yetti köprigi

The-Koenigsberg-bridge-problem-a-seven-bridges-of-Koenigsberg-b-graph-representation

Kenigsberg (Königsberg, hozirgi Kaliningrad) şahridagi yetti köprikni qanday qilib bir köprikga ikki marta çiqmasdan bosib ötiş - qadimiy matematik masalalardan biri bölib, birinçi marta 1736-yilda Leonard Eyler tomonidan yeçilgan. Eyler har bir köprikdan faqat bir marta foydalanib barça köpriklarni