Πλήρης γράφος
Εμφάνιση
Πλήρης γράφος | |
---|---|
![]() , ένας πλήρης γράφος με 7 κόμβους | |
Κορυφές | |
Ακμές | |
Ακτίνα | |
Διάμετρος | |
Περιφέρεια | |
Αυτομορφισμοί | n! (Sn) |
Χρωματικός αριθμός | |
Ιδιότητες | |
Συμβολισμός | |
Πίνακας γράφων και των παραμέτρων τους |
Στην θεωρία γράφων, ο πλήρης γράφος είναι ο γράφος όπου όλοι οι κόμβοι συνδέονται με όλους τους άλλους κόμβους.[1][2]:5[3]:21
Παραδείγματα
[Επεξεργασία | επεξεργασία κώδικα]- Μία ομάδα από ανθρώπους όπου όλοι είναι φίλοι με όλους.
- Πλήρεις γράφοι με κόμβους, για μεταξύ 1 και 12, δίνονται παρακάτω μαζί με το πλήθος των ακμών:
K1: 0 | K2: 1 | K3: 3 | K4: 6 |
---|---|---|---|
![]() |
![]() |
![]() |
![]() |
K5: 10 | K6: 15 | K7: 21 | K8: 28 |
![]() |
![]() |
![]() |
![]() |
K9: 36 | K10: 45 | K11: 55 | K12: 66 |
![]() |
![]() |
![]() |
![]() |
Ιδιότητες
[Επεξεργασία | επεξεργασία κώδικα]- Ο πλήρης γράφος με κόμβους έχει ακμές.
(Απόδειξη) Σε αντικείμενα υπάρχουν διαφορετικοί τρόποι να διαλέξουμε αντικείμενα. Επομένως, από τον ορισμό των δυωνυμικών συντελεστών, υπάρχουν ακμές στον πλήρη γράφο.
- Στον πλήρη γράφο όλοι οι κόμβοι είναι γειτονικοί, άρα σε έναν χρωματισμό πρέπει να έχουν διαφορετικό χρώμα. Επομένως, ο χρωματικός του αριθμός είναι και το χρωματικό του πολυώνυμο είναι .
- Ο πλήρης γράφος με δεν έχει κύκλο άρα η περιφέρειά του είναι . Για , ο γράφος περιέχει τρίγωνα άρα η περιφέρεια είναι .
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Diestel, Reinhard. Graph theory (3η έκδοση). Berlin Heidelberg: Springer. ISBN 9783540261834.
- ↑ Δημήτριος Μ. Θηλυκός. «Σημειώσεις στη θεωρία γραφημάτων» (PDF). Εθνικός και Καποδιστριακόν Πανεπιστήμιον Αθηνών. Ανακτήθηκε στις 2 Ιανουαρίου 2024.
- ↑ Φωτάκης, Δ.· Σούλιου, Δ. «Θεωρία Γραφηµάτων: Ορολογία και Βασικές Έννοιες» (PDF). Εθνικό Μετσόβιο Πολυτεχνείο. Ανακτήθηκε στις 2 Ιανουαρίου 2024.