Θεωρία και Αλγόριθμοι Γράφων

Διδάσκοντες: Ιωάννης Μανωλόπουλος, Καθηγητής

Yannis Manolopoulos is Professor with the Department of Informatics of the Aristotle University of Thessaloniki. He has been with the University of Toronto, the University of Maryland at College Park and the University of Cyprus. He has also served as Rector of the University of Western Macedonia in Greece, Head of his own department, and Vice-Chair of the Greek Computer Society. His research interest focuses in Data Management. He has co-authored 5 monographs and 8 textbooks in Greek, as well as >300 journal and conference papers. He has received >9000 citations from >1300 distinct academic institutions (h-index=44). He has also received 3 best paper awards from SIGMOD, ECML/PKDD and MEDES conferences and has been invited as keynote speaker in 10 international events. He has served as main co-organizer of several major conferences (among others): ADBIS 2002, SSTD 2003, SSDBM 2004, ICEIS 2006, EANN 2007, ICANN 2010, AIAI 2012, WISE 2013, CAISE 2014, MEDI 2015. He has also acted as evaluator for funding agencies in Austria, Canada, Cyprus, Czech Republic, Estonia, EU, Hong-Kong, Georgia, Greece, Israel, Italy and Russia. Currently, he serves in the Editorial Boards of (among others) The VLDB Journal, The World Wide Web Journal, The Computer Journal.

Συνεργάτης Ανάπτυξης Περιεχομένου: Ανδρέας Κοσματόπουλος

• Εισαγωγικά Στοιχεία
• Μονοπάτια και κύκλοι
• Δένδρα
• Συνδεσμικότητα
• Επιπεδικότητα
• Χρωματισμός
• Κατευθυνόμενοι Γράφοι
• Αντιστοιχίσεις και καλύμματα
• Δίκτυα και ροές

Εισαγωγή στη θεωρία γράφων. Κατανόηση της δομής των γράφων και των βασικών θεωρημάτων αυτών. Γνωριμία με τις βασικές εφαρμογές της θεωρίας γράφων. Βαθύτερη μελέτη ειδικών θεμάτων όπως συνδεσμικότητα, χρωματισμός, επιπεδικότητα, ροής δικτύων και δένδρων. Απόκτηση ικανότητας εφαρμογής τεχνικών και αλγορίθμων της θεωρίας γράφων όπως οι αλγόριθμοι εύρεσης ελαχίστων ζευγνυόντων δένδρων.

Βασικές γνώσεις αλγορίθμων

Το μάθημα βασίζεται στο βιβλίο “Θεωρία και Αλγόριθμοι Γράφων”, Ι. Μανωλόπουλος, Α. Παπαδόπουλος, Κ. Τσίχλας, Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 2014.

Επιπλέον συνιστώμενη βιβλιογραφία

Ι. Μανωλόπουλος: "Μαθήματα Θεωρίας Γράφων: Θεμελιώσεις-Αλγόριθμοι-Εφαρμογές", Εκδόσεις Νέων Τεχνολογιών, Αθήνα, 1996.

J. Gross and J. Yellen: "Graph Theory and its Applications", 2nd edition, CRC Press, 2006.

J. Gross and J. Yellen: Handbook of Graph Theory, CRC Press, 2003.

Οι φοιτητές του τμήματος Πληροφορικής ενδιαφερόμενοι για τη θεματική περιοχή της θεωρίας γράφων και των αλγορίθμων αυτής.

Πρόσωπο με πρόσωπο, διδασκαλία καθ’ έδρας.

Γραπτές εξετάσεις ή εργασία. Η ακριβής διαδικασία και βαρύτητα ανακοινώνεται στην ιστοσελίδα.

Μέθοδοι Αξιολόγησης Φοιτητών

Ερωτήσεις Σύντομης Απάντησης

Γραπτή Εργασία