ΠΛΗ20 - ΜΑΘΗΜΑ 4.3 - ΔΙΑΜΕΡΙΣΕΙΣ ΚΑΙ ΧΡΩΜΑΤΙΣΜΟΙ - ΛΥΜΕΝΕΣ ΑΣΚΗΣΕΙΣ 3

1) Διχοτομίσιμο και Πλήρες Διχοτομίσιμο Γράφημα
1.1) Διχοτομίσιμο Γράφημα
1.2) Πλήρες Διχοτομίσιμο Γράφημα
1.3) Σύνολο Ανεξαρτησίας
1.3.1) Ορισμός
1.3.2) Μεγιστοτικό Σύνολο Ανεξαρτησίας
1.3.3) Μέγιστο Σύνολο Ανεξαρτησίας
1.3.4) Πρόσθέτοι Ορισμοί για Διχοτομίσιμο Γράφημα
2) Χρωματισμοί Κορυφών
2.1) K-Χρωματίσιμο Γράφημα
2.2) Χρωματικός Αριθμός
Ασκήσεις

[rqd]

Εφόσον το G έχει χρωματικό αριθμό k αυτό σημαίνει ότι όλες οι κορυφές του διαμερίζονται σε k σύνολα ανεξαρτησίας. Προσθέτω μια κορυφή στο G και την συνδέω με k-1 κορυφές. Οι κ-1 κορυφές μπορούν να ανήκουν το πολύ σε κ-1 σύνολα ανεξαρτησίας, αρα όταν συνδέσω την u με k-1 κορυφές, η u θα ανήκει το πολύ σε k-1 σύνολα ανεξαρτησίας. Αρα θα υπαρχει τουλάχιστον 1 - από k - σύνολο ανεξαρτησίας στο οποίο η u δεν θα ανήκει. Άρα τα k σύνολα ανεξαρτησίας θα συνεχίσουν να είναι ξένα μεταξύ τους. Άρα ο χρωματικός αριθμός θα παραμείνει ο ίδιος, δηλαδή κ.