Εκκρεμής κόμβος

Στην θεωρία γράφων, ένας εκκρεμής κόμβος (ή τερματικός κόμβος) είναι ένας κόμβος σε έναν γράφο στον οποίο προσπίπτει ακριβώς μία ακμή.

Παραδείγματα

Οι κόμβοι 3, 7 και 8 είναι εκκρεμείς.

Όλα τα φύλλα ενός δέντρου είναι εκκρεμείς κόμβοι.

Μαθηματικός ορισμός

Μη κατευθυνόμενος γράφος

Σε έναν μη κατευθυνόμενο γράφο $G=(V,E)$, ο κόμβος $v\in V$ είναι εκκρεμής αν ο βαθμός του $\operatorname {deg} (v)=1$, δηλαδή

$|\{u:\{u,v\}\in E\}|=1$.

Κατευθυνόμενος γράφος

Αντίστοιχα, σε έναν κατευθυνόμενο γράφο $G=(V,E)$, ο κόμβος $v\in V$ είναι εκκρεμής αν το άθροισμα του έσω και του έξω βαθμού του $d_{-}(v)+d_{+}(v)=1$, δηλαδή

$|\{u:(u,v)\in E\}|+|\{u:(v,u)\in E\}|=1$.

Δείτε επίσης

• Απομονωμένος κόμβος
• Καθολικός κόμβος