İçeriğe atla

Düğüm (matematik)

En soldaki düğümün yaprak düğüm olduğu 6 düğümlü 7 kenarlı bir çizge

Düğüm matematikte ve özellikle çizge teorisinde, bir çizgeyi oluşturan temel elemandır. Bir çizge temel olarak düğüm ve kenarlardan oluşur. Çizge görselleştirilirken genellikle düğümler çember, kenarlar da çizgi (yönsüz çizge) veya ok (yönlü çizge) şeklinde gösterilir.

A düğümü ile B düğümü arasında bir kenar olduğu zaman A ile B birbirinin komşu düğümü olarak adlandırılır. Bir düğümün komşuluk çizgesi bu düğümün komşu düğümlerinden oluşan alt-çizgedir.

Düğüm çeşitleri

Bir düğümün derecesi o düğüme bağlı kenarların sayısına eşittir. Derecesi sıfır olan düğüme yalıtılmış düğüm denir, bu düğüm hiçbir kenarın uç noktası değildir. Derecesi bir olan düğüme yaprak düğüm denir. Yönlü çizgelerde dışaderece (düğümden çıkan oklar) ve içederece (düğüme gelen oklar) olarak iki farklı derece kullanılabilir. İçederecesi sıfır olan düğüme kaynak düğüm, dışaderecesi sıfır olan düğüme çıkış düğümü denir. Çizgedeki diğer tüm düğümlere komşu olan düğüme evrensel düğüm denir.

Kaldırıldığında çizgenin diğer düğümlerinin bağlantısını kesen düğüme kesici düğüm denir. En az K düğüm kullanılarak bağlantısı kesilebilen çizgeye K düğümle bağlı çizge denir. İçindeki hiçbir düğümün birbirine komşu olmadığı düğüm kümesine bağımsız küme denir.

Ayrıca bakınız

Kaynakça

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1). ss. 1-79. doi:10.1007/BF02288320. 
  • Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
  • Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9. 
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9. 
  • Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8. 
  • Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2. 

Dış bağlantılar

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Çizge teorisi</span> nesneler arasındaki ikili ilişkileri modellemek için kullanılan matematiksel yapılar olan grafiklerin incelenmesi

Graf teorisi, çizge teorisi veya çizit teorisi, 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 oluşur.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

<span class="mw-page-title-main">Yarıçap</span> merkezinden çevresine bir daire veya küre içinde bölüm veya yüzeyi ile uzunluğu

Yarıçap, bir daire veya kürenin özeğinin (merkezinin) çemberine olan mesafesidir. Çapın yarısına eşittir.

<span class="mw-page-title-main">Bağımsız küme problemi</span>

Bağımsız küme bir çizgede birbirleriyle komşu olmayan düğümleri içeren kümedir. çizgede düğümler kümesi 'de arasında ayrıt olan iki düğüm bulunmuyorsa S bağımsızdır denir. Bağımsız küme problemi NP-Tam bir problemdir. Yani Polinomsal zaman'da problemi çözen bir algoritma bulunamamıştır.

<span class="mw-page-title-main">Sonlu durum makinesi</span>

Sonlu durum makinası ; sınırlı sayıda durumdan, durumlar arası geçişlerden ve eylemlerin birleşmesiyle oluşan davranışların bir modelidir.

<span class="mw-page-title-main">Königsberg'in Yedi Köprüsü</span>

Königsberg'in yedi köprüsü; graf teorisinin temelini oluşturan ve XVIII. yüzyılda Königsberg köprülerinden ilhamlanılarak ortaya atılan ünlü bir matematik problemidir.

<span class="mw-page-title-main">Cebirsel sayılar</span>

Cebirsel sayılar, rasyonel katsayıları olan tek değişkenli sıfırdan farklı bir polinomun kökü olarak ifade edilebilen sayılardır. Mesela, altın oran, , cebirsel bir sayı örneğidir çünkü x2x − 1 polinomunun bir köküdür. Bu durumda, söz konusu polinomun değerinin sıfıra eşitlendiği x değeridir. Diğer bir örnek olarak, biçimindeki karmaşık sayı, x4 + 4 polinomunun bir kökü olduğundan dolayı cebirsel sayı olarak kabul edilir.

<span class="mw-page-title-main">Kuantum alan teorisi</span> hareketli parçacık sistemlerinin kuantizasyonuyla ilgilenen parçacık mekaniğiyle benzer olarak, alanların hareketli sistemlerine parçacık mekaniğinin uygulamasıdır

Kuantum Alan Teorisi (METATEORİ); Klasik Birleşik Alan (KAT) Teorilerini, Özel Görekliliği (SRT), Kuantum mekaniği (KM) teorilerini tek bir teorik çerçeve altında toplayan bir üst teoridir.

<span class="mw-page-title-main">Düğüm</span> bir parça ip, ip veya benzeri bir şey bağlayarak yapılan bir tutturma

