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

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

Πλήρης γράφος
$K_{7}$, ένας πλήρης γράφος με 7 κόμβους
Κορυφές	$n$
Ακμές	$\textstyle {\frac {n(n-1)}{2}}$
Ακτίνα	$\left\{{\begin{array}{ll}0&{\text{αν }}n\leq 1,\\1&{\text{διαφορετικά}}.\end{array}}\right.$
Διάμετρος	$\left\{{\begin{array}{ll}0&{\text{αν }}n\leq 1,\\1&{\text{διαφορετικά}}.\end{array}}\right.$
Περιφέρεια	$\left\{{\begin{array}{ll}\infty &{\text{αν }}n\leq 2,\\3&{\text{διαφορετικά}}.\end{array}}\right.$
Αυτομορφισμοί	n! (Sn)
Χρωματικός αριθμός	$n$
Ιδιότητες	(n − 1)-κανονικός Συμμετρικός γράφος Γράφος διαστημάτων
Συμβολισμός	$K_{n}$
Πίνακας γράφων και των παραμέτρων τους

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

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

• Πλήρεις γράφοι με $n$ κόμβους, για $n$ μεταξύ 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

Ιδιότητες

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

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

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

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

Δείτε επίσης

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