ΠΛΗ20 Μάθημα 4.3 – Διαμερίσεις και Χρωματισμοί


Στόχοι του Μαθήματος

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

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

Σύντομη Παρουσίαση

Με μια ματιά το μάθημα:

  • ΚΑΡΤΑ: Διχοτομίσιμο (ή Διμερές) Γράφημα
  • ΚΑΡΤΑ: Πλήρες Διχοτομίσιμο Γράφημα
  • ΚΑΡΤΑ: Σύνολο Ανεξαρτησίας
  • ΚΑΡΤΑ: k-Χρωματίσιμο Γράφημα
  • ΚΑΡΤΑ: Χρωματικός Αριθμός


Σχολιασμός (βίντεο)

Αναλυτική Παρουσίαση

ΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ:

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) Χρωματικός Αριθμός
Ασκήσεις

Παρουσίαση τουΜαθήματος:


ΒΙΝΤΕΟ ΜΑΘΗΜΑΤΟΣ και ΣΧΟΛΙΑΣΜΟΣ

ΣΥΜΒΟΥΛΕΣ

 two-face.200  batman.200
ΚατηγορίαΧΔΣχόλιο
Θεωρία 1 από 2Διαμερίσεις (Διχοτομίσιμο, Πλήρες Διχοτομίσιμο Γράφημα, Σύνολο Ανεξαρτησίας)
Θεωρία 2 από 2Χρωματισμοί (k-Χρωματίσιμο Γράφημα, Χρωματικός Αριθμός)
Κατανόηση 141Μελέτη των ορισμών του μαθήματος στις Κλίκες
Κατανόηση 241Μελέτη των ορισμών του μαθήματος στους Κύκλους
Κατανόηση 341Μελέτη των ορισμών του μαθήματος στους Τροχούς
Κατανόηση 441Μελέτη των ορισμών του μαθήματος στα Μονοπάτια
Ερωτήσεις 142Εξάσκηση στους χρωματικούς αριθμούς για συγκεκριμένες οικογένειες γραφημάτων.
Ερωτήσεις 242Συνδυαστική άσκηση και με τους ορισμούς των προηγούμενων μαθημάτων
Εφαρμογή 142Χρήσιμη απόδειξη επαγωγής για τον τύπο των ακμών του πλήρους διμερούς γραφήματος
Εφαρμογή 242Ελάχιστος και Μέγιστος Βαθμός Κορυφής σε Διχοτομίσιμο Γράφημα
Εφαρμογή 342Απόδειξη του 3ου ορισμού του διχοτομίσιμου γραφήματος

Περαιτέρω Εξάσκηση

(-)

Πηγές και Διαδίκτυο

Οι Λυμένες Ασκήσεις είναι θέματα εξετάσεων του ΕΑΠ

Εκτυπώσιμη μορφή αρχείων PDF