Ana Sayfa


Haber bülteni üyeliği

Örnek bir çizge
Graf teorisi, çizge teorisi veya çizit teorisi (İng. ), grafları inceleyen matematik dalıdır. Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf, çizge veya çizit, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan (yaylardan, bağıntılardan) oluşur.

Temeli 1736'da Leonhard Euler tarafından atılmıştır.

Graf teorisi üzerinde yapılan çalışmalar, Petri ağları gibi birçok yeni kavramların geliştirilmesine imkân sağlamıştır.

Teorinin tarihi

Königsberg köprüleri sorunu
Leonhard Euler tarafından, 1736 yılında, Königsberg'in yedi köprüsü () adında günümüzde hâlâ popülerliğini koruyan bir problem ile ilgili olarak yazılan bir makale, graf teorisinin kesin başlangıç tarihidir.

Matematiksel tanımı

Solda matematiksel ifadesi bulunan örnek bir graf
Solda matematiksel ifadesi bulunan örnek G grafı
Bir G grafı iki küme ile ifade edilir: G = (D, K). Bu ifadede D düğümler kümesi K ise, (düğümler ile ilişkili) kenarlar kümesi olarak ifade edilir.
  • Eğer düğümleri birbirine kenarlar için giriş ve çıkış yönleri belirli ise, bu kenarlara yönlü kenarlar denir.
  • Eğer bir düğümden çıkan ve yine aynı düğüme giren bir kenar varsa (mesela A'den çıkıp A'ya yeniden giren bir kenar), bu bir döngü () olarak ifade edilir.
  • Eğer bir düğümden bir başka düğüme giden aynı yöne sahip veya yönsüz iki adet kenar varsa bu kenarlara paralel kenarlar denir.

Sağdaki yönsüz, örnek graf için küme gösterimi aşağıdaki şekilde yapılır.

D = {A, B, C, D}

K = {(A, D), (A, D), (A, B), (A, C), (C, B), (C, D)}

G = (D, K)

Bu örnekte A ve D düğümleri iki adet paralel kenar içerir.

Graf tipleri

Graf tipi

Kenar tipi

Çoklu kenara izin

Döngüye izin?

Basit graf

Yönsüz

Hayır

Hayır

Çoklu graf

Yönsüz

Evet

Hayır

Pseudo (sahte) graf

Yönsüz

Evet

Evet

Yönlü graf

Yönlü

Hayır

Evet

Yönlü çoklu graf

Yönlü

Evet

Evet

Tanımlar ve örnekler

Yol haritasıyla haritada belirtilen yollarla bir beldeden diğer bir beldeye nasıl gidileceğine karar verilir. Sonuç olarak bu durumda nesnelerin iki farklı kümesi ile ilgilenilmektedir: Beldeler 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 beldeler kümesini ve E kümesi ile de yollar kümesini gösterirsek, V kümesi üzerinde yalnız E'deki yolları kullanarak a beldesinden (noktasından) b noktasına seyahat edilebiliyorsa a?b yazarak, bir ? bağıntısı tanımlanabilir. Eğer E'deki yollar gidiş-geliş yolları ise b?a da gerçeklenir. Eğer inceleme altındaki bütün 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. Bu, aşağıdaki şekilde gösterildiği şekilde çizgiler kullanarak yapılması daha uygundur.

Ayrıca bakınız

Kaynakça

Dış bağlantılar


Bu makale Creative Commons Attribution-Share-Alike License 3.0 altında yayınlanan
Wikipedia makalesi Çizge teorisi, materyallerini kullanır.

 

Editör Bilgileri

Yazar


Editöre Ulaşın

En Son Eklenenler

x-isini-pulsari
yaz-ucgeni
yerel-kabarcik
yildizlar-arasi-yolculuk
zhai-zhigang
avusturya-uzay-ajansi
birlesik-krallik-uzay-ajansi

Uzerine.com Copyright © 2005 Uzerine.com
uzerine.com Ana Sayfa | Gizlilik Sözleşmesi | Üye Girişi