📝 9. Sınıf Matematik: Euler Yolu Ve Hamilton Yolu Ders Notu
Euler Yolu ve Hamilton Yolu 🛤️
Graf teorisi, nesneler arasındaki ilişkileri inceleyen bir matematik dalıdır. Bu ilişkileri incelemek için kullandığımız önemli kavramlardan ikisi Euler yolu ve Hamilton yoludur. Bu iki kavram, bir grafın köşeleri veya kenarları üzerinden belirli kurallara uyarak geçme üzerine kuruludur.
Euler Yolu Nedir?
Bir grafın Euler yolu, grafın tüm kenarlarını tam olarak bir kez kullanarak bir köşeden başlayıp başka bir köşede (veya aynı köşede) biten bir yoldur. Euler yolu için önemli olan, kenarların tamamının kullanılmasıdır. Köşelerin birden fazla ziyaret edilmesi sorun değildir.
Euler Yolu İçin Koşullar
- Bağlı Graf: Euler yolu olabilmesi için grafın bağlı olması gerekir. Yani, grafın herhangi iki köşesi arasında bir yol bulunmalıdır.
- Tek Dereceli Köşe Sayısı:
- Eğer grafın hiç tek dereceli köşesi yoksa (tüm köşelerin derecesi çift ise), graf üzerinde bir Euler devri (başlangıç ve bitiş köşesi aynı olan Euler yolu) vardır.
- Eğer grafın tam olarak iki tek dereceli köşesi varsa, bu iki köşe arasında bir Euler yolu vardır. Bu yol, tek dereceli köşelerden biriyle başlar ve diğeriyle biter.
- Eğer grafın ikiden fazla tek dereceli köşesi varsa, o graf üzerinde bir Euler yolu yoktur.
Köşe derecesi: Bir köşeye bağlı olan kenar sayısıdır.
Euler Yolu Örneği
Aşağıdaki grafı inceleyelim:
- Köşe A: Derecesi 3 (tek)
- Köşe B: Derecesi 4 (çift)
- Köşe C: Derecesi 3 (tek)
- Köşe D: Derecesi 2 (çift)
Bu grafın A ve C olmak üzere tam olarak iki tek dereceli köşesi vardır. Bu nedenle, bu graf üzerinde bir Euler yolu vardır ve bu yol A'dan başlayıp C'de bitebilir veya C'den başlayıp A'da bitebilir. Örneğin: A -> B -> C -> D -> B -> A -> C. Bu yol, tüm kenarları tam olarak bir kez kullanır.
Hamilton Yolu Nedir?
Bir grafın Hamilton yolu, grafın tüm köşelerini tam olarak bir kez kullanarak bir köşeden başlayıp başka bir köşede (veya aynı köşede) biten bir yoldur. Hamilton yolu için önemli olan, köşelerin tamamının ziyaret edilmesidir. Kenarların birden fazla kullanılması veya bazı kenarların hiç kullanılmaması sorun değildir.
Hamilton Yolu İçin Koşullar
Hamilton yolu veya devri için Euler yolu kadar kesin ve basit koşullar yoktur. Bir grafın Hamilton yolu olup olmadığını belirlemek genellikle daha zordur ve özel algoritmalar gerektirir. Ancak bazı genel gözlemler yapılabilir:
- Bağlı Graf: Hamilton yolu için de grafın bağlı olması gerekir.
- Köşe Sayısı: Grafın en az 3 köşesi olmalıdır.
Dirac Teoremi ve Ore Teoremi gibi teoremler, bazı koşullar altında grafın Hamilton yolu veya devri olacağını garanti eder, ancak bu teoremler 9. sınıf müfredatı kapsamında değildir.
Hamilton Yolu Örneği
Yukarıdaki grafı tekrar ele alalım:
- Köşeler: A, B, C, D
Bu graf üzerinde bir Hamilton yolu bulmaya çalışalım. Tüm köşeleri tam olarak bir kez ziyaret etmeliyiz.
Örnek bir Hamilton yolu: D -> C -> A -> B. Bu yol, tüm köşeleri (D, C, A, B) tam olarak bir kez ziyaret eder.
Eğer başlangıç ve bitiş köşesi aynı olsaydı (D -> C -> A -> B -> D), bu bir Hamilton devri olurdu. Ancak bu grafın bir Hamilton devri yoktur çünkü B köşesinden tekrar D'ye dönmek için kullanılan bir kenar yoktur ve tüm köşeleri tam bir turda ziyaret edemeyiz.
Euler Yolu ve Hamilton Yolu Arasındaki Farklar
En temel fark, neyin tam olarak bir kez kullanılacağıdır:
- Euler Yolu: Tüm kenarları tam olarak bir kez kullanır.
- Hamilton Yolu: Tüm köşeleri tam olarak bir kez kullanır.
Euler yolu varlığını belirlemek için köşelerin derecelerine bakmak yeterliyken, Hamilton yolu varlığını belirlemek daha karmaşıktır.
Günlük Yaşamdan Örnekler
- Euler Yolu: Bir posta dağıtıcısının tüm sokakları (kenarları) tam olarak bir kez kullanarak bir rotayı tamamlaması, bir kar küreme aracının tüm yolları (kenarları) tam olarak bir kez temizlemesi gibi durumlar Euler yolu mantığına uyar.
- Hamilton Yolu: Bir kuryenin, teslimat yapacağı tüm evlere (köşelere) uğrayarak en kısa rotayı bulmaya çalışması, bir turistin bir dizi şehri (köşeleri) tam olarak bir kez ziyaret ederek bir gezi planlaması Hamilton yolu mantığına örnektir.
Çözümlü Örnek
Aşağıdaki grafı inceleyelim:
- Köşeler: P, Q, R, S
- Kenarlar: PQ, PR, PS, QR, QS, RS
Bu graf, tam bir graf (K4) olarak bilinir, yani her köşe diğer her köşe ile bir kenarla bağlıdır.
Soru 1: Bu grafın bir Euler yolu var mıdır? Varsa, bir örneğini yazınız.
Çözüm 1:
- Köşe P: Derecesi 3 (tek)
- Köşe Q: Derecesi 3 (tek)
- Köşe R: Derecesi 3 (tek)
- Köşe S: Derecesi 3 (tek)
Soru 2: Bu grafın bir Hamilton yolu var mıdır? Varsa, bir örneğini yazınız.
Çözüm 2: Bu grafın tüm köşelerini tam olarak bir kez ziyaret eden birçok yol vardır. Örneğin: P -> Q -> R -> S. Bu yol, P, Q, R ve S köşelerini tam olarak bir kez kullanır. Dolayısıyla bir Hamilton yoludur.