Spanning Tree Nedir?
Genişleme ağacı olarak türkçeye çevrilebilir. Yönsüz ve bağlı bir graf verildiğinde (G=(V,E)) G grafının her köşesini içeren bir ağaç oluşturulur ve G grafının bir alt grafı bu alt graftan kastedilen ağaçtaki her kenar, G grafına aittir.
Minimum Spanning Tree Nedir?
Minimum Genişleme Ağacı olarak türkçeye çevirebilir. Spanning tree algoritmasını oluşturmak ve çalıştırmak oldukça maliyetli,hız gerektiren senaryolarda yetersiz olmuştur.Bu sebeple algoritma revize edilmeye çalışılmıştır.Genel olarak; ağaçtaki tüm kenarların ağırlıklarının toplamı algoritmanın maliyetini verir.Birden fazla grafın olduğu sistemlerde min maliyetli grafı oluşturmak için kullanılır.
Minimum Spanning Tree Kullanım Alanları
Genelde Ağ merkezlerini konumlandırmak için kullanılır.Bunlar dışında
- Biyomedikal Uygulamalar
- Gen haritasını uygulamalarında (Gen haritası çıkartılarak hastalıklar belirlenir.)
- İletişim hatlarında
- Kara yollarında
- Gerçek zamanlı yüz tanımlamada kullanılır.
Aslında bir optimizasyon problemini minium indirmek için kullanılır. Matematiksel yolla çözümü çok uzun süren NP-harel problerimin yaklaşık sonuçlarını yada kesin sonuçlarını bulmada bu algoritma kullanılır.
Yüz tanımlamada 100-200 tane insan foto ceker görüntü işlemeye verir o noktalara göre yüzünüzü belirlerler.Cene,kulak burun vs. bu şekilde 100 tane noktaya göre çıkabilir insan yüzü buna göre belirlerler.Kısacası yüzümüzü grafa çeviriyorlar ondan sonra graf üzerinden iki graf birbiri ile karşılaştırıyorlar.İki grafın birbiri ile benzer yada yaklaşık benzerlik oranını hesaplıyorlar.
Min spanning Tree grafında iki kaşın arası 3 birim olsun kulağın ile kaş arası 5 birim diyerek bir graf çıkartır.Min spanning tree de bu grafın alt grafı ile karşılaşıyor kaydediyor.
Yukarıdaki görselde minimum maliyeti yakalamak için bazı vertexler çıkarılarak spanning tree oluşturulmuştur.
Min Spanning Tree algoritmasını oluşturmak için iki temel algoritma vardır.Kruskal ve Prim algoritmaları.
Kaynaklar
- https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/