Θεωρία Γραφημάτων

Εξάμηνο:
8ο
Τύπος Μαθήματος:
Προαιρετικό (ΠΜ)
Κατεύθυνση:
CS (Computer Science), CΕT (Computer Engineering and Telecoms)
Κωδικός:
ΘΠ10
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
B Βασικό
Διαχείριση Δεδομένων και Γνώσης (S2):
-
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
-
Σχετικά Μαθήματα
Υποχρεωτικά Προαπαιτούμενα:
Συνιστώμενα Προαπαιτούμενα:
-
Αναλυτική Περιγραφή
DIT_PPS_ΘΠ10-Θεωρία Γραφημάτων.pdf
Σύντομη περιγραφή Μαθήματος
Μονοπάτια, δέντρα. Κορυφοδιαχωριστές, ακμοδιαχωριστές, συνεκτικότητα. Θεώρημα του Menger. Ταιριάσματα. Θεώρημα του Tutte. Καλύμματα κορυφών. Επιπεδότητα, εξωεπιπεδότητα. Μοναδικές Εμβαπτίσεις. Θεώρημα του Whitney. Πλάτος μονοπατιού, δενδροπλάτος. Χρωματισμός γραφημάτων. Θεώρημα του Brooks. Κατασκευή Mycielski.
Βιβλιογραφία
Σ. Κολλιόπουλος, Σημειώσεις. Rheihnard Diestel. Graph Theory, 5th Edition, Springer, 2016. Douglas B. West. Introduction to Graph Theory, 2nd Edition, Pearson, 2001 K.H. Rosen. Διακριτά Μαθηματικά και Εφαρμογές τους. 7η Έκδοση, Εκδόσεις Τζιόλα, 2015
e-Class link
Θεωρία Γραφημάτων - ECLASS

Διδάσκων