Düğüm (matematik)

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.

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

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

• Düğüm (bilgisayar bilimleri)
• Çizge teorisinin kavramları