პრიმის ალგორითმი
კომპიუტერულ მეცნიერებაში პრიმის ალგორითმი ეწოდება ხარბ ალგორითმს, რომელიც პოულობს მინიმალურ დამფარავ ხეს წონადი არაორიენტირებული გრაფისთვის. სხვა სიტყვებით, ის ეძებს წიბოებს, რომლებიც ქმნიან ხეს, რომელიც ყველა წვეროს მოიცავს და მისი წიბოების წონების ჯამი რაც შეიძლება მინიმალურია. პრიმის ალგორითმით მინიმალური დამფარავი ხის ფორმირება იწყება ნებისმიერი r წვეროდან. ყოველ ბიჯზე ემატება უმცირესი წონის წიბო იმ წიბოებს შორის, რომლებიც წვეროს აერთებენ ხის არაწევრ წვეროებთან.
მოცემული ალგორითმი 1930 წელს შეიმუშავა ჩეხმა მათემატიკოსმა ვოიტეხ იარნიკმა[1], მოგვიანებით კი თავიდან შეისწავლეს რობერტ პრიმმა 1957 წელს[2] და ედსგერ ვიბე დეიქსტრამ 1959 წელს.[3] ამიტომაც, ალგორითმი ასევე ცნობილია როგორც იარნიკის ალგორითმი,[4] პრიმ-იარნიკის ალგორითმი[5] ან პრიმ-დეიქსტრას[6] ალგორითმი.
ლიტერატურა რედაქტირება
- ზაზა გამეზარდაშვილი, ალგორითმები, ქუთაისი, 2004. გვ 158.
სქოლიო რედაქტირება
- ↑ Jarník, V. (1930), "O jistém problému minimálním", Práce Moravské Přírodovědecké Společnosti 6 (4): 57–63.
- ↑ Prim, R. C. (November 1957), "Shortest connection networks And some generalizations", Bell System Technical Journal 36 (6): 1389–1401, , http://archive.org/details/bstj36-6-1389.
- ↑ Dijkstra, E. W. (December 1959), "A note on two problems in connexion with graphs", Numerische Mathematik 1 (1): 269–271, , http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf.
- ↑ Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms (4th რედ.), Addison-Wesley, p. 628, ISBN 978-0-321-57351-3, http://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA628.
- ↑ Rosen, Kenneth (2011), Discrete Mathematics and Its Applications (7th რედ.), McGraw-Hill Science, p. 798, http://books.google.com/books?id=6EJOCAAAQBAJ&pg=PA798. წაკითხვის თარიღი: 2019-12-29[მკვდარი ბმული].
- ↑ Cheriton, David; Tarjan, Robert Endre (1976), "Finding minimum spanning trees", SIAM Journal on Computing 5 (4): 724–742, .