Graflar Kuramı

**SERDEM** · 30.08.10, 02:55

Graflar Kuramı

XVIII. yy’da Euler’in çalışmaları sonucunda ortaya çıkan graflar kuramı, XX. yy’ın başında König ve Kuratowski’nin, Cayley’in ve daha yakınlarda Berge, Erdös ve Harray’nin çalışmalarıyla bir matematik dalı haline geldi. Bilgisayar alanında ve özellikle algoritmalar üzerinde yapılan araştırmalar, graflar kuramına yeni bir soluk getirdi. Graflar kuramı, çok çeşitli uygulamalar için oluşturulan problemleri, noktalar ve noktalar arası bağlantılar yardımıyla çizilen konfigürasyonlara indirgeyerek çözme olanağı verir.

GRAFLAR KURAMI
Graflar kuramının, << Königsberg (bugün Rusya’da Kaliningrad) Köprüleri>> denilen probleme kadar dayandığı kabul edilir. 1736’da Euler’in çözdüğü bulmacaya benzer bir problem olan << Königsberg Köprüleri >> problemi, şöyle ifade edilebilir: kentin herhangi bir yerinden yola çıkıp, kentteki yedi köprüden yalnızca bir kez geçerek başlangıç noktasına geri dönmek mümkün müdür?
Graflar kuramı, her şeyden önce çözümü aranan bir problemi ya da işi en etkin şekilde temsil edebilmeye ve düzenlemeye yarar. Bu problem graf biçimine çevrildikten sonra, tüm amaçları yerine getirecek en hızlı veya en az masraflı yolu bulmak için sistematik yöntemler aranır.
Graflardan çok değişik uygulama alanlarında yararlanılır: ulaşım ağlarının optimizasyonunda (yol ya da bilgi ulaşımı), elektrik şebekeleri kavramında, haberleşme ağlarında, istatistiksel mekanikte, kimyasal formüllerde, bilgisayar kuramında, toplumsal bilimlerde, coğrafyada, mimarlıkta…

GRAF NEDİR?

Graf sözcüğünü ilk kez 1822’de İngiliz matematikçi J.J. Sylvester kullandı, gaflar kuramı üzerine ilk kitabı ise 1936’da D. König yayımladı. Garf, bir noktalar(köşeler) kümesi ile bu noktaların arasındaki çizgiler ya da oklar(ayrıtlar) kümesi tarafından tanımlanan bir geometrik çizimdir. Her ayrıtın ucunda gerektiğinde birbiri üzerine gelebilen iki köşe vardır. Eğer grafın her ayrıtında bir başlangıç ve bir sonuç ucu ayırt ediliyorsa, bu graf yönlü olarak tanımlanır.

Grafların özellikleri farklı tipten problemleri niteler:

- Eğer bir grafta, iki ayrı köşe tek bir ayrıtla birbirine bağlanıyorsa buna yalın graf denir.
- Eğer bir grafta iki ayrı köşe bir dizi kesintisiz ayrıtla birbirine bağlanıyorsa, buna bağlantılı graf denir.
Bir << ağaç >> kapalı yol içermeyen bağlantılı bir graftır. Ağaçların ya da ağaç görünümlü grafların kullanılmasının örneklerine, veri tabanlarının yönetiminde rastlanır. Bilgilerin nasıl düzenlendiğini izleyerek ağacı tanımak, onların incelenmesini kolaylaştırır ve optimize eder. Bilgisayarlardaki buna koşut yapı amaçları ve hedefleri düzene koyan bir yöntem izlenerek gerçekleştirilir. Bu alan, bilgisayar matematiğinin en etkin biçimde kullanıldığı bir araştırma dalıdır.