Graf(Çizge) Teorisi - Etkileşimli Öğrenme

Öğren, Pratik Yap, Test Et ve Keşfet

Ön Bilgi: Königsberg Köprü Problemi

Problemin Tanımı

Königsberg (günümüzdeki Kaliningrad), Pregel Nehri'nin etrafına kurulmuş eski bir Prusya şehridir. Nehir, şehrin ortasında Kniephof adında bir ada oluşturur ve şehri dört ana kara parçasına ayırır. 18. yüzyılda bu kara parçalarını birbirine bağlayan yedi köprü bulunmaktaydı.

O dönemde şehir sakinleri arasında popüler olan bir soru ortaya çıktı:

"Bir kişi yürüyüşüne herhangi bir noktadan başlayıp, yedi köprünün her birinden yalnızca bir kere geçerek başladığı noktaya dönebilir mi veya tüm köprüleri geçebilir mi?"

Euler'in Çözümü ve Graf(Çizge) Teorisi

Bu problem, ünlü matematikçi Leonhard Euler tarafından 1736'da çözülmüştür ve bu çalışma graf teorisinin başlangıcı olarak kabul edilir. Euler, problemi soyutlayarak kara parçalarını düğüm (köşe) ve köprüleri de bu düğümleri birleştiren kenar olarak modellemiştir.

Euler, bir grafın tüm kenarlarından tam olarak bir kez geçilip geçilemeyeceğini belirlemek için düğümlerin derecelerini (bir düğüme bağlı kenar sayısını) incelemiştir:

• Euler Devresi (Başlangıç noktasına dönülen yol): Bir graf üzerinde her kenardan tam olarak bir kez geçerek başlanan düğüme geri dönülebilmesi için, grafın tüm düğümlerinin derecesinin çift olması gerekir.
• Euler Yolu (Başlangıç ve bitiş farklı olabilir): Bir graf üzerinde her kenardan tam olarak bir kez geçilebilmesi için (başlangıç ve bitiş düğümleri farklı olabilir), grafın tam olarak iki düğümünün derecesinin tek olması gerekir. Diğer tüm düğümlerin derecesi çift olmalıdır. Tek dereceli düğümler yolun başlangıç ve bitiş noktaları olur.
• Eğer grafın ikiden fazla tek dereceli düğümü varsa, ne Euler Yolu ne de Euler Devresi çizilebilir.

Königsberg Probleminin Çözümü

Yukarıdaki graf gösteriminde Königsberg köprü probleminin düğüm dereceleri şöyledir:

• Sağ Kıyı (A): 3 (Tek)
• Üst Kıyı (B): 3 (Tek)
• Alt Kıyı (C): 3 (Tek)
• Orta Ada (D): 5 (Tek)

Görüldüğü gibi, grafın dört tane tek dereceli düğümü vardır. Euler'in teoremine göre, ikiden fazla tek dereceli düğüm olduğu için Königsberg şehrinde köprülerin her birinden tam olarak bir kez geçerek bir tur atmak mümkün değildir.

Eğer Königsberg'e uygun bir yere bir köprü daha (8. köprü) eklenseydi ve bu sayede tek dereceli düğüm sayısı sıfıra veya ikiye inseydi, o zaman böyle bir yürüyüş mümkün olabilirdi.

Not: Königsberg Köprü Problemi, gerçek dünya problemlerinin matematiksel modelleme (özellikle graf teorisi) ile nasıl çözülebileceğinin harika bir örneğidir.

Graf Teorisine Giriş

Grafın Temel Kavramları

Graflar, farklı noktaları (düğümleri) çizgilerle birleştirerek bir ağ oluşturan matematiksel yapılardır. Bir graf, kenarları kırmadan, azaltmadan veya yeni birleşme noktaları eklemeden hareket ettirilerek manipüle edilir.

Ana Terimler:

• Düğüm (Köşe): Grafın kenarların buluştuğu noktaları.
• Kenar: Düğümleri birleştiren çizgiler.
• Derece: Bir düğüme bağlı kenarların sayısı.

Not: Birden fazla kenarı birleştirmeyen bir kenar üzerindeki bir nokta, düğüm olarak kabul edilmez.

Graf Dönüşümleri

Graflar, temel yapılarını korurken çeşitli şekillerde dönüştürülebilir. Geçerli dönüşümler, kenarları kırmadan veya yeni düğümler oluşturmadan düğümler arasındaki bağlantıları korur.

Geçerli Dönüşüm Örnekleri:

Düzlemsel Graflar

