Projenin Adı: EULER`İN YOLU İSTANBUL`A DÜŞERSE Projenin

Projenin Adı: EULER’İN YOLU İSTANBUL’A DÜŞERSE
Projenin Amacı: Çizge kuramının başlangıç noktası kabul edilen Königsberg köprüsü
probleminden hareketle İstanbul ve Königsberg şehirleri arasında analoji kurulmuştur.
İstanbul’a gelen bir turistin boğaz köprüsü ve haliç köprülerinden en az bir kere geçerek
görülmesi gereken önemli mekanlara gidebilecekleri en uygun turun hesaplanması
amaçlanmıştır. Ele alınan problemin çözüm yöntemleri gerçek hayatta mektup dağıtımı, yol
bakımı atık veya çöp toplama işlemleri kar temizleme çalışmaları elektrik sayaçlarının
okunması polis devriye araçlarının rotalarının belirlenmesi ve otobüs çizelgelemesi gibi geniş
uygulama alanlarına sahiptir ve ekonomiye olumlu katkı sağlamaktadır. Ülkemizdeki
kurumlarca bu olumlu etki göz ardı edilmektedir. Bu çalışmada bir problem ele alınarak
çeşitli modellemeler için örnek tescil etmesi amaçlanmıştır.
GİRİŞ:
GRAF TEORİSİ
Günlük hayatta birçok problemin çözümü için kullanılan graflar ekonomi yönetim bilimi
bilgi iletimi gibi birçok alanı kapsamaktadır. Graf teorisi problemleri tanımlamada ve ilişkileri
belirlemekte oldukça faydalıdır.
-
Graf, noktalar yani diğer bir değişle düğümler ve bu noktaları birleştiren çizgiler yani ayrıtlar
topluluğudur. Graf Teori’sinde
’deki diyagrama bakılınca
noktalara düğüm (vertex) olarak adlandırılırken
düğümleri bileştiren
diyagram için
kümesini ifade eder.
düğümler kümesi ve
kenarları da ayrıt (vertices) olarak adlandırılır. Bu
düğümler kümesini ve
ayrıtlar
ayrıtlar kümesi olmak üzere
bir graf belirtir.
Bir ayrıt her iki ucunda da bir düğüm olacak şekilde tanımlandığından graftaki tüm
ayrıtların uç noktalarını bir düğüm ile ilişkilendirmek gerekir. Bu nedenle, her bir ayrıtı için
kümesi tanımlanır ve
şeklinde gösterilir. Bunun anlamı ayrıt’ının ve
düğümlerini bağladığıdır. Ayrıca belirtilmesi gerekir ki
olabilir.
Başlangıç ve bitiş noktası aynı olan ayrıtlara çevrim (loops) denir. (Yani;
dumrumunun gerçeklenmesidir). Örnek olarak
- ’deki
bağlantısı
verilebilir.
Bir düğüm çifti iki veya daha fazla kenar ile bağlanmış ise bu kenarlara paralel kenarlar
denir.
- ’ deki A ve B düğümlerini birleştiren iki ayrıt paralel ayrıta örnek verilebilir.
Bir yönsüz (undirected)
i) boş olmayan sonlu bir
(ii) bir
alt kümesidir
grafı şunlardan oluşur:
düğümler kümesi ve sonlu bir
fonksiyonu öyle ki her bir e ayrıtı için
Şekil-3
ayrıtlar kümesi ve
‘nin bir veya iki elemanlı bir
- ’deki
grafına bakalım. Açıktır ki
olduğuna göre
grafı için
ve
fonksiyonu şöyle tanımlanmaktadır:
Graf ile onu temsil eden diyagram aynı değildir. erilen bir graf birbirinden çok farklı
görünen iki graf ile gösterilebilir. Örneğin;
- ve
- ‘deki iki diyagram çok farklı
görünmelerine rağmen aynı grafını temsil ederler.
-
-
Paralel ayrıt ve çevrim içermeyen graflara basit (simple) graf denir. (
Paralel kenarı olan ve çevrim içermeyen graflara çoklu (multi)
graf denir.
-
Pseudo Graf paralel kenarı olan ve çevrim içeren graflardır.
-
-
-
-
-
Eğer düğümlü bir basit grafta her bir düğüm çifti arasında bir ayrıt var ise buna tam
(complete) graf denir ve
ile gösterilir
.
-
Yönsüz bir grafta ve düğüm çiftini bağlayan bir ayrıt’ ı varsa bu iki düğüm
kom udur (adjacent) denir.
Yönsüz bir grafta bir düğümünün derecesi (degree): düğümüne bağlı olan ayrıtların
sayısıdır ve
şeklinde gösterilir. Aksi belirtilmediği sürece çevrim içeren düğümler
derecesini iki arttırır.)
- için:
,
,
,
Tüm düğümleri aynı derecesine sahip grafa dereceli düzenli (regular) graf denir.
Düğümlerin dereceleri ile ilgili iki önemli teorem vardır:
El Sıkı ma Teoremi: (Handshaking Theorem):
graf olsun. Bu durumda;
m tane ayrıta sahip olan yönsüz bir
eşitliği gerçeklenir.
Teorem: Yönsüz bir
grafında derecesi tek olan düğümlerin sayısı çifttir.
İspat:
, m tane ayrıta sahip olan yönsüz bir graf olsun. derecesi çift olan düğümlerin
kümesini ve
derecesi tek olan düğümlerin kümesini temsil etsin. El Sıkışma Teorem’ini
kullanarak;
eşitliğini yazabiliriz. Eşitliğin sol tarafında
bulunduğuna göre derecesi tek olan düğümler
ile derecesi çift olan düğümlerin sayısının toplamı çift bir sayıya eşittir.
derecesi çift olan ayrıtların kümesi olduğundan
için
çift bir sayıdır bu
durum eşitliğin ilk terimini çift yapar. Çift bir sayıyı ancak ve ancak çift bir sayı ile toplarsak
sonucu çift olabileceğini biliyoruz).Bu durumda birinci terim çift bir sayı olduğuna göre ve
eşitliğin sol tarafının da çift olduğunu bildiğimize göre ikinci terimi de yani derecesi tek olan
düğümlerin sayısının toplamı) çift olmak zorundadır. Sonuç olarak derecesi tek olan
düğümlerin sayısı çift olur.
Yol:
(i)
grafında uzunluğunda ayrıt dizisi;
için ve
komşu
olmak üzere
ayrıtlarının dizisidir. Ayrıt dizisi
olmak
üzere
düğüm dizisini belirler. ’a ilk düğüm, ‘e son düğüm
denir.
(ii)
Bir grafta,
düğümü arasındaki bir yol (path), düğümlerin
şeklindeki ayrıtların sonlu bir dizisidir. Burada,
ve
düğümleri arasındaki ayrıttır. Yani bir yolda aynı bir ayrıttan birden fazla
geçilmeye izin verilmez.
Kapalı Yol:
yollardır.
ve
ise ayrıt dizisi kapalıdır. Yani başlangıç ve bitiş noktaları aynı olan
Basit Yol: Aynı düğümü birden fazla ziyaret etmiyorsak bu yola basit yol denir.
Devre(circuit): En az bir ayrıt içeren basit ve kapalı bir yola devre circuit) denir.
-
Bağlantılı Graf: Herhangi düğüm çiftinin arasında bir yol olan graflara bağlantılı connected)
ya da bağlı graf denir.
-
Şekil-11
Ağaçlar
Tanım: İçinde devre circuit) içermeyen yönsüz bağlı graflara ağaç (tree) denir.
-
)
Tanımdan da açıkça görüldüğü gibi bir ağaçta çevrim veya paralel ayrıt yoktur. Herhangi bir
çevrim loop) kendi başına bir devredir ve ve aynı düğüm çiftinin bağlıyorsa , dizisi de
bir devredir.
Ağaçların
zellikleri
* düğümlü bir ağacın tam olarak
ayrıtı vardır.
Bir yönsüz graf ancak ve ancak herhangi iki düğümü arasında tek bir basit yol var ise bir
ağaçtır.
Ağaçların graf teorisinde önemli olmasının bir nedeni tüm bağlı grafların bir ağaç
içermesindendir. Buna kapsayan ağaç(spanning tree) denir ve bütün düğümleri bağlar.
Bir ayrıt dizisi grafın diyagramında kalemi k ğıdın üzerinden kaldırmadan çizebileceğimiz
herhangi sonlu ayrıt dizisidir. Ayrıtlar tekrar edilebilir veya çevrimler tekrarlanabilir. Ayrıt
dizileri çok genel olduklarından kullanıma uygun değillerdir ve bu yüzden yollar
tanımlanmıştır. Bir yolda aynı ayrıttan birden fazla geçmeye izin verilmez.
Hamilton Devreleri (Hamiltonian Circuits)
Benzer bir problem de herhangi bir ayrıttan birden fazla geçmemek kaydıyla her bir
düğümü sadece bir kez ziyaret edip başladığımız yere geri dönebilir miyiz Şeklinde
sorulabilir. Bu problem Hamilton tarafından irdelenmiştir ve ismi bu yollar ile birlikte
anılmaktadır.
Hamilton Yolu: Eğer bir grafta her bir düğümden sadece bir kere geçilen bir yol varsa iki
düğüm arasındaki yola, Hamilton yolu denir.
Hamilton Devresi: Her bir düğümden tam olarak bir kere geçen ve tüm ayrıtların farklı
olduğu bir kapalı yol Hamilton devresidir. (cycle)
Bir graftaki Hamilton devresi tüm düğümlerden bir kez geçen kapalı bir yol olduğu için aynı
ayrıttan birden fazla geçmeye izin vermez.
Hamilton Graf: Hamilton devresi içeren graflara Hamilton Graf denir.
-
-
Königsberg ve Euler
18. yüzyılın ortalarında Königsberg şehri Pregel nehrinin iki yakası ve nehirdeki iki ada
üzerine kurulmuştu. Bu adalardan büyük olanı şehrin iki yakasına ikişer köprü diğeri de birer
köprü ile bağlanmıştı. Ayrıca iki ada
arasında da bir köprü bulunmaktaydı.
Şehir sakinlerinin cevaplandırmaya
çalıştığı bir soru vardı: Her hangi bir
noktadan harekete başlayıp yedi
köprünün hepsinden bir ve yalnız bir
kez geçip şehrin bütün bölümlerini
dolaştıktan sonra başlangıç noktasına varılabilir mi Bu problemin çözümü olmadığı
Leonhard Euler (1707-1783) tarafından gösterildi. Euler problemi üzerinde daha rahatça
oynayabilecek bir şekille temsil ederek işe başladı. Şehrin dört bölümü birer nokta ve köprüler
de bu noktaları bağlayan eğri parçaları ile gösterilirse probleme ait şekil şöyle olur;
-14
Elbette bu şekli problemin özelliklerini bozmadan aşağıdaki şekil gibi de çizebilirdik.
-15
Şehirleri temsil eden noktalara düğüm köprülere tekabül eden eğri parçalarına da kiriş
adını verelim. Königsberg köprüleri problemi bu çizdiğimiz şekiller dilinde şu hali aldı: Her
hangi bir düğüm noktasından harekete başlayıp bütün kirişlerden bir ve yalnız bir defa
geçerek bütün düğümleri ziyaret ettikten sonra başlangıç düğümüne varabilir miyiz
Böyle bir gezintinin imkansızlığını göstermeden önce bir iki tanım daha yapalım. Her
kirişin iki ucunda birer düğüm bulunmaktadır. Bu düğümlere o kirişin uçları denebilir.
Aralarında en az) bir kiriş bulunan iki düğüme komşu düğümler ve ortak bir ucu bulunan iki
kirişe de komşu kirişler diyelim. Bir düğümü uç kabul eden kirişlerin sayısı uğraştığımız
problemde ve bir çok tartışmada önemli rol oynamaktadır. Bu sebeple bu sayıya da bir isim
vermek yerinde olur. Buna yerel) derece diyeceğiz. Bu tanımlardan sonra probleme
dönmeden önce bir gözlemde bulunalım. Sadece Königsberg köprüleri problemi için
çizdiğimiz şekilde değil düğümler ve kirişlerden oluşan benzer herhangi bir şekilde bir
düğümden başlayıp bütün kirişleri bir ve yalnız bir defa kullanarak ve bütün düğümleri ziyaret
edip başlangıç noktasına varmak istediğimizi düşünelim. Derecesi tek olan bir düğüm
başlangıç düğümü olamaz zira buna bağlı kirişlerden birisi harekete başlarken çıkış kirişi
olarak kullanılacaktır geriye bu düğüme bağlı çift sayıda kullanılmamış kiriş kalacaktır. Bu
düğümü ikinci kez ziyaret ettiğimizde buna varmak için bir kiriş daha kullanılmış
olacağından geriye tek sayıda yani en az 1) kiriş kalacaktır demek ki bu düğüm hareketin
biteceği nokta olamaz.
ÇİNLİ POSTACI PROBLEMİ
Rotalama problemleri düğüm rotalama problemleri ve ayrıt rotalama problemleri olmak
üzere ikiye ayrılır. Bu problem tiplerinden ilki bir çizgeni düğümlerini ikincisi ise ayrıtlarını
ele alır. Ayrıt rotalama problemlerinde amaç bir çizge üzerinde yer alan tüm ayrıtlardan en az
bir kere geçerek başlangıç düğümüne dönen kısa rota veya rotaları belirlemektir. Ayrıt
rotalama problemleri de kırsal postacı problemi rural postman problem/KPP) ve Çinli
postacı problemi Chinese postman problem/CPP) olmak üzere ikiye ayrılabilir. Kırsal postacı
probleminde bir çizge üzerinde yer alan belirli ayrıtlardan en az bir kez geçilerek Çinli
postacı probleminde ise çizgedeki her ayrıttan en az bir kez geçilerek en kısa turun
oluşturulması istenir.
Çinli postacı problemi ilk olarak 1962 yılında Çinli bir matematikçi olan Mei-Ko Kwan
tarafından incelenmiştir. Problem bir postacının postaneden aldığı mektupları mümkün
olan en kısa yoldan şehirdeki tüm sokaklara uğrayarak dağıtmak istemesiyle ortaya çıkmıştır.
Mektupların dağıtımından sonra postacı başladığı düğüm olan postaneye geri dönmek
zorundadır.
Çinli postacı probleminde bir çizgenin düğümleri yerine bu düğümleri birbirine bağlayan
ayrıtlardan geçilmesi ve bunun da en az bir kez gerçekleşmesi şartıdır. Çinli postacı
probleminin çizgesinde eğer bir Euler tur elde edilemiyorsa turun tamamlanabilmesi için
ayrıtlardan birden fazla geçilmesi gerekmektedir.
Çinli postacı problemi 8 alt başlık halinde incelenir.
1) Yönsüz Çinli postacı problemi Undirected Chinese postman problem)
2) Yönlü Çinli postacı problemi Directed Chinese postman problem)
3) Karma Çinli postacı problemi Mixed Chinese postman problem)
4) k-Çinli postacı problemi k-Chinese postman problem)
5) Min-Max k-Çinli postacı problemi Min-Max k-Chinese postman problem)
6) Hızlı Çinli postacı problemi Windy Chinese postman problem)
7) Hiyerarşik Çinli postacı problemi (Hierarchical Chinese postman problem)
8) Kapasite Kısıtlı Çinli postacı problemi Capacitated Chinese postman problem)
Bu çalışmada yönsüz Çinli postacı problemi ele alınmaktadır.
Yönsüz Çinli Postacı Problemi
Yönsüz Çinli postacı probleminde yönsüz bir çizge üzerindeki her bir ayrıta en az bir kez
uğrayarak başlanılan düğüme geri dönmek koşuluyla en kısa yolun bulunması istenir.
Yönsüz Çinli postacı problemi, yönlü Çinli postacı probleminden biraz
daha karmaşıktır. Problemin G çizgesi bir Euler çizge ise problem Euler tur bulunarak
çözülebilir. Tur tekrarlanan ayrıt deadheading) olmadan tamamlanabilir. Ancak G
bir Euler çizge değil ise o zaman tekrarlanan ayrıtların toplam uzunluğu en kısa mesafeli
eşleştirme minimum-length matching) yönteminin probleme uygulanması ile en
küçüklenmeye çalışılır. Tekrarlanan ayrıtların toplam uzunluğunun en küçüklenmesi
problemin en iyi sonucunu verir.
Şekil 16’da yönsüz CPP’nin çözümüne 1-2-3-4-5-3-5-2-1-5-6-1) ilişkin bir örnek verilmiştir.
-16
Şekil 17’de ise yönsüz CPP’ ne ilişkin başka bir çizgeye yer verilmiştir.
-17
En Kısa Mesafeli E le tirme Yöntemi
Bir Çinli postacı probleminin çözümü için bu problemin çizgesindeki herhangi bir x
düğümü tek dereceli ise x düğümüne bağlı en az bir ayrıt tekrarlanmalıdır. Bu ayrıtların
tekrarlanmasıyla çizgedeki tüm düğümler çift dereceli even degree) olabilmektedir.
Tekrarlanacak ayrıtları belirlemek için en kısa mesafeli eşleştirme yönteminden yararlanılır.
En kısa mesafeli eşleştirme yönteminin yönsüz Çinli postacı probleminin çözümü için etkin
bir algoritma olarak kullanılması ilk defa Edmonds ve Johnson tarafından 1973 yılında
gerçekleştirilmiştir. Bu yöntemde ilk önce çizge G’deki tek dereceli düğümler tespit edilir.
Sonra bir G´=(V´, E´) çizgesi kurulur. Bu G´çizgesindeki düğümler kümesi G çizgesindeki
tüm tek dereceli düğümleri ayrıtlar kümesi ise bu tek dereceli düğümleri birbirine bağlayan
ayrıtları içermektedir. Burada amaç oluşturulan G´çizgesinde yer alan tek dereceli
düğümlerin olası eşleştirilmiş çiftlerini ve bunların arasındaki en kısa uzunluğu saptamaktır.
Bunun gerçekleştirilebilmesi için G´çizgesi çift sayıda tek dereceli düğüme 2n) sahip
olmalıdır. Böylece her bir tek dereceli düğüm çifti yine G´çizgesinde yer alan bir ayrıtla bağlı
olduğu için n sayıda düğüm çifti eşleştirilebilir. Bir tek dereceli düğümden diğer bir tek
dereceli düğüme doğrudan giden yeni bir yolun kurulması da akla gelebilir. Ancak bu gerçek
hayatta yeni bir yolun veya köprünün kurulması anlamına gelir. Böyle bir yol veya köprünün
kurulması ise çok maliyetli veya imkansız olabilir. Bu nedenle yeni bir yol kurmak yerine
mevcut yollar dikkate alınarak en az maliyetli ya da en kısa uzunluklu yollar bulunmaya
çalışılır. Tek dereceli düğümler en kısa uzunluk dikkate alınarak eşleştirildiğinde bunlar
arasındaki en kısa yollar tekrarlanacak ayrıtları kapsayacaktır.
Şekil-18
Şekil 18’de bir yönsüz Çinli postacı problemi yer almaktadır. Bu problemin çizgesi olan G’de
A B C ve D düğümleri tek derecelidir. Bu tek dereceli düğümleri ve onları birbirine
bağlayan ayrıtları gösteren G´çizgesi ise Şekil-19 ’da verilmiştir. Burada dört tane tek dereceli
düğüm ile iki tane eşleştirilmiş düğüm çifti n=2) vardır ve üç olası eşleştirme yapmak
mümkündür.
-19. Şekil 18’deki Çinli Postacı Probleminin G´ Çizgesi
Aşağıda G´çizgesindeki tüm ayrıtlar için en kısa mesafeli eşleştirme yöntemi kullanılarak
yapılan eşleştirmeler verilmektedir:
Eşleştirme
Mesafe
(A,B) (C,D)
5+3=8
(A,C) (B,D)
2+4=6
(A,D) (B,C)
3+2=5*
Burada en kısa mesafeli eşleştirme A D) ve B C) ayrıtları arasında ortaya çıkmaktadır.
Postacının tekrar edeceği yollar A’dan D’ye en kısa yol A D ayrıtı) ve B’den C’ye en kısa
yol (B,C ayrıtı) şeklindedir. Şekil 20’deki G çizgesinde A D) ve B C) ayrıtlarının
birer kopyası görülmektedir. Çizgedeki tüm düğümler çift dereceli hale dönüşmüştür. En
iyi rotayı bulmaya çalıştığımız Şekil 18’deki orijinal çizge için artık yeni oluşan G çizgesine
bakılarak en az bir Euler tur oluşturulabilir. Bu oluşturulan Euler tur aynı zamanda
en iyi rotayı verir. Oluşan en iyi rota ise şöyledir { A E) E D) D F) F A) A B) B D)
D C) C B) B C) C A) A D) D A)}. Buna göre G çizgesindeki her bir ayrıttan tam
olarak bir kez ve G çizgesindeki her bir ayrıttan en az bir kez geçilmiştir. G çizgesinde
sadece A D) ve B C) ayrıtları tekrarlanmıştır. Sonuç olarak bu rotanın toplam uzunluğu
birimdir. Bu uzunluk G çizgesindeki her bir ayrıtın yalnız bir kez
geçilmesiyle bulunan toplam uzunluktan 5 birim fazladır.
-20: Şekil 18daki Çinli Postacı Probleminin G Çizgesi
SERBEST SATICI PROBLEMİ
Serbest Satıcı Problemi İngiltere’nin Armbridge köyünde yaşayan ve civar kasabalara
mallarını satmak isteyen bir seyyar satıcının bu kasabaları mümkün olan en kısa şekilde ve
her bir kasabaya sadece bir kere uğrayarak başladığı yere geri dönmek istemesidir.
İki çeşit serbest satıcı problemi vardır:
1) Pratik Gezgin Satıcı Problemi: Gezgin Satıcı Problemi’nin bu çeşidinde her kasabaya
sadece bir kez uğrama koşulu ile en kısa rotadan gidildiği takdirde aynı yoldan tekrar
geçmek umursanmamıştır.
2) Klasik Gezgin Satıcı Problemi: Her kasabaya sadece bir kez uğrama ve aynı yol
üzerinden tekrar geçmeme koşulları ile en kısa rotayı bulmak amaçlanmıştır.
Bu çalışmada Klasik Serbest Satıcı Problemi ele alınacaktır.
Klasik Serbest Satıcı Problemi
Her düğümden sadece bir kez geçilerek ve kullanılan ayrıtı bir daha kullanmamak şartıyla
başlanılan düğüme geri dönen en kısa yolun bulunması istenir.
Her bir düğümden sadece bir kez geçen ve geçtiği ayrıtı bir daha kullanmayan kapalı
yolların Hamilton devresi olduğundan daha önce bahsedildi. Bu durumda klasik serbest satıcı
problemi için aradığımız rota en kısa Hamilton devresidir .
Problemi çözmek için sağlanması gereken şartlar:
Her tam complete) graf bir Hamilton devresi içerdiğinden problemin çözümde tam graf
kullanmak,
Ayrıtların uzunlukları üçgen eşitsizliğini doğrulamasıdır.
Üçgen E itsizliği:
- ’deki
üçgeninde
eşitsizliğinin sağlanmasıdır.
ayrıt kümesindeki her düğüm için:
Serbest satıcı problemi kolay görünmesine rağmen hızlı ve etkili bir çözüm için bilinen bir
algoritma yoktur. erilen şartlarda en kısa rotayı bulmak için tüm olası yolları eksiksiz
listeleyerek çözüme ulaşmayı amaçlayan algoritmadaki adımlar:
Adım : Tüm Hamilton devrelerini lisetelenir
Adım : Her Hamilton devresinin için toplam mesafe bulunur
Adım : En kısa mesafe seçilip bu mesafe aranan rota olarak belirlenir.
- ’ deki tam graf için bu yöntem kullanılmaya çalışılırsa tüm Hamilton yolları
aşağıda verilmiştir.
Görüldüğü üzere 24 tane devre çıkmaktadır. Bu devrelerin uzunluklarını hesaplamak
oldukça meşakkatli bir iştir. Kenar sayısı daha fazla olan tam graflarda iş daha da
zorlaşmaktadır. Bu yöntem kullanışlı olmadığından daha iyileştirilmiş yöntemlere başvurulur.
Bu çalışmada en kısa mesafeli Hamilton devresini bulmak için üst sınır ve alt sınır bulma
yöntemi kullanılacaktır.
Üst Sınır: Bir kümedeki her elemandan büyük olan değerlere üst sınır denir. Bir
için
için
ise ’e kümesinin üst sınırı denir.
Alt sınır: Bir kümedeki her elemandan küçük değerlere alt sınır denir. Bir
için
ise ’e kümesinin alt sınırı denir.
kümesi
kümesi için
Açıktır ki bulunan üst sınırların en küçüğünü ve alt sınırların en büyüğünün alınması daha
kesin sonuçlara ulaşmayı sağlar. En kısa mesafeli Hamilton devresi bu sınırların arasında yer
alacağından sınır aralığımızı daraltılması doğru sonuca daha da yaklaşılmasını sağlar.
Üst sınırların en küçüğü ve alt sınırların en büyüğüne ulaşma yönteminde en kısa mesafeli
kapsayan ağaç (spanning tree) kullanılacaktır. Ayrıca en kısa mesafeli kapsayan ağaç
bulunurken Prim Algoritmasına başvurulacaktır.
Prim Algoritması:
İstenilen düğümden başlanarak belirlenen graftaki tüm noktaları içeren en kısa ağacın inşası
gerçekleştirilir. Her bir adımda en kısa ayrıt kullanılarak ve ağaç olma şartlarını bozmadan en
yakın düğümler ağaca eklenir. İzlenmesi gereken adımlar aşağıdaki gibidir:
1) İlk olarak her düğüm çiftinin arasındaki uzaklıkları gösteren tablo(matris) oluşturulur.
2) Başlamak için herhangi bir düğüm seçilir ve düğümün olduğu sütündan en küçük sayı
işaretlenir. Bir sonraki adımın başlangıç düğümleri işaretlenen sayının ait olduğu
satırda bulunan düğüm ile başlanılan düğüm olur.
3) Bir önceki adımda seçilen iki düğümün satırı incelenir ve tekrar en küçük sayı
seçilir. En küçük sayı seçilirken çevrim loop) devre circuits) veya parelel kenar
oluşmamasına dikkat edilir.)
4) Bu işlem graftaki her noktayı ağaca bağlayana kadar devam ettirilir.
5) Bu durumda bulunan ağaç tüm noktaları içeren en kısa kapsayan ağaç spanning tree)
olur.
- ’de klasik serbest satıcı problemi yer almaktadır. Bu çizgede düğümler kasabaları
ayrıtlar kasabalar arasındaki yolları ve ayrıtların uzunlukları kasabalar arasındaki yolların en
kısa mesafelerini ifade eder. Her düğümden sadece bir kez geçilerek ve aynı ayrıttan tekrar
geçilmeme şartı ile başlanılan noktaya geri dönmeyi sağlayan en kısa rotayı bulmak
amaçlanır.
Modellediğimiz
- ’deki örneğin bir tam graf olduğu açıktır. Aynı zamanda düğüm
çiftinin arasındaki en kısa mesafe alındığı için üçlü her düğüm üçgen eşitsizliğini sağlar.
Üst sınır: Çizgedeki her düğüm çiftinin arasındaki uzaklık
- ’de verilmiştir.
En kısa mesafeli kapsayan ağaç
- kullanılarak
-
’deki gibi oluşturulmuştur.
Ağacında toplam uzunluğu
Üst sınır:
birimdir.
eklinde hesaplanır.
Bu durumda
hesaplanacaktır.
-
bir üst sınırdır. Devamında bu üst sınırın en küçüğü
çizgesindeki güzergah
-
’de verilmiştir.
Ardından kestirme yol belirlenip
güzergahı kısaltılır.
görüldüğü gibi
bu ağaç için kestirme yoldur ve yeni güzergah
olur.
’da
birim olduğu görülür.
Bu sonuçtan kestirme
kısalmış anlamına gelir.
yolunun uzunluğu çıkartılırsa:
birimlik yol
Daha önce bulunan
üst sınırından kısalan yolun uzunluğu çıkartılırsa:
birim bulunur ve
birim üst sınırların en küçüğü olarak alınır.
Bu durumda;
olur.
Alt sınır: Aşağıdaki adımlar sırayla uygulanarak bulunur.
Adım Herhangi bir düğüm seçilir ve bu düğüm bağlı olduğu kenarlar ile birlikte graf
üzerinden silinir. Geriye kalan kısım yeni bir graf gösterir.
Adım : Bu yeni graf için en kısa kapsayan ağaç bulunur.
Adım : Daha önce silinen düğümün en kısa ayrıtlarla bağlı olduğu iki düğüm belirlenir.
Devamında bu iki düğüm ile silinen düğüm en kısa kapsayan ağaç üzerinde tekrar bağlanır.
Adım : Problemde verilen graf üzerindeki her nokta için ilk
düğüm için ayrı alt sınır bulunur.
adım uygulanarak her bir
Adım :Her düğüm için bulunan alt sınırların en büyüğü alınır.
Bu adımlar probleme uygulanırsa:
A düğümü ve bağlı olduğu ayrıtlar silinirse yeni graf
-27’deki gibidir.
-27
Oluşturulan yeni graf için
- kullanılarak bulunan en kısa kapsayan ağaç
şeklinde olduğu görülür ve uzunluğu
birimdir.
( birim) ve
(
ayrıtları düğümünün bağlı olduğu en kısa iki ayrıt olduğu
belirlenir ve düğümü bu iki ayrıt ile ağaç üzerinde ve noktalarına
-29’daki gibi
bağlanır.
düğümünün silinmesiyle bulunan
Bu işlemler
ve
olur.
düğümleri için de uygulanır ve
- ’deki alt sınırlar bulunur.
Bulunan alt sınırlar arasından en büyüğü
olarak belirlenir.
Bu durumda;
.
Elde edilen en küçük üst sınır ile en büyük alt sınırın aralığı
olduğu görülür.
Sonuç olarak
yoludur.
-
’deki çizge için aranan en kısa rota:
birim olan
Y NTEM:
Graf teorisi kullanılarak İstanbul’un turistik mekanlarına yapılacak gezi için belli turistik
noktalardan ve yollardan geçme koşulu altında en uygun rotanın belirlenmesi
amaçlanmaktadır. Bu amaç doğrultusunda graf teorisi ile ilgili araştırmalar yapılmış ve graf
teorisi ile çözümlenmiş problemler incelenmiştir.
Projede İstanbul’u ziyaret eden turistler için gezilmesi planlanan turistik mekanların yerleri
belirlendi. Daha sonra harita üzerinde bu noktalar belirlenerek aralarındaki bağlantılar
belirlendi ve bir graf oluşturuldu. Yaptığımız araştırmalar sonucunda İstanbul için uygun
modelleme yöntemi belirlendi.
Edinilen bilgilere göre her yoldan geçme koşulu altında en uygun yöntemin yönsüz Çinli
postacı problemi çözüm yöntemi Seçilmiş Yöntem 1) olduğu belirlendi.
Yine edinilen bilgilere göre her noktaya sadece bir kere uğrama koşulları altında en uygun
yöntemin serbest satıcı problemi çözüm yöntemi Seçilmiş Yöntem 2) olduğu belirlendi.
Yönsüz Çinli Postacı Probleminin Çözüm Yöntemini Kullanarak Yapılan Hesaplamalar
Çinli postacı probleminde temel unsur düğümler arasındaki her ayrıttan en az bir kere
geçerek en kısa rotayı bulmaktır. G modellediğimiz çizge olmak üzere G’deki tek dereceli
düğümler tespit edildi. Euler teoreminde her düğümün derecesi çift ise Euler turu
gerçekleştirilebilir. Oluşturulan çizgede tek dereceli düğümlerin varlığı söz konusu ise bu
düğümler ayrıştırılır. Şehirdeki turu temsil eden düğümler ayrıtlar ve ayrıtların uzunluğu
aşağıdaki şekilde tasvir edildiği gibidir.
-
İstanbul’un belirli semtleri için G çizgesi
Tablo-4’de G grafı üzerindeki numaraların temsil ettiği semtler verilmiştir.
Numaralar
Semt
İsimleri
1
Anadolu
Hisarı
2
Fatih
3
Eminönü
4
Eyüp
5
Taksim
6
Karaköy
7
Beşiktaş
8
Rumeli
Hisarı
9
Üsküdar
10
Beylerbeyi
-
- ’ bakılınca deg(1)=2, deg(2)=3, deg(3)=4, deg(4)=2, deg(5)=6, deg(6)=3, deg(7)=4,
deg 8)=3 deg 9)=2 deg 10)=3 olduğu görülür. Bu durumda 2 6 8 10 numaralı düğümler
tek derecelidir.Tek dereceli düğümler ve onları birbirine bağlayan ayrıtlar için en kısa
mesafeli eşleştirme yöntemi kullanılarak yapılan eşleştirmeler
- ’ de verilmiştir.
Eşleştirmeler
Mesafe
(2,6) - (8,10)
5.9 + 15.3 = 21.2 *
(2,8) - (6,10)
14.8 + 9.9 = 24.7
(2,10) - (6,8)
14.3 + 10.6 = 24.9
-
- ’den de açıkça görülmektedir ki en kısa mesafeli eşleştirme 2 6)- 8 10) ayrıtları
arasında ortaya çıkmaktadır. Turun gerçekleşebilmesi için tekrar edilecek yollar 2’den 6’ya en
kısa yol ((2,3)- 3 6) ayrıtı) ve 8’den 10’a gidilecek en kısa yoldur((8,7)- 7 10) ayrıtı).
-
İstanbul’un belirli semtleri için G çizgesi
- ‘deki G çizgesinde tekrar edilecek yollar kırmızı renkle ifade edilmiştir.Bu
durumda çizgedeki tüm düğümler çift dereceli hale dönüşmüştür.en iyi rotayı bulmaya
çalıştığımız
- ’deki orijinal çizge için artık yeni oluşan G çizgesine bakılarak en az
bir Euler tutu oluşturulabilir. Bu oluşturulan Euler turu aynı zamanda en iyi rotayı verir.
Oluşan en iyi rota ise şöyledir (2,4)-(4,5)-(5,2)-(2,3)-(3,5)-(5,8)-(8,1)-(1,10)-(10,7)-(7,8)(8,7)-(7,5)-(5,6)-(6,3)-(3,9)-(9,10)-(10,7)-(7,6)-(6,3)-(3,2). Buna göre G çizgesindeki her bir
ayrıttan tam olarak bir kez ve G çizgesindeki her ayrıttan en az bir kez geçilmiştir. G
çizgesinde sadece 2 3)- (3,6) ve (8,7)- 7 10) ayrıtları tekrarlanmıştır. Sonuç olarak bu rotanın
toplam uzunluğu 112 24 km’dir. Bu uzunluk G çizgesindeki her bir yolun yalnız bir kez
geçilmesiyle bulunan toplam uzunluktan 21 2 km fazladır.
Problem en kısa mesafe eşleştirme yöntemi ile çözülüp en kısa rota uzunluğu bulunmuştur.
Fatihten yola çıkan aracın ana yollardan en az bir kere geçmesini sağlayarak aracın tekrar
fatihe dönmesi sağlanarak problem çözüme ulaştırılmıştır.
Her yoldan geçme koşulu sayesinde turistler sadece turistik mekanları değil İstanbul’un
tamamını görme fırsatı elde edecekler. Haliç üzerindeki köprüler boğaz köprüsü bu yollara
örnek verilebilir. Tablo-6’da geçilen tollar üzerindeki yerler belirtilmiştir.
Tablo-6
Serbest Satıcı Probleminin Çözüm Yöntemini Kullanarak Yapılan Hesaplamalar
Serbest satıcı probleminde; kullanılan ayrıt tekrar kullanılmama şartı ile her düğümden
sadece bir kere geçerek başlanılan düğüme geri dönen en kısa rotayı bulmak amaçlanır.
Bir tam graf olacak şekilde Tablo-4’teki numaraların temsil ettiği semtler ile Şekil-32’de G
tam grafı modellenmiştir.
Şekil-32: G tam grafı
Modellenen G grafında her düğüm semt) çiftinin arasındaki en kısa mesafeli yol alınarak
Tablo-7’da gösterilmiştir.
Tablo-7
G grafı üzerinde her düğüm çifti arasında en kısa mesafe alınması her üçlü düğümün bir
üçgen olduğunu gösterir. Bu durum aşağıdaki eşitsizliklerin her üçlü düğü takdirde için
sürdürüldüğü takdirde doğru sonuçlar vereceğinin kanıtıdır. Bu durumda oluşturulan grafta
her üçlü düğüm için ;
işlemler sürdürülerek üçgen eşitsizliğinin sağlandığı görülür.
Modellenen G grafının tam graf olması ve ayrıtların uzunluklarının üçgen eşitsizliğini
doğrulaması serbest satıcı probleminin çözüm yöntemi için gereken şartların sağlandığını
gösterir.
Üst sınır ve alt sınır bulma yöntemi ile problem çözümü;
Üst Sınır Bulma
2 numaralı semtten başlayarak tablo-7 yardımıyla Prim algoritması kullanıldı. Tüm
noktaları kapsayan en kısa ağaç spanning tree) Şekil-33teki gibi oluşturuldu.
Şekil-33
Bulduğumuz en kısa ağacın uzunluğu:
km olarak bulunur.
Üst sınır:
km’dir.
Devamında en küçük üst sınıra ulaşmak için Şekil-34’te görüldüğü gibi kestirme yollar
1 6)ve 8 6) ayrıtları olarak belirlendi. Kestirme yollar kullanılarak ve her düğümden sadece
birkere geçilerek kapsayan ağaç üzerinde en kısa rota Şekil-34’te mavi çizge ile gösterilmiştir.
Şekil-34
1 6) ayrıtı için kısaltılan yol uzunluğu:
’dir.
4 8) ayrıtı için kısaltılan yol uzunluğu:
’dir.
Üst sınır değerinden kısaltılan yolların uzunluğu çıkartılarak ulaşılan en küçük üst sınır:
olarak bulunur.
Bu durumda;
olmalıdır.
Bu durumda üst sınır bulunduktan sonra izlenen rota:
(2,3)-(3,9)-(9,10)-(10,1)-(1,6)-(6,5)-(5,7)-(7,8)-(8,4)- 4 2) şeklinde olur.
Alt sınır bulma:
G çizgesindeki her düğüm tek tek çıkartılarak her biri için en kısa ağaç belirlenerek alt
sınır bulunacak ve buradan en büyük alt sınıra ulaşılacaktır..

