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