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.
PHP dasturchi bilishi kerak bo’lgan Javascript hususiyatlari
PHPdan keyin Javascriptda (Jquery emas) kod yozishni boshlaganimda tilning ba’zi o’ziga xosliklari men uchun yangilik bo’lgan. Quyida ularni tushuntirishga harakat qilaman.
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.
Yo’qotishlar bahosi
Taylanddagi ekspatlar orasida yaqin ikki oy ichidagi muhokamalardan biri – amerikalik o’qituvchining Koh Chang orolidagi resortlardan birida bo’lib, yomon baho qo’ygani uchun, tuhmat qilish ayblovi bilan sudga berilgani bo’ldi.
Topological sort
Biz o’tgan graph masalalarida asosan undirected graph’larni ko’rib chiqdik. Aslida undirected graph directed graph’dan kodda ifodalanganda bor yo’g’i graph’dagi barcha vertex’larning ikki tomonlama (ikki yo’nalishli) bog’langani bilan farq qiladi. Shuning uchun undirected graph masalalaridagi yechimlar yoki algoritmlar direct graph uchun ham mos kelishi mumkin.
Kenigsbergning yetti ko’prigi
Kenigsberg (Königsberg, hozirgi Kaliningrad) shahridagi yetti ko’prikni qanday qilib bir ko’prikga ikki marta chiqmasdan bosib o’tish – qadimiy matematik masalalardan biri bo’lib, birinchi marta 1736-yilda Leonard Eyler tomonidan yechilgan. Eyler har bir ko’prikdan faqat bir marta foydalanib barcha ko’priklarni aylanib chiqish imkonsizligini isbotlab bergan.
Graph’dagi aylanalarni topish
Graph’da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan. Bir graph’da aylanalar bir necha bo’lishi mumkin.
Graph masalalari. Bipartite graph
Agar graph’ning har bir vertex’i qarama-qarshi tomondagi vertex’ga bog’lanuvchi ikki subset’ga (qismga) ajraladigan bo’lsa, demak graph – bipartite bo’ladi.