1 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için, içerisinde 1
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-8).
Tablo-8
Tablo-8 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 1 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 1 8) ve (1,10) olduğu belirlendi ve ağaca
eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-35 de gösterilmiştir.
Şekil-35
1 numaralı düğümün silinmesiyle ulaşılan alt sınır:
’dir.

2 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 2
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-9)
Tablo-9
Tablo-9 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 2 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 2 3) ve 2 6) olduğu belirlendi ve ağaca
eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-36 de gösterilmiştir.
Şekil-36
2 numaralı düğümün silinmesiyle ulaşılan alt sınır:

3 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 3
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-10)
Tablo-10
Tablo-10 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 3 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 3,6) ve (3,2) olduğu belirlendi ve ağaca eklendi.
Eklenen ayrıtlar mavi çizgeler ile Şekil-37 de gösterilmiştir.
Şekil-37
3 numaralı düğümün silinmesiyle ulaşılan alt sınır:

4 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 4
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-11)
Tablo-11
Tablo-11 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 4 numaralı düğümün
bağlı olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 4 2) ve 4 3) olduğu belirlendi ve
ağaca eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-38 de gösterilmiştir.
Şekil-38
4 numaralı düğümün silinmesiyle ulaşılan alt sınır:

5 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 5
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-12)
Tablo-12
Tablo-12 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 5 numaralı düğümün
bağlı olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 5 6) ve 5 7) olduğu belirlendi ve
ağaca eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-39 da gösterilmiştir.
Şekil-39
5 numaralı düğümün silinmesiyle ulaşılan alt sınır:

