Essay in Graf teorisi

GRAPH THEORY(ÇIZGE KURAMI)

GİRİŞ

Graph Theory nedir?

Tarihçesi

Graf teorisinin kullanıldığı yerler

GELİŞME

Graf çizmek ve bazı özel Graflar

Euler Grafı

Edinburgh Grafı

Graph-theoretic data yapıları nasıl oluşturulur

Liste yardımıyla

Matrix yardımıyla

Graf teorisi yardımıyla çözülen bazı problemler

Düzlemlilik kullanılarak çözülen bazı problemler

Renklendirme kullanılarak çözülen bazı problemler

Rota problemleri

SONUÇ

Graf teorisinin matematik ve bilgisayar bilimine yaptığı katkıları tekrar gözden geçirmek

GRAPH THEORY(ÇIZGE KURAMI)

Graf teorisi 1736 yılında Leonhard Euler tarafından ilk defa kullanılmış bir kavramdır. Graflar bazıları birbirlerine bağlı olan çok sayıdaki noktalardan oluşur. Euler yine kendisinin yazdığı könisgberg köprüleri sorusuna graflar yardımıyla çözerek yeni bir matematik dalı ortaya çıkarmıştır.

Könüsgberg köprüleri sorusunda dört anakara ve yedi tane köprüden oluşan bu şehirde, herhangi bir anakaradan başlayarak ve her geçtiğimiz köprüden bir daha geçmemek koşuluyla tüm karaları dolaşmanın mümkün olup olmadığı problemine cevap aramıştır. Bu soru aslında bizim küçüklükten beri sürekli duyduğumuz açık zarf sorusunun bir benzeriydi. Yandaki resimde de gördüğümüz gibi bu soruda bir noktadan başlayarak aynı çizgiden bir kere daha geçmemek şartıyla tüm noktaları dolaşmak söz konusuydu.

Graf teorisi bilgisayar empieza matematik bilimlerindeki uygulamaları daha çok göze çarpsa weil, fizik, biyoloji, kimya bilimlerinde ve hatta linguistikte bile uygulamalarını görmek mümkün. Dillerdeki parçalı yapılardan dolayı graf teorisi linguistik biliminde kullanılmaktadır. Ayrıca, kimya ve fizik bilimlerinde kullanılan molekül yapıları graflar yardımıyla gösterilmektedir. Biyolojide, popülâsyonların gösterimi, hastalık bölgelerinin ve yayılma alanlarının gösterilmesi, hayvanların yaşadığı habitatların gösterimi yine graf teorisi vas?tas? ile mümkündür. Bilgisayar ve matematik bilim dallarına katkısı biraz daha buyuktur. Mesela, " Minimum spanning tree", " Shortest course problem" ve " Network flow problem" gibi birçok problem graf teorisi yardımıyla çözülmüştür.

Graf çizilirken, öncelikle noktalar yardımıyla objeler belirlenir. Sonrasında, çizgiler yardımıyla aradaki bağlantılar belirlenir. Eğer çizilecek graf yönlü bir grafsa bağlantıların yönlerininde belirtilmesi gerekmektedir.

Şimdi iki özel graftan bahsedeceğiz. Bunlardan ilki yukarıda bahsettiğimiz Euler grafıdır. Bahsettiğimiz gibi Euler grafı her bir çizgiden sadece bir kere geçmek koşuluyla tüm çizgileri dolaşmaktır. Yukarıdaki resimdeki gibi bazı graflar Euler grafı özelliğine uyarken bazı graflar uymamaktadır. Euler 1736 yılında yayınladığı makalesinde bu özelliğe uyan grafların çok basit bir yöntemle fark edilebilindiklerini tum olasılıkları denemek zorunda olunmadığından bahsetmiştir. Bu yöntem şöyledir: Her noktadan çıkan çizgi sayısını bir yere kaydedelim. Eğer tek sayı miktarı, iki ya da ikiden daha azsa bu graf Euler grafıdır. Diğer özel grafımız ise Hamilton grafıdır. Bu graf Euler grafının noktalarıyla çizgilerinin yer değiştimiş halidir. Diğer bir deyişle, her noktadan sadece bir kere geçmek şartıyla tüm noktaları dolaşan graflara Hamilton grafı denmektedir.

Yukarıda graf teorisinin bilimlere yaptığı katkıları sayarken bilgisayar bilimine çok büyük katkılarının olduğunu söylemiştik. Fakat grafları yukarıdaki halleriyle bilgisayarlara kaydedemeyiz. Bu yüzden, grafları bilgisayarların anlayabileceği data yapılarına çevirmemiz gerekmektedir. Bunu iki türlü yapabiliriz. Bunlardan birincisi grafı matrise çevirip çift katlı mixture yardımıyla bilgisayara kaydetmektir. Bunun methodu ise şöyledir: İlk önce tüm noktalar sayılar yardımıyla isimlendirmelidir. Toplam d tane nokta olduğunu varsayalım. n*n boyutunda bir matris yapalım. Matristeki her boşluk graftaki iki nokta arasındaki bağlantıyı ifade etsin. Eğer iki nokta arasında çizgi varsa matrisimizdeki ilgili boşluğa " 1" yoksa " 0" yazalım. Mesela,...