Çizge teorisi

Örnek bir çizge

Çizge kuramı (İng: Graph theory), çizgeleri inceleyen matematik dalıdır. Çizge, uçlar ve bu uçları birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır.

Temeli 1736'da Leonhard Euler (1707-1783) tarafından atılan kavram.

Geçmiş

Königsberg köprüleri sorunu

Leonhard Euler tarafından yazılmış bir makalenin 1736 yılında basılması tarihi çizge kuramının kesin başlangıç tarihidir. O makalenin arkasındaki asıl fikir Königsberg'in yedi köprüsü olarak bilinen şimdi popüler olan problemden çıkmış olmasıdır.

Ortaya çıkışının sebebi Königsberg adlı 4 anakaradan oluşan Prusya (Almanya) şehrinde bu 4 anakarayı birbirine bağlayan 7 köprüdür. Şehrin içinden geçen akarsu ve köprüler ilginç bir yapı oluşturmuştur.

Problem şu idi: Herhangi bir anakaradan başlayarak ve bu 7 köprü bir ve sadece bir kere kullanılarak "kapalı bir yürüme", yani tam bir tur gerçekleştirilebilir miydi? Birçok insan bunu deneyerek yapmaya çalışsa da kimse başarılı olamamıştı. Konu üzerine kafa yoran Leonhard Euler, bu problemle ilgili bir makale yayımladı "Seven Bridges of Königsberg". Hatta bu problemi genel bir şekilde inceledi ve bunu teoremlerle kuramlaştırdı.

Euler'e göre bir grafik üzerinde her bir köşe bir ve sadece bir kez kullanılarak kapalı bir tur yapılabilmesi için her köşenin derecesinin çift olması gerekir (köşenin derecesi, komşu köşelerle oluşturduğu kenarların sayısı anlamına gelir). Bundan dolayı bu koşulları sağlayan grafiklere "Euler turu" adı verilmiştir.

Grafik olarak çizilmiş Königsberg 7 köprü probleminde 2 köşenin derecesi tek olduğu için Euler turu olmadığı anlaşılmış ve insanlar da rahatlamıştır.

Euler bu teoremi ortaya attıktan sonra Hierholzer, Fleury gibi matematikçiler Euler turlarında manuel kapalı yürüme bulma algoritmaları geliştirmişlerdir. Bu algoritmaların özyineli (recursive) olması bilgisayarda çok rahat programlanmasını sağlamış ve Euler turu yaratmak kolaylaşmıştır.

Matematiksel Tanımı

Bir G grafiği uçlar kümesi U(C), kenar kümesi K(C) ve bu kenar kümesindeki her kenarın iki uç ile ilişkilerinden oluşur.

Uçları birleştiren kenarların yönleri olabilir. Bu grafiklere yönlü denilir ve "sahte" (pseudo) grafik diye de bilinir.

Tanımlar ve Örnekler

Bir yol haritasını kullandığımız zaman, haritada belirtilen yolların yardımıyla bir şehirden diğer bir şehre nasıl gideceğimize bakarız. Sonuç olarak, biz bu durumda nesnelerin (elemanların) farklı iki kümesi ile ilgileniriz: Şehirler ve yollar. Daha önce gördüğümüz gibi böyle nesnelerin kümeleri bir bağıntı tanımlamak için kullanılabilir. Eğer V kümesi ile şehirler kümesini ve E kümesi ile de yollar kümesini gösterirsek, V kümesi üzerinde yalnız E deki yolları kullanarak a şehrinden (noktasından) b noktasına seyahat edebiliyorsak, aβb yazarak, bir β bağıntısı tanımlayabiliriz. Eğer E deki yollar gidiş-geliş yollar ise bβa da gerçeklenir. Eğer incelememiz altındaki tüm yollar gidiş-gelişli yollar ise bu bağıntı simetriktir. Bir bağıntıyı tanımlamanın bir yolu onun elemanlarını sıralı çiftler olarak listeleyerek vermektir. Burada aşağıdaki şekilde gösterildiği şekilde çizgiler kullanarak yapmak daha uygun olmaktadır.

Dış bağlantılar

• Çizge kuramı