Graf Teorisi Nedir

3
43008
graf teorisi

Graf teorisi ve elini kaldırmadan çizmeyi birçoğumuz ilkokul yıllarımızda karşılaşmışızdır. Ya arkadaşlarımız bizlere yada bizler onlara resimdeki şekli hiç el kaldırmadan çizip çizemeyeceğini sormuşuzdur ve hepimiz birkaç denemeden sonra sonucuna ulaşmışızdır. Ancak hiçbirimiz bunun aslında çok basit bir Matematik problemi olduğu bilmiyorduk.

Problemin aslı 1700′ lü yılların meşhur problemi olan “Königsberg’in 7 köprüsü” problemidir. Königsberg şehri Pregel nehrinin kıyısına kurulmuş ve 7 ayrı köprü ile birbirine bağlanmış 4 farklı bölümden oluşmaktadır (Resimde görüldüğü üzere).

Königsberg' in 7 köprüsü

Zamanla insanlar kendilerine, aynı köprüden bir kez daha geçmemek üzere tüm şehri dolaşmanın mümkün olup olmadığı sorusunu sormuşlardır. Ancak hiç kimse böyle bir rota çizemedi, dönemin meşhur matematikçilerinden biri olan Leonhard Euler’ de dahil, fakat Euler bunun neden mümkün olamayacağını ispatlayabilmiştir.

Euler problemin ispatı için şekli daha basit bir hale getirmiştir, bunun için köprüleri çizgiler ve şehir parçalarınıda noktalar halinde ifade etmiştir. Bunun sonucu olarak aşağıdaki şekil ortaya çıkmıştır.

Leonhard Euler

Resimden sadece çizgi ve noktaları alacak olursak:

graf teorisi örnekEuler böyle bir gezinin mümkün olabilmesi için her noktada buluşan çizgilerin toplam sayısının çift rakam olması gerektiği kanısına varmıştır. Bu sayede bir noktaya ulaşmak için köprülerden birisi, çıkmak içinse diğeri kullanılacaktı. Ancak ortada bir istisna vardı, başlangıç ve bitiş noktaları. Başlangıç ve bitiş noktalarının farklı olduğu durumlarda bu iki noktanın sadece tek bir çizgi ile diğer noktalara bağlı olması gerekiyordu. Başlangıç ve bitiş noktalarının aynı olduğu durumlarda ise her noktanın çift sayıda köprüye ihtiyacı vardır. Bütün bu düşünceler ışığında Euler genel bir teoremi ortaya çıkartmıştır. Bu teoreme göre böyle bir gezintiyi mümkün kılabilmek için sistemdeki her bir noktaya ulaşan toplam çizgi saysının çift olması yada en fazla iki noktaya ulaşan toplam çizgi sayısının tek olması zorunluydu.

Königsberg problemiBu teoremi Königsberg problemine uygulayan Euler A noktasına toplam 3, B noktasına 5, C noktasına 3 ve D noktasına toplamda 3 köprü ulaştığını görmüş ve teoremine göre böyle bir gezinin imkansız olduğunu kanıtlamıştır.

Bizler de Euler teoremini ilkokul yıllarımızın bulmacasına uyguladığımız zaman şeklin gerçekten de hiç el kaldırılmadan çizilebildiğini ispatlayabiliriz.

Euler teoremi

Resimde görüldüğü üzere A noktasına toplam 2, B noktasına 4, C noktasına 3, D noktasına 3 ve E noktasına 4 çizgi ulaşmaktadır. Euler teoremine göre sistemde en fazla 2 noktaya ulaşan çizgi sayısının tek, geri kalanların çift yada tüm noktalara ulaşan çizgi sayısının çift  olması gerekmekteydi. Bizim sistemimiz bu teoreme uygun olduğu için, şeklin hiç el kaldırılmadan çizilebileceğini ispatlamış olduk.

Sizlerde bu teoremi kullanarak aşağıdaki şekillerin hiç el kaldırmadan çizilip çizilemeyeceğinin ispatını yapabilirsiniz.

Paylaşır mısınız?
Önceki İçerikNükleer Pil Projesi
Sonraki İçerikPiezoelektrik Seramik Nedir
Merhabalar. İsmim Ali Çevik ve 22 yaşındayım. Almanyada RWTH-Aachen Üniversitesinde bilgisayar bilimleri öğrencisiyim. İyi derecede Almanca ve orta derece İngilizce bilmekteyim. Hobi olarak yaptığım aktiviteler piyano çalmak, müzik dinlemek, ufak çaplı oyunlar ve yazılımlar üretmek/geliştirmek ve IT-Kitapları okumak.

3 Yorum

    • Şekildeki altıgen maalesef el kaldırmadan çizilemiyor bunun sebebi noktalarda buluşan çizgi sayısına baktığınız zaman 2 den fazla tek sayılı noktanın olması. Ancak altıgenin ortasındaki çizgileri kaldıracak olursak yani hepimizin bildiği sade altıgene bakacak olursak el kaldırmadan çizmenin mümkün olduğunu görebilirsiniz.

Düşünceleriniz Nedir?