Θεωρία Γραφημάτων και Εφαρμογές

Θεωρία Γραφημάτων και Εφαρμογές

Κωδικός:
Εξάμηνο:
Είδος:
Ροή:

ICE-8108
8ο
Επιλογής Υποχρεωτικό (ΕΥ)
Λογισμικού και Πληροφοριακών Συστημάτων

Ώρες:
Διδάσκοντες:
Σύνδεσμοι:

2 Θ – 1 ΑΠ/Φ- 1 Ε
Δημήτριος Μάγος (ΔΕΠ), Γραμματή Πάντζιου (ΔΕΠ)

Περιγραφή

Βασικοί ορισμοί, ιδιότητες και θεωρήματα. Τα γραφήματα σαν μοντέλα πρακτικών εφαρμογών. Απεικονίσεις γραφημάτων: πίνακες γειτνίασης και πρόσπτωσης και ιδιότητες τους. Γραφικές ακολουιθείες. Διαδρομές, Μονοπάτια και Κύκλοι. Συνδεσιμότητα: γέφυρες και σημεία κοπής. Διμερή γραφήματα. Πράξεις σε γαρφληματα. Κύκλωμα Euler, αναγκαίες και ικανές συνθήκες ύπαρξης, Κύκλος Hamilton, Θεωρημα Galais – Ore. Ισομορφισμοί, Ομομορφισμοί και Αυτομορφισμοί- κλάσεις γραφημάτων και απαριθμήσεις . Χρωματισμοί γραφημάτων. Επιπεδότητα και Δυϊκότητα σε γραφήματα. Δένδρα. Ταιριάσματα. Αναξάρτητα σύνολα και κάλυψη κόμβων. Κατεθυνόμενα γραφήματα.