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