Kuflu Forum  

Geri Git   Kuflu Forum > Eğitim-Öğretim Dünyası > Ödevler Dünyası > Matematik



Çizge Kuramı

Matematik


Yeni Konu aç  Cevapla
 
LinkBack Seçenekler Stil
Alt 23.09.12, 02:41   #1 (permalink)
Müdavim Üye
 
Uygu - ait Kullanıcı Resmi (Avatar)
 
Üyelik tarihi: Sep 2012
Mesajlar: 4.304
Teşekkürleri: 1.659
965 mesajına 2.008 kere teşekkür edildi.
Standart Çizge Kuramı



(İng: Graph theory), çizgeleri inceleyen matematik dalıdır. Çizge, uçlar ve bu uçları birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır.

Temeli 1736'da Leonhard Euler (1707-1783) tarafından atılan kavram
Geçmiş :

Königsberg köprüleri sorunuLeonhard 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.

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.

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ı.

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.

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.

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 grafiği uçlar kümesi U(C), kenar kümesi K(C) ve bu kenar kümesindeki her kenarın iki uç ile ilişkilerinden oluşur.

Uçları birleştiren kenarların yönleri olabilir. Bu grafiklere yönlü denilir ve "sahte" (pseudo) grafik diye de bilinir.

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 (elemanların) farklı iki 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.


Alıntı


Uygu isimli Üye şimdilik offline konumundadır   Alıntı ile Cevapla
Cevapla


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Seçenekler
Stil

Yetkileriniz
Konu Acma Yetkiniz Yok
Cevap Yazma Yetkiniz Yok
Eklenti Yükleme Yetkiniz Yok
Mesajınızı Değiştirme Yetkiniz Yok

BB kodu Açık
Smileler Açık
[IMG] Kodları Açık
HTML-Kodu Kapalı
Trackbacks are Açık
Pingbacks are Açık
Refbacks are Açık



Tüm Zamanlar GMT +2 Olarak Ayarlanmış. Şuanki Zaman: 03:10.


Powered by vBulletin® Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.
2008-2016 Her hakkı kendinde saklı olan forum.
Sitemiz bir forum sitesi olduğu için kullanıcılar paylaşımlarını önceden onay almadan anında siteye yazabilmektedir. Bu yazılardan dolayı doğabilecek her türlü sorumluluk yazan kullanıcılara aittir. Yinede sitemizde yasalara aykırı unsurlar bulursanız iletisim adresine bildirebilirsiniz, şikayetiniz incelenip en kısa sürede gereken yapılır.