Prim Algoritması

Prim Algoritması, minimum spanning tree algoritmalarından biridir. Kenarların bir alt kümesini, tüm düğümleri kapsayacak ve kenarların toplam ağırlığını minimum yapacak şekilde bulur.

Bu algoritma 1930 yılında matematikçi Vojtech Jarnik tarafından bulunmuştur. Daha sonra bağımsız olarak 1957'de bilgisayar bilimcisi Robert C. Prim ve 1959'da Dijkstra tarafından tekrar bulunmuştur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritması da denir.

Bu algoritmayı bir örnek ile anlatmak istersek:

  * Orijinal graf aşağıdaki gibi olsun:

 

  * İlk olarak düğüm noktaları arasındaki uzaklıkları gösteren bir matris hazırlanır. Eğer iki graf arasında bağlantı, yol yoksa buraya bir M değeri girilir. Bu değer çok büyük bir tam sayıyı temsil etmektedir. Algoritma uygulanırken bu değerler dikkate alınmaz. Yukarıdaki graf için bu matris aşağıdaki gibidir:

  * Bu işlemden sonra başlamak için herhangi bir düğüm seçilir ve bu düğümün olduğu sütun silinir. Seçilen düğümün satırındaki en küçük sayı seçilerek işaretlenir. Bir sonraki adımın başlangıç düğümü, seçilen sayının ait olduğu sütun olacaktır.

  * Yukarıdaki işlem sonucu en küçük eleman 5 olarak belirlendi. Şimdi 5'in bulunduğu sütun olan D seçilmiş oluyor. Bu sütun silinir ve eski satır (yani ilk seçmiş olduğumuz A'nın bulunduğu satır) ile D satırında en küçük eleman aranır:

  * Aynı işlemler F için tekrar edilir:

  * Aynı işlemler B için tekrar edilir; B'nin bulunduğu sütun silinir, satır arama kümesine dahil edilir:

  * E'nin bulunduğu sütun silinir, satır arama elemanlarına dahil edilir:

  * Aynı işlemler bu sefer C için uygulanır:

  * Böylelikle en son sütuna kadar gelinmiş olur ve işlem burada sona erer:

  * Yukarıdaki matriste belirtilen elemanlara karşılık gelen, AB, AD, BE, DF, EC ve EG yolları minimum spanning tree olmaktadır:

_______________________________________________________________________
Kaynaklar:
http://tr.wikipedia.org/wiki/Prim_algoritmas%C4%B1
http://www.ce.yildiz.edu.tr/mygetfile.php?id=1373
_______________________________________________________________________

Kruskal Algoritması

Kruskal algoritması, bir grafın tüm düğümlerinin en kısa şekilde dolaşılmasını amaçlar.

Her seferinde en iyi kenarın seçilmesi esasına dayalıdır. n kenarlı bir graf için herhangi bir düğümle başlanır ve en kısa yol buna eklenir. Döngü oluşturmayacak şekilde (n-1) kenar eklenene kadar devam edilir. Aynı değerli kenarlarda seçim keyfi yapılabilir. Düğümlerin birleştirilme işlemine en az maliyetli kenardan başlanır, kalan kenarlar arasından en az maliyetlisi seçilerek devam edilir.

Bir örnek üzerinde bu algoritmayı uygulayalım:

__________________________________________________________________________

  * Orijinal graf aşağıdaki gibi olsun:

 

__________________________________________________________________________ 

  * Algoritmada önce en kısa kenarlar belirlenir. Ve uygun olan seçilir. Aynı uzunlukta kenarlar varsa rasgele seçim yapılır. Yukarıdaki şekilde de görüldüğü gibi AD ve CE kenarları eşit uzunluklara sahip en kısa kenarlardır. Bunlardan AD gelişigüzel seçilebilir. Seçim aşağıda yeşil renk ile belirtilmiştir:

 

__________________________________________________________________________

  * AD seçildikten sonra kalan kenarlar arasında, bir döngü oluşturmayacak şekilde seçilebilecek en kısa kenar CE kenarıdır. Bu nedenle bir sonraki seçim bu kenar olacaktır:

 

__________________________________________________________________________

  * Kalan kenarlar incelendiğinde, en kısa olan kenarın, 6 birim uzunluğu ile DF olduğu görülmektedir. Ayrıca herhangi bir çevrim de oluşturmamaktadır. Bu nedenle yeni seçim bu kenar olacaktır:

 

__________________________________________________________________________

  * Geriye kalan kenarlar tekrar incelendiğinde, kalan en kısa kenarların 7 birim uzunluğu ile AB ve BE olduğu görülmektedir. Bunlardan AB kenarı seçilebilir:

    AB kenarı seçildikten sonra, şekil incelendiğinde artık BD kenarının kullanılamayacağı görülür. Çünkü sonraki adımlarda BD kenarı seçilirse ABD bir çevrim oluşturmaktadır. Kruskal algoritmasının şartlarından biri de seçimlerin bir çevrim, döngü oluşturmamasını gerektirmektedir. Bu nedenle bu kenar kırmızı ile belirtilmiştir.

__________________________________________________________________________

  * Şekil incelendiğinde, en kısa kenarın BE kenarı olduğu görülmektedir:

    BE kenarı seçildikten sonra, BC, DE, ve FE kenarlarının da, birer çevrim oluşturabileceği görülmektedir. Bu nedenle bu kenarlar da ilerleyen adımlarda kullanılamayacaktır.

__________________________________________________________________________

  * Geriye sadece EG ve FG kenarları kalmaktadır. Bu kenarlardan en kısa olan, 9 birim uzunluğundaki EG seçilir.

 

__________________________________________________________________________

  * Seçilebilecek kenar kalmamıştır. İşlem sona erer.

__________________________________________________________________________

Kaynaklar:

http://en.wikipedia.org/wiki/Kruskal's_algorithm

http://www.ce.yildiz.edu.tr/mygetfile.php?id=2639

__________________________________________________________________________

"Ubuntu" nedir?

Ubuntu, insanların birbirlerine bağlılıklarına odaklanan insancıl bir felsefedir (humanity to others). Sözcük Güney Afrika'daki Bantu dillerinden gelmektedir. "Ben ben olduğum için sen sensin (I am what I am because of who we all are)" sloganı üzerine şekil alır. Ubuntu Linux dağıtımı, adını bu felsefeden alır.

The Meaning of “Ubuntu” – Explained by Nelson Mandela

________________________________________________________________________
Kaynak: 
http://tr.wikipedia.org/wiki/Ubuntu_%28felsefe%29 
http://www.ubuntu.com/project/about-ubuntu
________________________________________________________________________