Düğüm (matematik)

Vikipedi, özgür ansiklopedi
Gezinti kısmına atla Arama kısmına atla
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[değiştir | kaynağı değiştir]

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[değiştir | kaynağı değiştir]

Kaynakça[değiştir | kaynağı değiştir]

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1), s. 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[değiştir | kaynağı değiştir]