Düğüm (matematik)
Bu maddede kaynak listesi bulunmasına karşın metin içi kaynakların yetersizliği nedeniyle bazı bilgilerin hangi kaynaktan alındığı belirsizdir. (Ekim 2016) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin) |
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
