Κέντρο γράφου

Στην θεωρία γράφων, το κέντρο ενός γράφου είναι το σύνολο των κόμβων του που έχουν την ελάχιστη εκκεντρότητα. Πιο συγκεκριμένα, για τον γράφο $G=(V,E)$ το κέντρο του ορίζεται ως

$\mathrm {center} (G)=\{v\in V:\epsilon (v)=\mathrm {rad} (G)\}$,

όπου

• $\epsilon (v)$ είναι η εκκεντρότητα του κόμβου $v$, που ορίζεται ως

$\epsilon (v)=\max _{u\in V}d(u,v)$,

με $d(u,v)$ είναι η απόσταση των κορυφών $u$ και $v$ στον γράφο $G$, δηλαδή το μήκος του συντομότερου μονοπατιού μεταξύ τους (ή $\infty$ αν δεν υπάρχει),

• και $\mathrm {rad} (G)$ είναι η ακτίνα του γράφου, δηλαδή $\mathrm {rad} (G)=\min _{u\in V}\epsilon (u)$.

Κάθε κόμβος που ανήκει στο $\mathrm {center} (G)$ λέγεται κεντρικός.

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

• Στον παρακάτω γράφο οι εκκεντρότητες των κόμβων του είναι: $\epsilon (v_{1})=3$, $\epsilon (v_{2})=3$, $\epsilon (v_{3})=4$, $\epsilon (v_{4})=2$, $\epsilon (v_{5})=2$, $\epsilon (v_{6})=3$, $\epsilon (v_{7})=4$, $\epsilon (v_{8})=3$. Επομένως, το κέντρο του γράφου είναι $\mathrm {center} (G)=\{v_{4},v_{5}\}$.

Οι κεντρικοί κόμβοι του γράφου δίνονται με μπεζ χρώμα.

• Στον πλήρη γράφο όλοι οι κόμβοι είναι κεντρικοί, δηλαδή $\mathrm {center} (G)=V$.

Όλοι οι κόμβοι του $K_{6}$ είναι κεντρικοί.

• Στο παρακάτω τριαδικό δέντρο, η ρίζα του είναι το κέντρο του γράφου.

Ο κεντρικός κόμβος ενός τριαδικού δέντρου είναι η ρίζα του.

Δείτε επίσης

• Εκκεντρότητα (θεωρία γράφων)
• Ακτίνα (θεωρία γράφων)