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

Στην θεωρία γράφων, η ακτίνα ενός γράφου ${\displaystyle G=(V,E)}$ είναι η ελάχιστη εκκεντρότητα ${\displaystyle \epsilon (v)}$ από όλες τις κορυφές ${\displaystyle v\in V}$, δηλαδή^{[1]:9[2]:35[3][4]:21}

${\displaystyle \mathrm {rad} (G)=\min _{v\in V}\epsilon (v)}$.

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

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

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

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

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

• Η ακτίνα του παρακάτω γράφου είναι ${\displaystyle 2}$, καθώς οι εκκεντρότητες είναι ${\displaystyle \epsilon (v_{1})=3}$, ${\displaystyle \epsilon (v_{2})=3}$, ${\displaystyle \epsilon (v_{3})=4}$, ${\displaystyle \epsilon (v_{4})=2}$, ${\displaystyle \epsilon (v_{5})=2}$, ${\displaystyle \epsilon (v_{6})=3}$, ${\displaystyle \epsilon (v_{7})=4}$, ${\displaystyle \epsilon (v_{8})=3}$.

Αριστερά ο αρχικός γράφος και δεξιά οι αποστάσεις σε κόκκινο από την κορυφή ${\displaystyle v_{5}}$, που δίνει την ελάχιστη εκκεντρότητα.

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

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

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

Αριστερά ο αρχικός γράφος και δεξιά οι αποστάσεις σε κόκκινο για μία από τις κορυφές του πλήρους γράφου ${\displaystyle K_{6}}$.

Δείτε επίσης

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

Παραπομπές

1. Diestel, Reinhard. Graph theory (3η έκδοση). Berlin Heidelberg: Springer. ISBN 9783540261834.
2. Δημήτριος Μ. Θηλυκός. «Σημειώσεις στη θεωρία γραφημάτων» (PDF). Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών. Ανακτήθηκε στις 2 Ιανουαρίου 2024.
3. Συμβώνης, Α. «Θεωρία Γραφημάτων: 3η Διάλεξη» (PDF). Εθνικό Μετσόβειο Πολυτεχνείο. Ανακτήθηκε στις 2 Ιανουαρίου 2024.
4. Καβρουδάκης, Δημήτρης. «Εισαγωγή στην θεωρία γράφων» (PDF). Τμήμα Γεωγραφίας, Πανεπιστήμιο Αιγαίου. Ανακτήθηκε στις 2 Ιανουαρίου 2024.