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

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

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

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

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

• Στον παρακάτω γράφο, έχουμε ότι $\epsilon (v_{1})=3$ και $\epsilon (v_{5})=2$.

Αριστερά ο αρχικός γράφος, στη μέση οι αποστάσεις σε κόκκινο από την κορυφή $v_{1}$ και δεξιά οι αποστάσεις από την κορυφή $v_{5}$. Η εκκεντρότητα για κάθε κορυφή είναι η μέγιστη από αυτές τις αποστάσεις.

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

Αριστερά το άστρο με 5 κορυφές, στη μέση οι αποστάσεις σε κόκκινο από την κεντρική κορυφή και δεξιά οι αποστάσεις από μία μη-κεντρική κορυφή.

Δείτε επίσης

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