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

Εξάμηνο:
8ο
Τύπος Μαθήματος:
Προαιρετικό Μάθημα (ΠΜ)
Κατεύθυνση:
Α, Β
Κωδικός:
ΘΠ10
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (Ε1):
(B) Βασικό
Διαχείριση Δεδομένων και Γνώσης (Ε2):
-
Λογισμικό (Ε3):
-
Υλικό και Αρχιτεκτονική (Ε4):
-
Επικοινωνίες και Δικτύωση (Ε5):
(E) Επιλογής
Επεξεργασία Σήματος και Πληροφορίας (Ε6):
-
Σχετικά Μαθήματα
Περιγραφή Μαθήματος

Μονοπάτια, δέντρα. Κορυφοδιαχωριστές, ακμοδιαχωριστές, συνεκτικότητα. Θεώρημα του 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

Αναλυτική Περιγραφή