Düzlemsel graflar, kenarların yalnızca düğümlerde kesişmesi dışında hiçbir kenarın kesişmediği şekilde bir düzlem üzerine çizilebilen graflardır. Düğümlerin (\( V \)), kenarların (\( E \)) ve dış bölge dahil bölgelerin (\( R \)) sayısı arasında özel bir ilişki vardır.

Düzlemsel Graflar için Euler Formülü:

\[ V + R = E + 2 \]

Euler Yolu ve Euler Devresi

Graf teorisinde, Euler Yolu ve Euler Devresi, bir grafın kenarlarını belirli kurallara göre dolaşmayı tanımlayan önemli kavramlardır.

• Euler Yolu: Bir grafın her kenarını tam olarak bir kez ziyaret eden bir yoldur. Başlangıç ve bitiş düğümleri farklı olabilir.
• Euler Devresi: Bir Euler Yolu olup aynı zamanda başlangıç ve bitiş düğümünün aynı olduğu bir döngüdür.

Euler Yolu ve Devresi Koşulları:

Euler Yolu ve Euler Devresi’nin varlığı, grafın düğümlerinin derecelerine bağlıdır:

• Euler Devresi için: Grafın tüm düğümlerinin derecesi çift olmalıdır. Bu, her düğümden girip çıkarken kenarların tükenmesini sağlar.
• Euler Yolu için: Grafın tam olarak iki düğümünün derecesi tek olmalı, diğer tüm düğümlerin derecesi ise çift olmalıdır. Tek dereceli düğümler yolun başlangıç ve bitiş noktalarıdır.
• Eğer grafın ikiden fazla düğümünün derecesi tekse, ne Euler Yolu ne de Euler Devresi yoktur.

Örnek Açıklamaları:

• Soldaki Graf: Tüm düğümlerin derecesi 2 (çift). Bu nedenle bir Euler Devresi vardır.
• Sağdaki Graf: İki düğümün derecesi 1 (tek), iki düğümün derecesi 2 (çift). Tam olarak iki tek dereceli düğüm olduğu için Euler Yolu vardır, ancak Euler Devresi yoktur.

Pratik Etkinlikler

Alıştırma 1

Aşağıdaki grafın düğüm ve kenar sayısını bulun.

Düğümler: 3, Kenarlar: 3

Alıştırma 2

Bu grafın bir Euler Yolu var mı?

Evet, var. Dereceler: 2, 2, 2 (hepsi çift, Euler Devresi de var. Euler Devresi olan her grafın Euler Yolu da vardır).

Alıştırma 3

Bu grafın bir Euler Devresi var mı?

Hayır, yok. Dereceler: 2, 1, 1 (iki tane tek dereceli düğüm var, Euler Yolu vardır ama devresi yoktur).

Alıştırma 4

Bu grafın düğümlerinin derecelerini hesaplayın.

Dereceler: Üst Sol (ÜS): 2, Üst Sağ (ÜSa): 2, Orta (O): 3, Alt (A): 1

Alıştırma 5

Bu grafın bir Euler Yolu var mı?

Evet, var. Dereceler: 2, 2, 2 (hepsi çift). Euler devresi olduğu için Euler yolu da vardır.

Alıştırma 6

Bu grafın kenar sayısını bulun.

Kenar sayısı: 5

Alıştırma 7

Bu grafın bir Euler Devresi var mı?

Hayır, yok. Dereceler: 2, 1, 1 (iki tane tek dereceli düğüm var).

Alıştırma 8

Bu grafın düğüm sayısını bulun.

