Yeni Üyelik Haber bülteni üyeliği |
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 tarihiLeonhard 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ı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.
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
Tanımlar ve örneklerYol 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ızKaynakça
Dış bağlantılar
Bu makale Creative Commons Attribution-Share-Alike License 3.0 altında yayınlanan
|
|
Copyright © 2005 Uzerine.com
uzerine.com Ana Sayfa |
Gizlilik Sözleşmesi |
Üye Girişi