Πλήρης γράφος

Στην θεωρία γράφων, ο πλήρης γράφος  είναι ο γράφος όπου όλοι οι κόμβοι συνδέονται με όλους τους άλλους κόμβους.

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

 Μία ομάδα από ανθρώπους όπου όλοι είναι φίλοι με όλους.

 Πλήρεις γράφοι με  κόμβους, για  μεταξύ 1 και 12, δίνονται παρακάτω μαζί με το πλήθος των ακμών:
     140px 140px 140px 140px     140px 140px 140px 140px     140px 140px 140px 140px

 Ιδιότητες 
 Ο πλήρης γράφος  με  κόμβους έχει  ακμές.

 Στον πλήρη γράφο  όλοι οι κόμβοι είναι γειτονικοί, άρα σε έναν χρωματισμό πρέπει να έχουν διαφορετικό χρώμα. Επομένως, ο χρωματικός του αριθμός είναι  και το χρωματικό του πολυώνυμο είναι 
.

 Ο πλήρης γράφος με  δεν έχει κύκλο άρα η περιφέρειά του είναι . Για , ο γράφος περιέχει τρίγωνα άρα η περιφέρεια είναι .

 Δείτε επίσης 
 Πλήρης διμερής γράφος
 Αστεροειδής γράφος
 Τρίγωνο (θεωρία γράφων)

 Παραπομπές 

Κατηγορία:Θεωρία γράφων