Ağ tasarım problemlerinde farklı bağlantılılıkların incelenmesi

Ağ tasarım problemleri telekomünikasyon, ulaştırma, dağıtma ve lojistik gibi bir çok alanda önem kazanmıştır. Çalıştığımız problemler ağda meydana gelebilecek bir arıza durumunda bile ağın veri iletimine devam edebildiği kalımlı ağ tasarım (KAT) problemleridir. Bu tezde, ayrıt-bağlantılılık gereksinimlerine sahip minimum maliyetli bağlantılı ağ tasarım problemi incelenmiştir. Bu gereksinimleri tanıtmak için izomorf ağlar tanımı kullanılmıştır. Verilen bir grafa izomorf olan herhangi bir graf ağdan silindikten sonra bağlantılı kalan minimum maliyetli bağlantılı ağların tasarlanması ihtiyacı bizi bu problemde çalışmaya motive etmiştir. İlk olarak ağdaki herhangi bir ayrıt silindiğinde ağın bağlantılı olma durumu incelenmiştir. Bu ağ yapısı literatürde 2-ayrıt bağlı ağ olarak adlandırılmaktadır. İkinci olarak ağdaki herhangi 2 ayrıtlı bir eşleme silindiğinde herhangi iki terminal düğümü arasında en az bir yol içeren minimum maliyetli bir altgrafın bulunması durumu incelenmiştir. Yukarıdaki iki durum için ağın yapısal özellikleri belirlenip matematiksel modelleri geliştirilmiştir. Bu modeller kullanılarak güçlü alt sınırlar sağlayan dal ve sınır tabanlı sezgisel algoritmalar önerilmiştir. Bu algoritmalar C dilinde kodlanıp hesaplama denemeleri yapılmıştır. Denemeler programın verimli olduğunu göstermektedir