Dasturchi, frilanser, gik va introvert
Endi biz DAGlar (directed acyclic graph) uchun shortest path’ni topishni ko’rib chiqamiz. Aslida DAGlar uchun Dijkstra’ning algoritmi ham ishlayveradi, ammo bizdagi graph’ning acyclic, ya’ni aylanasi yo’q ekanligini bilar ekanmiz, bu bizga shortest path’ni topish ishini yengillashtiradimi?
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
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’da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan. Bir graph’da aylanalar bir necha bo’lishi mumkin.