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

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

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

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

Σε έναν μη κατευθυνόμενο γράφο $G=(V,E)$, ο κόμβος $v\in V$ είναι εκκρεμής αν ο βαθμός του $\mathrm{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$.

Δείτε επίσης

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