Διάμετρος (θεωρία γράφων)

Στην θεωρία γράφων, η διάμετρος ενός γράφου $G=(V,E)$ είναι η μέγιστη απόσταση μεταξύ δύο κόμβων $u$ και $v$ του γράφου:

$\mathrm {diam} (G)=\max _{u,v\in V}d(u,v)$,

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

$\mathrm {diam} (G)=\max _{v\in V}\epsilon (v)$.

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

• Η διάμετρος του παρακάτω γράφου είναι $2$, καθώς οι εκκεντρότητες των κόμβων του είναι $\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})=2$.

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

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

Αριστερά ο αρχικός γράφος και δεξιά ένα από τα ζευγάρια με την μέγιστη απόσταση στον κύκλο $C_{7}$.

• Ο γράφος-μονοπάτι $P_{n}$ έχει διάμετρο $n-1$.

Αριστερά ο αρχικός γράφος και δεξιά το ζευγάρι με την μέγιστη απόσταση στον γράφο-μονοπάτι $P_{5}$.

Δείτε επίσης

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