Düğüm; ip vb. doğrusal cisimleri, birbirine tutturmak için kullanılan yöntemdir. Düğüm, bir veya birden fazla ipten, dokumalardan, sicim ve kayışlardan, zincirlerden, hatta birbirine bağlanmış hatlardan meydana gelen dokumalardan meydana gelebilir. Düğümler, bağlama yöntemleri, kullanımları, hikâyeleri, kökenleri ve düğüm teorisinin matematiksel gözlemleri nedeniyle ilginç nesneler olarak tanınırlar.

Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.

3SAT ve KLIK problemleri, Turing makinasından polinom zamanda kararlaştırılabilen NP problemleri arasında yer alır. Bu problemlerin birbirinin cinsine çevrilmesine indirgeme denilir.

Mimarlık teorisi veya mimari teori mimarlık hakkında düşünmek, tartışmak ve en önemlisi yazmak eylemlerine verilen isimdir. Mimarlık teorisi dünyanın birçok yerinde mimarlık fakültelerinde öğretilmekte ve bazıları da belli mimarlar tarafından benimsenip uygulanmaktadır.

<span class="mw-page-title-main">David Bohm</span> Amerikalı teorik fizikçi (1917 – 1992)

David Bohm ; teorik fizik, felsefe ve nöropsikoloji alanlarına katkıda bulunmuş bir kuantum mekaniği fizikçisidir.

<span class="mw-page-title-main">4=0 düğümü</span>

4=0 düğümü, bir ipe dört düğüm atıp iki ucundan çekince ipin düğümsüz kalmasıyla şaşırtır. Aslında son iki hamle ilk iki işlemi geri almıştır.

<span class="mw-page-title-main">İki parçalı graf</span>

Graf teorisinde, düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrılabilen graflara iki parçalı graf adı verilir.

<span class="mw-page-title-main">Bayes ağı</span>

Bir Bayes ağı, Bayes modeli ya da olasılıksal yönlü dönüşsüz çizge modeli bir olasılıksal çizge modelidir ve birbirleriyle koşulsal bağımlılıklara sahip bir rassal değişkenler kümesini yönlü dönüşsüz çizge(YDÇ) şeklinde ifade eder. Bayes ağları; gündelik hayatta meydana gelen bir olayı anlatmak ve o olayın gerçekleşmesine sebebiyet verebileceği bilinen birkaç olası nedenden herhangi birinin katkıda bulunan faktör olma olasılığını tahmin etmek için kullanılan ideal bir modelleme türüdür. Örneğin, bir Bayes ağı kullanılarak hastalıklar ve semptomları arasındaki olasılıksal koşul ilişkileri modellenebilir. Bu model kullanılarak, bir kişide görülen semptomlar verildiğinde bu kişinin bazı hastalıklara sahip olma olasılıkları hesaplanabilir. Buna benzer olarak neden-sonuç ilişkisi olan birçok olayın olasılığı bu modelleme ile görselleştirilebilir.

<span class="mw-page-title-main">Graf (matematik)</span> kenarlarla çiftler halinde bağlanmış köşeler

Matematikte graf ya da çizge, nesne çiftlerinin bir anlamda "ilişkili" olduğu bir dizi nesne kümesini belirleyen bir yapıdır. Nesneler, köşeler adı verilen matematiksel soyutlamalara karşılık gelir ve ilgili düğüm çiftlerinin her birine bir kenar, ayrıt adı verilir. Tipik olarak bir graf, kenarları için çizgiler veya eğriler ile birleştirilen, düğümler için bir nokta veya daire kümesi olarak diyagram şeklinde gösterilir. Graflar ayrık matematikte çalışmanın amaçlarından biridir.

<span class="mw-page-title-main">Yönlü çizge</span> yönlendirilmiş kenarlara sahip grafik

Çizge teorisinde, yönlü çizge düğümler ve hepsi birer yöne sahip kenarlardan oluşan çizgedir.

<span class="mw-page-title-main">Ölçü (matematik)</span> uzunluk, alan, hacim ve integralin bir genellemesi olarak görülebilecek bir kümenin bazı alt kümelerine sayılar atayan işlev

Matematiksel analizde, küme üzerindeki bir ölçü, bu kümenin her bir uygun alt kümesine bir sayı atamanın sistematik bir yoludur ve sezgisel olarak kümenin boyutu olarak yorumlanır. Bu anlamda ölçü, uzunluk, alan ve hacim kavramlarının bir genellemesidir. Özellikle önemli bir örnek, Öklid geometrisinin geleneksel uzunluğunu, alanını ve hacmini n-boyutlu Öklid uzayının Rn uygun alt kümelerine atayan bir Öklid uzayındaki Lebesgue ölçüsüdür. Örneğin, gerçek sayılardaki [0, 1] aralığının Lebesgue ölçüsü, kelimenin günlük anlamındaki uzunluğudur ve tam olarak 1'dir.

Grafik teorisinin matematiksel disiplininde, yönlendirilmemiş bir G grafiğinin çizgi grafiği, G'nin kenarları arasındaki bitişiklikleri temsil eden başka bir L (G) grafiğidir.. L(G) şu şekilde oluşturulur: G'deki her kenar için, L(G)'de bir tepe noktası yapılır; G'de ortak bir tepe noktasına sahip her iki kenar için, L(G)'de karşılık gelen köşeleri arasında bir kenar yapılır.