MAT106U-MATEMATİK II
Ünite 5: Çizge Kuramına Gidiş
Çizge Nedir?
Çizge, boş kümeden farklı noktalar kümesiyle bu noktalar arasındaki çizgilerin kümesinden oluşur. Çizgiler istediği gibi olabilir. İster düz çizgi, ister eğri. Hatta çizgilerin kesişmesinin de bir sakıncası yok (S:104, Şekil 5.1). Köşe noktalarının kümesini V = {x,y,z....}olarak gösterebiliriz. Köşe noktalarının arasındaki çizgilere ise kenar denir. Eğer çizgenin tüm kenarlarının kümesini E ile gösterecek olursak, E = {xy,xz,yz…} şeklinde gösterilebilir. Çizgenin köşe noktalarının kümesi V ile kenarlarının kümesi E verildiğinde bir G çizgesi G = (V, E) şeklinde yazılır.
Çizgeye bir örnek verecek olursak, 8 takımdan oluşan bir futbol ligini düşünelim. Lig başladıktan birkaç hafta sonra, diyelim ki üç hafta sonra, bu takımlardan bazıları birbirleriyle karşılaşacak, bazıları ise daha karşılaşmamış olacaktır. İşte köşe noktaların kümesini futbol takımları, kenarların kümesini de birbirleriyle en az bir kez karşılaşan takımlara karşılık gelen köşe noktaları arasına çizeceğimiz çizgiler olarak alırsak, bir çizge elde ederiz (S:106, Şekil 5.4).
Bir köşe noktasından çıkan kenar sayısına o köşe noktasının derecesi denir. Çizgedeki bir u köşe noktasının derecesi d(u) şeklinde gösterilir. Bir çizgedeki tüm köşe noktalarının derecelerinin toplamı çizgedeki kenar sayısının iki katına eşittir.
Bir çizgenin herhangi iki köşe noktası arasında bir kenar varsa, bu tür çizgelere tam çizge denir. Bir çizgenin iki köşe noktası arasında bir kenar varsa, bu noktalara komşu noktalar denir.
Königsberg Köprüleri
Çizge kuramına ait belki de en eski sonuç 18. Yüzyılda Leonhard Euler tarafından keşfedilmiştir. Bu sonuç Königsberg (şimdiki adıyla Kaliningrad)’de yaşayan halkın ortaya attığı bir soru üzerine elde edilmiştir. Königsberg şehri, Pregel nehrinin kolları ile dört farklı bölgeye ayrılmaktaydı ve nehrin üzerinde yer alan yedi köprüyle de bu bölgeler birbirine bağlanmaktaydı (S:109 Şekil 5.10). Königsberg köprülerinde her köprüden bir kez geçerek bu şehirde bir gezinti yapmak mümkün değildir. Böyle bir gezinti var olsa ve a bölgesinden başlamasa bu gezinti mutlaka a bölgesine uğraması gerekirdi.
Eğer gezintinin bittiği köşe noktası gezintinin başladığı köşe noktasından farklıysa, gezintinin bittiği köşe noktasının derecesi tek sayı olmalıdır Aynı şey gezintinin başladığı köşe noktası için de geçerlidir. Gezintinin başladığı köşe noktası gezintinin bittiği köşe noktasından farklıysa onun da derecesi tek sayı olmalıdır. Eğer gezintinin başladığı köşe noktası ile gezintinin bittiği köşe noktası aynı ise, bu köşeden her çıktığımızda tekrar dönmek zorunda olduğumuzdan bu köşenin de derecesi çift sayı olmalıdır. Yani bu durumda çizgenin tüm köşe noktalarının derecesi çift sayı olur. Bir çizgede her
kenardan bir kez geçen bir gezinti varsa, iki durum söz konusu olabilir: Ya bütün köşe noktalarının derecesi çifttir, ya da sadece iki köşe noktasının derecesi tek olup, diğerlerinin dereceleri çifttir.
Königsberg şehrine karşılık gelen çizgeye göre a köşe noktasının derecesi 5, b köşe noktasının derecesi 3, c köşe noktasının derecesi 3 ve d köşe noktasının da derecesi 3 olur. Derecesi tek sayı olan köşe noktası ya iki tane olmalıydı ya da hiç olmamalıydı. Oysa burada dört köşe noktasının da derecesi tek sayıdır. O zaman bu çizgede dolayısıyla da bu şehirde istenen şekilde bir gezinti yapılamaz.
Düzlemsel Çizgeler
Bir çizge düzlemde kenarları birbiriyle kesişmeyecek şekilde çizilebiliyorsa, bu çizgeye düzlemsel çizge denir.
Düzlemsel tek parça bir çizgede çizgenin düzlemde belirlediği bölgelerin sayısıyla çizgenin köşe noktalarının sayısının toplamı, çizgenin kenar sayısından iki fazla olur. Yani; bölge sayısı + köşe noktalarının sayısı = kenar sayısı +2 eşitliği geçerlidir.
Prizma, piramit gibi hangi konveks çokyüzlü cismi alırsanız alın, yüzlerinin sayısı ile köşelerinin sayısının toplamı ayrıtlarının sayısının iki fazlasını verir. Yani Euler’in formülünü;
“yüzlerin sayısı + köşelerin sayısı = ayrıtların sayısı+2”
Şeklinde de ifade edebiliriz. Futbol topu bir düzgün 20 yüzlünün köşeleri uygun şekilde kesilerek elde edilebilir. Bu durumda 12 düzgün beşgen ve 20 düzgün altıgen ortaya çıkar. Bu cismin 12 + 20 = 32 yüzü olduğunu biliyoruz. Ayrıca 60 köşesi olduğunu bulmak da çok zor değil. Köşeleri tıraşlarken 12 köşenin her biri 5 köşe doğurdu. O zaman Euler formülünden 32+60 = a+2 yazıp, ayrıt sayısının 90 olduğunu bulabiliriz.
Çizgeleri Boyamak
Boyama meselesi çizgelerden önce haritaları boyamak ile başlamış. Bilirsiniz, siyasi haritalarda komşu ülkeler farklı renklerde gösterilir. Francis Guthrie adlı bir matematikçi 1850’li yıllarda haritaların komşu ülkeler farklı renklerde olacak şekilde sadece dört renk kullanılarak boyanabileceği tezini ortaya atmış. Dört Renk Problemi olarak bilinen bu problem uzunca bir süre matematiğin çözülemeyen problemleri arasında kalmış. Ancak 1976 yılında Kenneth Appel ve Wolfgang Haken isimli matematikçiler bilgisayarın da yardımıyla bu iddiayı kanıtladılar.
Bir çizgenin tüm köşe noktalarının derecesi en fazla d ise bu çizgenin köşe noktaları, komşu noktalar farklı renklerde olacak şekilde d + 1 renk ile boyanabilir. Her düzlemsel çizgenin köşe noktaları komşu noktalar farklı renklerde olacak şekilde dört renkle boyanabilir.
Ağaçlar
Tek parça çizgelere agaç denir. Ağaçlar özel tipte çiz- gelerdir. Ağaçlar üzerinde, kenarlar en fazla bir kez kullanarak yapılan gezintilerde başlangıç noktası bitiş noktasıyla aynı olmaz. Yani, gezintiye başladıgınız yere geri dönemezsiniz.
Bir çizgede kullandığı kenarı bir daha kullanmayan ve başladıgı yere geri dönen gezintilere döngü denir. Bu durumda ağaç döngü bulundurmayan tek parça çizge şeklinde tanımlayabilir.
En düşük maliyetli yani optimal ağacı bulmak için Kruskal Algoritması geliştirilmiştir. Bu algoritmaya göre çizgenin hangi kenarının maliyeti en düşük ise önce o kenar eklenir. Sonra yine en ucuz maliyetli kenar çizgeye eklenir. Sonra diğer kenarların en düşük maliyetli olanına bakılır. Eğer bu kenar çizgeye eklendiğinde döngü oluşturmuyorsa, bu kenar da çizgeye eklenir ve bundan sonraki en düşük maliyetli kenara geçilir. Eğer bu kenar çizgeye eklendiğinde döngü oluşturuyorsa bu kenar değil, bu kenar dışındaki en düşük maliyetli kenar eklenerek devam edilir. Belli bir aşamada en düşük maliyetli birden fazla kenar varsa, hangisini seçeceğimiz sonucu etkilemez. Diyelim ki evlerimiz arasına kablo döşeyerek kendimize bir haberleşme ağı oluşturmak istiyoruz. Elbette evlerimizin birbirine olan mesafesi, evlerimiz arasındaki fiziksel engeller vb. bu işin maliyetini etkileyecektir. Kabul edelim ki tüm maliyetleri biliyoruz ve bu maliyetler Tablo 5.2 ile verilmiş olsun. Algoritmaya göre en düşük maliyetli kenarı seçmemiz lazım. O zaman önce g ve m noktaları arasına maliyeti 1 olan kenarı çiziyoruz. Sonra, maliyeti en düşük kenar 2 birim maliyeti olan m ve p noktaları arasındaki kenar. Kalanlar içinde maliyeti en düşük olan kenar g ve p noktaları arasındaki kenar.
Ancak bu kenarı çizersek bir döngü oluşur. O nedenle bu kenarı çizmeyip, m ve s noktaları arasına maliyeti 6 birim olan kenarı çiziyoruz.
Böyle devam edersek optimal ağacı elde ederiz (Şekil 5.43).
Gezgin Satıcı Problemi
Gezgin satıcı probleminde (GSP) amaç, bir satıcının, bulunduğu şehirden başlayıp, her şehre sadece bir kez uğradıktan sonra başladığı şehre geri dönen en kısa turu bulmaktır. Herhangi iki şehir arasında bir yol olduğunu ve o yolun uzunluğunu bildiğimizi varsayıyoruz. GSP, anlaşılması için matematiksel herhangi bir temel gerektirmeyen bir problemdir. Anlaşılması kolaydır ama çözümü zordur!