Απομονωμένος κόμβος

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

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

Οι κόμβοι 1, 3 και 7 είναι απομονωμένοι.

Ο πλήρης γράφος $K_{1}$ αποτελείται από έναν απομονωμένο κόμβο.

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

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

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

$\forall u.\{u,v\}\not \in E$.

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

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

$\forall u.(u,v)\not \in E{\text{ και }}(v,u)\not \in E$.

Δείτε επίσης

• Εκκρεμής κόμβος
• Καθολικός κόμβος