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

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

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

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

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

Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math
Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math
Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math	Πρότυπο:Math

Ιδιότητες

• Ο πλήρης γράφος $K_n$ με $n$ κόμβους έχει $\frac{1}{2}\cdot n\cdot (n-1)$ ακμές.

(Απόδειξη) Σε $n$ αντικείμενα υπάρχουν $(\genfrac{}{}{0ex}{}{n}{2})$ διαφορετικοί τρόποι να διαλέξουμε $2$ αντικείμενα. Επομένως, από τον ορισμό των δυωνυμικών συντελεστών, υπάρχουν $\frac{1}{2}n\cdot (n-1)$ ακμές στον πλήρη γράφο.

• Στον πλήρη γράφο $K_n$ όλοι οι κόμβοι είναι γειτονικοί, άρα σε έναν χρωματισμό πρέπει να έχουν διαφορετικό χρώμα. Επομένως, ο χρωματικός του αριθμός είναι $n$ και το χρωματικό του πολυώνυμο είναι $P(G,x)=x\cdot (x-1)\cdot (x-2)\cdot \dots \cdot 2\cdot 1=x!$.

• Ο πλήρης γράφος με $n\le 2$ δεν έχει κύκλο άρα η περιφέρειά του είναι $\mathrm{\infty }$. Για $n\ge 3$, ο γράφος περιέχει τρίγωνα άρα η περιφέρεια είναι $3$.

Δείτε επίσης

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