Çizge kuramı

Vikipedi, özgür ansiklopedi
Şuraya atla: kullan, ara
Örnek bir çizge

Çizge kuramı, Graf Teorisi veya Çizit kuramı (ing: Graph theory), çizgeleri inceleyen matematik dalıdır. Çizge, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf veya çizit, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan(yaylardan, bağıntılardan) oluşur.

Temeli 1736'da Leonhard Euler (1707-1783) tarafından atılmıştır.[1]

Kuramın Tarihçesi[değiştir | kaynağı değiştir]

Königsberg köprüleri sorunu

Leonhard Euler tarafından,1736 yılında, Königsberg'in yedi köprüsü (Seven Bridges of Königsberg) adında günümüzde hala popülerliğini koruyan bir problem ile ilgili olarak yazılan bir makale, çizge kuramının kesin başlangıç tarihidir.

Matematiksel Tanımı[değiştir | kaynağı değiştir]

Solda matematiksel ifadesi bulunan örnek bir graf
Solda matematiksel ifadesi bulunan örnek G grafı

Bir G grafı, iki küme ile ifade edilir. G = (D, K)

Bu ifadede D düğümler kümesi, K ise (düğümler ile ilişkili) kenarlar kümesi olarak ifade edilir.

  • Eğer düğümleri birbirine kenarlar için giriş ve çıkış yönleri belirli ise, bu kenarlara yönlü kenarlar denir.
  • Eğer bir düğümden çıkan ve yine aynı düğüme giren bir kenar varsa (örneğin A'den çıkıp A'ya yeniden giren bir kenar), bu bir döngü (loop) olarak ifade edilir.
  • Eğer bir düğümden bir başka düğüme giden aynı yöne sahip veya yönsüz iki adet kenar varsa, bu kenarlara paralel kenarlar denir.

Sağdaki yönsüz, örnek graf için küme gösterimi aşağıdaki şekilde yapılır.

D = {A,B,C,D}

K = {(A,D), (A,D), (A,B), (A,C), (C,B), (C,D)}

G = (D,K)

Bu örnekte A ve D düğümleri iki adet paralel kenar içerir.

Graf Tipleri[değiştir | kaynağı değiştir]

Graf Tipi Kenar Tipi Çoklu Kenara İzin Döngüye İzin?
Basit Graf Yönsüz Hayır Hayır
Çoklu Graf Yönsüz Evet Hayır
Pseudo(Sahte) Graf Yönsüz Evet Evet
Yönlü Graf Yönlü Hayır Evet
Yönlü Çoklu Graf Yönlü Evet Evet

Tanımlar ve Örnekler[değiştir | kaynağı değiştir]

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 iki farklı 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.

Kaynakça[değiştir | kaynağı değiştir]

  1. ^ (İngilizce) Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press.

Dış bağlantılar[değiştir | kaynağı değiştir]