Düğüm sayısı: 4 (Ancak 100,150 koordinatındaki düğümün derecesi 0'dır, yani izole bir düğümdür).

Alıştırma 9

Bu grafın bir Euler Yolu var mı?

Evet, var. Dereceler: 2, 2, 3, 1 (tam olarak iki tek dereceli düğüm var: 3 ve 1).

Alıştırma 10

Bu grafın bir Euler Devresi var mı?

Evet, var. Dereceler: 2, 2, 2, 2 (hepsi çift).

Kendini Test Et

Test: Graf Teorisi Bilgini Ölç

1. Bir grafın tüm düğümlerinin derecesi çift ise ne olur?

2. Bir grafın tam olarak iki düğümünün derecesi tek ise ne olur?

3. Bir grafın düğüm dereceleri 2, 2, 2 ise bu grafın özelliği nedir?

4. Bir grafın düğüm dereceleri 1, 2, 3 ise ne olur?

5. Basit bir grafın kenar sayısı 4, düğüm sayısı 4 ise bir düğümün maksimum derecesi kaç olabilir?

6. Bir grafın düğüm dereceleri 2, 3, 3 ise ne olur?

7. Bir grafın tüm düğümleri izole (derece 0) ise ne olur? (Not: Bağlantılı olmayan bir graf kabul edilir)

8. Bir grafın düğüm dereceleri 1, 1, 2, 2 ise ne olur?

9. Bir grafın kenar sayısı 5, düğüm sayısı 4 ise toplam derece kaçtır? (Handshaking Lemma)

10. Bir grafın düğüm dereceleri 2, 2, 4 ise ne olur?

Ek Bilgi

Tokalaşma Problemi ve Graf Teorisi

Bir gruptaki herkesin birbiriyle tokalaşma sayısını graf teorisi ile bulmak için oldukça basit ve elegant bir yöntem kullanabiliriz. Bu problemi, tam graf (complete graph) olarak modelleyebiliriz. Tam graf, her bir düğümün (kişinin) diğer tüm düğümlere (kişilere) bağlı olduğu bir grafiktir. Burada tokalaşmalar, grafın kenarları (edges) olarak temsil edilir.

Adım Adım Çözüm:

1. Problem Tanımı:
   • Grupta \( n \) kişi olduğunu varsayalım.
   • Herkes birbiriyle bir kez tokalaşıyor (kendisiyle tokalaşmıyor ve aynı kişiler arasında birden fazla tokalaşma yok).
2. Graf Teorisi Modeli:
   • Bu durum, \( K_n \) olarak adlandırılan \( n \) düğümlü bir tam graf ile ifade edilir.
   • \( K_n \) grafında, her bir düğüm diğer \( n-1 \) düğüme bağlıdır.
3. Tokalaşma Sayısı (Kenar Sayısı):
   • Bir tam grafın kenar sayısı, şu formülle hesaplanır:
   • \[ \frac{n (n-1)}{2} \]
4. Neden Bu Formül?:
   • \( n \) kişi varsa, her bir kişi \( n-1 \) kişiyle tokalaşır. Toplamda \( n (n-1) \) tokalaşma olur gibi görünebilir, ama bu hesaplama her tokalaşmayı iki kez sayar (A ile B tokalaşması, hem A’dan B’ye hem B’den A’ya sayılır). Bu yüzden sonucu 2’ye böleriz.

Örnek:

• \( n = 3 \) kişi varsa:

  \[ \text{Tokalaşma Sayısı} = \frac{3 (3-1)}{2} = \frac{3 \cdot 2}{2} = 3 \]

  (Kişiler A, B, C ise: A-B, A-C, B-C tokalaşmaları olur, toplam 3.)

• \( n = 5 \) kişi varsa:

  \[ \text{Tokalaşma Sayısı} = \frac{5 (5-1)}{2} = \frac{5 \cdot 4}{2} = 10 \]

  (5 kişinin her biri diğer 4 kişiyle tokalaşır, çift sayımı düzeltince 10 tokalaşma.)

Genel Formül:

Bir gruptaki \( n \) kişinin birbiriyle tokalaşma sayısı:

\[ \frac{n (n-1)}{2} \]

Bu, graf teorisindeki tam grafın kenar sayısını bulmanın klasik bir uygulamasıdır. Soruda belirli bir \( n \) değeri verilmediyse, bu formülü kullanarak herhangi bir grup büyüklüğü için sonucu hesaplayabilirsin!

\( n = 5 \) için \( K_5 \) Grafı

5 kişinin birbiriyle tokalaşmasını temsil eden \( K_5 \) grafı, 5 düğüm ve 10 kenardan oluşur. Her düğümün derecesi 4’tür çünkü her kişi diğer 4 kişiyle tokalaşır.

Bağlantılar:

• A → B, C, D, E
• B → A, C, D, E
• C → A, B, D, E
• D → A, B, C, E
• E → A, B, C, D

Toplam 10 tokalaşma: A-B, A-C, A-D, A-E, B-C, B-D, B-E, C-D, C-E, D-E.

İnteraktif \( K_n \) Grafı Deneyimi

Aşağıdan \( n \) değerini seçerek \( K_n \) grafını ve tokalaşma sayısını görebilirsiniz (\( n = 2 \) ile \( n = 10 \) arasında):

\( n = 2 \) \( n = 3 \) \( n = 4 \) \( n = 5 \) \( n = 6 \) \( n = 7 \) \( n = 8 \) \( n = 9 \) \( n = 10 \)