5.2 Μερικά ειδικά γραφήματα

Το κενό γράφημα με $n$ κορυφές έχει σύνολο κορυφών $[n]={\left\{{1,\ldots,n}\right\}}$ και σύνολο ακμών $E = \emptyset$. Το συμβολίζουμε με $E_n$.

Το πλήρες γράφημα με $n$ κορυφές έχει σύνολο κορυφών $[n]$ και όλες τις δυνατές ακμές, δηλ. $E$ = όλα τα διμελή υποσύνολα του $[n]$. Συμβολίζεται με $K_n$ και έχει ${n\choose 2} = {n(n-1) \over 2}$ ακμές. Το αριστερό γράφημα στο Σχ. 5.10 είναι το $K_5$.

Το πλήρες διμερές γράφημα με $m$ και $n$ κορυφές έχει σύνολο κορυφών το $V=A \cup B$, με $A={\left\{{a_1,\ldots,a_m}\right\}}$, $B={\left\{{b_1,\ldots,b_n}\right\}}$, και $a_i \sim b_j$, για κάθε $i=1,\ldots,m$, $j=1,\ldots,n$. Συμβολίζεται με $K_{m,n}$ και έχει $m\cdot n$ ακμές. Δείτε το Σχήμα 5.8 για παράδειγμα.

Σχήμα 5.8: Το πλήρες διμερές γράφημα $K_{4,3}$ με $A={\left\{{1,2,3,4}\right\}}, B={\left\{{\alpha,\beta,\gamma}\right\}}$ και το πλήρες διμερές γράφημα $K_{3,1}$, ζωγραφισμένο με ασυνήθιστο τρόπο, με $A={\left\{{a, b, c}\right\}}, B={\left\{{d}\right\}}$.

Ο κύκλος με $n$ κορυφές έχει σύνολο κορυφών το $[n]$ και $i \sim j$ αν και μόνο αν ${\left\vert{i-j}\right\vert}=1$ ή ${\left\{{i,j}\right\}} = {\left\{{1,n}\right\}}$. Συμβολίζεται με $C_n$ και έχει $n$ ακμές. Δείτε το Σχήμα 5.9 για παράδειγμα.

Σχήμα 5.9: Ο κύκλος $C_6$