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

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

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

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

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)=\underset{v\in V}{\max }ϵ(v)$.

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

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

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

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

Δείτε επίσης

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