Ακτίνα (θεωρία γράφων)

Στην θεωρία γράφων, η ακτίνα ενός γράφου $G=(V,E)$ είναι η ελάχιστη εκκεντρότητα $ϵ(v)$ από όλες τις κορυφές $v\in V$, δηλαδήΠρότυπο:RpΠρότυπο:RpΠρότυπο:Rp

$\mathrm{r}\mathrm{a}\mathrm{d}(G)=\underset{v\in V}{\min }ϵ(v)$.

Ισοδύναμα, ορίζεται ως

$\mathrm{r}\mathrm{a}\mathrm{d}(G)=\underset{v\in V}{\min }\underset{u\in V}{\max }d(u,v)$,

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

Κάθε κορυφή $v\in V$ για την οποία $ϵ(v)=\mathrm{r}\mathrm{a}\mathrm{d}(G)$ λέγεται κεντρική και το σύνολο αυτών των κορυφών λέγεται κέντρο του $G$.

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

• Η ακτίνα του παρακάτω γράφου είναι $2$, καθώς οι εκκεντρότητες είναι $ϵ(v_1)=3$, $ϵ(v_2)=3$, $ϵ(v_3)=4$, $ϵ(v_4)=2$, $ϵ(v_5)=2$, $ϵ(v_6)=3$, $ϵ(v_7)=4$, $ϵ(v_8)=3$.

• Ο κύκλος $C_n$ έχει ακτίνα $\lfloor n/2\rfloor$.

• Ο πλήρης γράφος έχει ακτίνα $1$, καθώς όποια κορυφή και να διαλέξουμε οι αποστάσεις τις προς όλες τις κορυφές είναι $1$.

Δείτε επίσης

• Απόσταση (θεωρία γράφων)
• Εκκεντρότητα (θεωρία γράφων)
• Διάμετρος (θεωρία γράφων)