Çizge teorisi: Revizyonlar arasındaki fark

Vikipedi, özgür ansiklopedi
Etkileşimli olarak geçmişe göz at
[kontrol edilmiş revizyon][kontrol edilmiş revizyon]
← Önceki sürümle aradaki farkSonraki sürümle aradaki fark →
İçerik silindi İçerik eklendi
GörselVikimetin
Gundoganfa (mesaj | katkılar)
Devriyeler
1.205 değişiklik
Hatalı bilgi düzeltmesi ve graf tipleri ile ilgili ekler.
Gundoganfa (mesaj | katkılar)
Devriyeler
1.205 değişiklik
→‎Matematiksel Tanımı: Kuram geçmişindeki königsberg köprüsü ile ilgili ayrıntılar kaldırıldı, bu ayrıntılar zaten königsberg köprüsü başlığı altında detaylı biçimde inceleniyor. Ayrıca başlık düzenlendi.
1. satır: 1. satır:
[[Dosya:6n-graf.svg|thumb|250px|Örnek bir çizge]]
[[Dosya:6n-graf.svg|thumb|250px|Ö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. Matematik ve bilgisayar biliminde kullanılan kuramı bir toplulukta bulunan nesneler arasındaki ilişkileri modelleyen matematiksel yapıları, çizitleri inceler. Bu bağlamda çizit, düğümlerden (köşeler)ve bu köşeleri birbirine bağlayan kenarlardan oluşur.
'''Ç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) oluşur.


Temeli 1736'da '''[[Leonhard Euler]]''' '''(1707-1783)''' tarafından atılan kavram.<ref>{{en}} Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press.</ref>
Temeli 1736'da '''[[Leonhard Euler]]''' '''(1707-1783)''' tarafından atılmıştır.<ref>{{en}} Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press.</ref>


== Geçmiş ==
== Kuramın Tarihçesi ==
[[Dosya:Konigsberg bridges.png|thumb|200px|Königsberg köprüleri sorunu]]
[[Dosya:Konigsberg bridges.png|thumb|200px|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.
[[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ı ==
[[Dosya:Graf ornek.jpg|alt=Solda matematiksel ifadesi bulunan örnek bir graf|thumb|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.
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.
* 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}
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ı.


K = {(A,D), (A,D), (A,B), (A,C), (C,B), (C,D)}
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.


G = (D,K)
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.


Bu örnekte A ve D düğümleri iki adet paralel kenar içerir.
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 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.


== Graf Tipleri ==
== Graf Tipleri ==

Sayfanın 12.30, 10 Ağustos 2015 tarihindeki hâli

Ö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) oluşur.

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

Kuramın Tarihçesi

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ı

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

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

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.

Çizge kuramı soruları

Çizge tabanlı veri yapıları

Kaynakça

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

Dış bağlantılar

"https://tr.wikipedia.org/w/index.php?title=Çizge_teorisi&oldid=15880172" sayfasından alınmıştır