6 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 6
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-13)
Tablo-13
Tablo-13 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 6 numaralı düğümün
bağlı olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 6 3) ve 6 5) olduğu belirlendi ve
ağaca eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-40 ta gösterilmiştir.
Şekil-40
6 numaralı düğümün silinmesiyle ulaşılan alt sınır:

7 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 7
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-14)
Tablo-14
Tablo-14 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 7 numaralı düğümün
bağlı olduğu en kısa iki ayrıt Tablo-7’ya bakılarak 7 5) ve 7 6) olduğu belirlendi ve
ağaca eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-41 de gösterilmiştir.
Şekil-41
7 numaralı düğümün silinmesiyle ulaşılan alt sınır:

8 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 8
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-15)
Tablo-15
Tablo-15 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 8 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 8,5) ve (8,7) olduğu belirlendi ve ağaca eklendi.
Eklenen ayrıtlar mavi çizgeler ile Şekil-42 de gösterilmiştir.
Şekil-42
8 numaralı düğümün silinmesiyle ulaşılan alt sınır:

9 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 9
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-16)
Tablo-16
Tablo-16 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 9 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 9,3) ve (9,10) olduğu belirlendi ve ağaca
eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-43’te gösterilmiştir.
Şekil-43
9 numaralı düğümün silinmesiyle ulaşılan alt sınır:

