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

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

$\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}(G)=\{v\in V:ϵ(v)=\mathrm{r}\mathrm{a}\mathrm{d}(G)\}$,

όπου

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

$ϵ(v)=\underset{u\in V}{\max }d(u,v)$,

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

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

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

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

• Στον παρακάτω γράφο οι εκκεντρότητες των κόμβων του είναι: $ϵ(v_1)=3$, $ϵ(v_2)=3$, $ϵ(v_3)=4$, $ϵ(v_4)=2$, $ϵ(v_5)=2$, $ϵ(v_6)=3$, $ϵ(v_7)=4$, $ϵ(v_8)=3$. Επομένως, το κέντρο του γράφου είναι $\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}(G)=\{v_4,v_5\}$.

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

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

Όλοι οι κόμβοι του $K_6$ είναι κεντρικοί.

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

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

Δείτε επίσης

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