• Graph(Çizge) nedir?
• Ağaç nedir?
• Kullanılan alanlar
• Minimum Kapsayan Ağaçlar nedir?
• Prim Algoritması
• Kruskal Algoritması

• Çizge veya Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Örnek bir çizge:

• Eğer ki, graf bağlı bir graf ise ve bu graf hiç döngü içermiyorsa, bu graf türüne Ağaç denmektedir. Örnek bir Ağaç:

• Ağaçlar bir çok nedenden dolayı graf teorisi içerisinde önemli bir yere sahiptir. Ayrıca, ağaçlar graf teorisinin birçok uygulamasında ön plana çıkmaktadır.

• Matematikte
• Fizikte
• Biyolojide
• Örneğin, bilgisayar bilimcileri, hiyerarşik veritabanı kullanarak belirli tipteki verilerin depolanma ve düzenlenme uygulamasını, ağaçları kullanarak gerçekleştirmişlerdir.
• Bunlara ek olarak, sıralama, kodlama teorisi ve bazı optimizasyon problemlerinin incelenmesinde de ağaçlar kullanılmaktadır.

• Ağırlıklı bir grafta(weighted graph), yani birbirleri ile bağlantılı olan bütün düğümlerin yollarının maaliyetleri olan bir grafta, bütün düğümleri en kısa yol vercek şekilde dolaşan(kapsayan) bir ağaçtır.

• Örneğin, hava yollarını en az maaliyetli şekilde ve döngüsüz olacak şekilde oluşturulmasında kullanılmaktadır.
• Aynı şekilde şehirler arasında kara yolları oluşturmakta kullanılmaktadır. Örneğin, maaliyet olarak da dağlar, ırmaklar vs. göz önüne alınmaktadır.

• Bir çizge(graf) birçok kapsayan ağacı içerebilir. Örneğin, 4 düğümlü bir çizge 16 tane kapsayan ağaca sahiptir:

Minimum kapsayan ağaç bulmak için çeşitli algoritmalar vardır. Bunlardan en ünlü olan bazılar aşağıdakilerdir:

• Prim Algoritması
• Kruskal Algoritması
• Boruvka(Sollin) Algoritması

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.

1. Herhangi bir düğümi seç
2. Bu düğüme bağlı olan en kısa kenarı seç
3. Elimizde var olan bağlı düğümlerin birine bağlı olan en kısa kenarı seç
4. Düğümler birbirlerine bağlı olana kadar 3.Adımı tekrarla

Kruskal algoritması Joseph Kruskal tarafından geliştirilmiş ve ilk kez 1956 yılında anlatılmıştır. Kruskal algoritması 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.

• Prim ve Kruskal Algoritmalarının ikisi de her zaman aynı uzunluktaki sonucu verecektir.

• Bu algoritmalar minimum kapsayan ağaç oluştururken, genelde kenarları farklı sırayla seçmektedir.

• Bazen ise farklı kenarları da seçebilirler. Örneğin, kenar maaliyetleri aynı olduğu zaman.

• https://en.wikipedia.org/wiki/Graph
• https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
• https://tr.wikipedia.org/wiki/Prim_algoritmas%C4%B1
• http://www.stoimen.com/blog/2012/11/19/computer-algorithms-prims-minimum-spanning-tree/ -https://www.youtube.com/watch?v=8fJgkVpxbQg
• https://www.youtube.com/watch?v=5XkK88VEILk
• https://www.youtube.com/watch?v=Pn874kEc3IA
• https://github.com/israelst/Algorithms-Book—Python/blob/master/5-Greedy-algorithms/kruskal.py

• Dikkatiniz için Teşekkürler…
• Sorular???

• Soru1: Aşağıdakilerden hangisi Minimum Kapsayan Ağaç oluşturabilmek için gerekli bir graf özelliğidir? Graf nasıl bir Graf olmalı?
  
  a) Bağlı olmayan bir Graf
  
  b) Ağırlıklı bir Graf
  
  c) Döngülü bir Graf
  
  d) Ağırlıksız bir Graf
  
  e) Yönlü bir Graf
  

• Soru2: Aşağıdakilerden hangisi Ağaçtır?
  

  1.resim	2.resim	3.resim
  4.resim	5.resim	6.resim

  a) 1-2-3
  b) 2-3-4
  c) 3-4-5
  d) 4-5-6
  e) 2-3-6

• Soru3: Aşağıdakilerden hangisi yanlıştır?
  
  a) Prim algoritması Kruskal algoritmasının seçtiği kenarın aynısını seçmektedir.
  
  b) Prim ve Kruskal Algoritmalarının ikisi de her zaman aynı uzunluktaki sonucu verecektir
  
  c) Kruskal algoritması her seferinde en iyi kenarın seçilmesi esasına dayalıdır.
  
  d) Prim algoritması matematikçi Vojtech Jarnik tarafından bulunmuştur.
  
  e) Kruskal algoritması Joseph Kruskal tarafından geliştirilmiştir.

• Cevap1: b) Ağırlıklı bir Graf
  
• Cevap2: a) 1-2-3
  
• Cevap3: a) Prim algoritması Kruskal algoritmasının seçtiği kenarın aynısını seçmektedir.