10 numaralı düğümün G grafından kaldırılması ile oluşan yeni graf için içerisinde 10
numaralı düğümün olmadığı yeni bir tablo tekrar oluşturuldu. Tablo-17)
Tablo-17
Tablo-17 yardımıyla en kısa yollu ağaç oluşturuldu. Silinen 10 numaralı düğümün bağlı
olduğu en kısa iki ayrıt Tablo-7’ye bakılarak 10,9) ve (10,1) olduğu belirlendi ve ağaca
eklendi. Eklenen ayrıtlar mavi çizgeler ile Şekil-44’te gösterilmiştir.
Şekil-44
10 numaralı düğümün silinmesiyle ulaşılan alt sınır:
Her düğüm için bulunana alt sınır Tablo-18’de gösterilmiştir ve bulunan alt sınırların en
büyüğü
olduğu görülmüştür.
Tablo-18
Bu durumda;
olur.
Opsiyonel rotanın uzunluğu
aralığında alınmalıdır.
Dolayısıyla aranan en kısa rota üst sınır araştırmalarında bulunan ve uzunluğu 68 74 km
olan, (2,3)-(3,9)-(9,10)-(10,1)-(1,6)-(6,5)-(5,7)-(7,8)-(8,4)-(4,2) rota olarak belirlenir.
İncelenmesi gerekir ki en büyük üst sınır olan 50 24 değeri 1 numaralı ve 10 numaralı
düğümlerin çıkarılmasıyla elde edilmiştir. Bu düğümlerin çıkarılmasıyla oluşturulan ağaçlar
üzerinde belirlediğimiz rotanın aynısı izlenebilir. Örnek olarak 10 numaralı düğümün
çıkarılmasıyla oluşturulan en kısa ağaç üzerinde belirlenen rotanın aynısı Şekil-45’de kırmızı
çizge ile gösterilmiştir.
Şekil-45
Şekil-32’deki G grafı için kullanılan ayrıtı bir daha kullanmamak şartı ile her düğümden
sadece bir kere geçen ve başladığı noktaya geri dönen rota bulunmuştur. Yani Hamilton
devresine ulaşılmıştır ve opsiyonel en kısa Hamilton devresi 68 74 km’dir.
Fatih’ten başlayarak ziyaret edilmesi uygun görülen semtlere sadece bir kere gidilmiş ve hızlı
bir tur için geçilen yollardan sadece bir kere geçilmiştir. En kısa mesafeli turist yolculuğunun
rotası belirlenerek problem çözüme kavuşturulmuştur.
SONUÇ VE TARTIŞMA:
1.çözüm için rota 2 4)-(4,5)-(5,2)-(2,3)-(3,5)-(5,8)-(8,1)-(1,10)-(10,7)-(7,8)-(8,7)-(7,5)(5,6)-(6,3)-(3,9)-(9,10)-(10,7)-(7,6)-(6,3)-(3,2) olarak bulundu.
Buna göre G Şekil-31) çizgesindeki her bir ayrıttan tam olarak bir kez ve G Şekil-30)
çizgesindeki her ayrıttan en az bir kez geçilmiştir. G çizgesinde sadece 2 3)- (3,6) ve (8,7)7 10) ayrıtları tekrarlanmıştır. Sonuç olarak bu rotanın toplam uzunluğu 112 24 km’dir. Bu
uzunluk G çizgesindeki her bir yolun yalnız bir kez geçilmesiyle bulunan toplam uzunluktan
21 2 km fazladır. Ayrıtların uzunlukları ve temsil ettikleri yolların isimleri Tablo-6’da
verilmiştir.
Seçilen 1. yöntem olan Yönsüz Çinli Postacı Problemi Çözüm Yöntemi kullanılarak çıkan
rotadaki yolların açıklaması
Fatih’ten başlanarak Edirnekapı ardından Yavedut Caddesi üzerinden Eyüp’e gidildi.
Eyüp’ten E-5 üzerinden Haliç köprüsü ve Okmeydanı’ndan geçerek Taksim’e gidildi.
Taksim’den Fatih’e Atatürk Köprüsü ve Atatürk Bulvarı üzerinden gidildi. Fatih’ten
Eminönü’ne giderken Atatürk Bulvarı ardından Kennedy Caddesi kullanıldı. Eminönü’nden
Taksim’e Galata Köprüsü üzerinden gidildi. Taksim’den Rumeli Hisarı’na giderken Bebek
Sahilyolu kullanıldı. Rumeli Hisarı’ndan Anadolu Hisarı’na Fatih Sultan Mehmet üzerinden
gidildi. Anadolu Hisarı’ndan Beylerbeyi’ne giderken Kuleli Sahilyolu kullanıldı.
Beylerbeyi’nden Beşiktaş’a Boğaziçi Köprüsü aracılığıyla gidildi. Beşiktaş’tan Rumeli
Hisarı’na Bebek Sahilyolu üzerinden gidildi. Yine Bebek Sahilyolu kullanılarak Beşiktaş’a
geri dönüldü. Beşiktaş’tan Taksim’e Gümüşsuyu Caddesi üzerinden gidildi. Taksim’den
Karaköy’e Kazancı Yokuşu aracılığıyla gidildi. Karaköy’den Eminönü’ne Galata Köprüsü
üzerinden gidildi. Eminönü’nden arabalı vapurla Üsküdar’a geçildi. Üsküdar’dan
Beylerbeyi’ne Üsküdar Sahilyolu üzerinden gidildi. Beylerbeyi’nden Beşiktaş’a Boğaziçi
Köprüsü aracılığıyla gidildi. Beşiktaş’tan Karaköy’e Meclis-i Mebusan Caddesi üzerinden
gidildi. Karaköy’den Eminönü’ne Galata Köprüsü üzerinden geçildi. Eminönü’nden Fatih’e
Kennedy Caddesinden geçilerek Atatürk Bulvarı aracılığıyla gidildi.
2. çözüm için rota 2 3)-(3,9)-(9,10)-(10,1)-(1,6)-(6,5)-(5,7)-(7,8)-(8,4)-(4,2) olarak bulundu.
Şekil-32’deki G grafı için kullanılan ayrıtı bir daha kullanmamak şartı ile her düğümden
sadece bir kere geçen ve başladığı noktaya geri dönen rota bulunmuştur. Yani Hamilton
devresine ulaşılmıştır ve opsiyonel en kısa Hamilton devresi 68 74 km’dir.
Seçilen ikinci yöntem olan Serbest Satıcı Problemi Çözüm Yöntemi kullanılarak çıkarılan
rotadaki yolların açıklaması
Fatih’ten Eminönü’ne Atatürk Bulvarı ve Kennedy Caddesi üzerinden gidildi. Eminönü’nden
Üsküdar’a arabalı vapur ile geçildi. Üsküdar’dan Beylerbeyi’ne Üsküdar Sahilyolu’ndan
gidildi. Beylerbeyi’nden Anadolu Hisarı’na giderken Kuleli Sahilyolu kullanıldı. Anadolu
Hisarı’ndan Karaköy’e gidildi. Karaköy’den Taksim’e giderken Kazancı Yokuşu kullanıldı.
Taksim’den Beşiktaş’a Gümüşsuyu Caddesi üzerinden gidildi. Beşiktaş’tan Bebek Sahilyolu
kullanılarak Rumeli Hisarına gidildi. Rumeli Hisarı’ndan TEM otoyolu ile Eyüp’e gidildi.
Eyüp’ten Fatih’e Yavedut Caddesi Edirnekapı üzerinden gidildi.
Çözümün Değerlendirilmesi
Bu çalışmada görülmüştür ki problem ne kadar karmaşık olursa olsun graf teorisi
kullanılarak çözüm bulunabilmekte ve elde edilen çözüm gerek zaman kaybını engellemesi
açısından gerek ekonomik açıdan olumlu etkiler göstermektedir. Bu anlamda projede elde
edilen mektup dağıtımı yol bakımı atık veya çöp toplama işlemleri kar temizleme
çalışmaları elektrik sayaçlarının okunması polis devriye araçlarının rotalarının belirlenmesi
ve otobüs çizelgelemesi gibi durumlar için örnek olma niteliği taşımaktadır.
Projenin geliştirilmesi için bir sonraki aşama olarak semtlerde bulunan turistik mekanların
gezilebilmesi için yayalar göz önünde bulundurularak yeni rotalar hesaplanabilir.
KAYNAKÇA:
Rosen, Kenneth H., (2012),Discrete Mathematics and Its Applications,McGraw-Hill,
NewYork
Wilson, Robin J.,(1996), Introduction to Graph Theory, England, Fourth Edition
Liberti, Leo, (2010), Problems and exercise in Operations Research, ECOLE
POLYTECHNIQUE
Doğanaksoy Ali 1993) Graf Teorisi, Cilt 1-2
Casquilho, Miguel A. S., Travelling Salesman Problem, Universty of Lisbon, Portugal
EMEL Gökay Gül TAŞKIN Çağatan DİNÇ Emtullah Yönsüz Çinli Postacı Problemi:
Polis Devriye Araçları İçin Bir Uygulama Uludağ Üniversitesi Sosyal Bilimler Dergisi,
Sayfa 121-138
Sural, Haldun, (2003), Gezgin Satıcı Problemi Matematik Dünyası 2003- III, Sayfa 37-40
Nesin, Ali, (2003), Euler Turu, Matematik Dünyası 2003-III, Sayfa 13-15
Eiselt, H. A., Gendreau, Michel, Laporte, Gilbert,(1995), Arc Routing Problems, Part I: The
Chinese Postman Problem, Operations Research, Volume 43 Issue 2, March-April 1995, pp.
231-242
Xiong, Bin, Zheng, Zhongyi, (2010), Graph Theory, World Scientific, Massachusetts
Marcus, Daniel A., (2008), Graph Theory: A Problem Oriented Approach, MAA, USA