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

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

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

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

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

• Στον παρακάτω γράφο, έχουμε ότι $ϵ(v_1)=3$ και $ϵ(v_5)=2$.

• Σε ένα άστρο $K_{1,n}$ η εκκεντρότητα του κεντρικού κόμβου είναι $1$ και για κάθε άλλο κόμβο (όταν $n>2$) είναι $2$.

Δείτε επίσης

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