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

Μαθησιακοί στόχοι

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

Προαπαιτούμενα

Θα ήταν χρήσιμο οι φοιτητές να διαθέτουν στοιχειώδεις γνώσεις Διακριτών Μαθηματικών, Συνδυαστικής, Λογικής και Θεωρίας Συνόλων.

Περιεχόμενο μαθήματος

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

Μέθοδοι αξιολόγησης

Ως επιπλέον κίνητρο, οι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα. Πιο συγκεκριμένα, οι φοιτητές θα κληθούν να σχηματίσουν ομάδες συνεργασίας (μέχρι 3 άτομα ανά ομάδα), οι ομάδες αυτές θα πρέπει να επιλύσουν τις ασκήσεις, να γράψουν τις απαντήσεις τους (κατά προτίμηση σε LaTeX) και να τις καταθέσουν στον διδάσκοντα μέσω της πλατφόρμας «η-τάξη». Η επίλυση των πακέτων ασκήσεων είναι προαιρετική και δίνει την δυνατότητα στους φοιτητές που θα ασχοληθούν με αυτές να βελτιώσουν τον τελικό βαθμό τους κατά το πολύ 1 μονάδα.

Στο τέλος του εξαμήνου οι φοιτητές θα κληθούν να συμμετάσχουν στη γραπτή εξέταση του μαθήματος.

Ο τελικός βαθμός υπολογίζεται ως εξής:

Ασκήσεις: Το πολύ 1 μονάδα (μισή μονάδα για κάθε πακέτο ασκήσεων)

Εξετάσεις: 10 μονάδες

Τελικός βαθμός: min{βαθμός εξέτασης+βαθμός ασκήσεων, 10}

Βιβλιογραφία

• Δημήτριος Μ. Θηλυκός: Σημειώσεις στη Θεωρία Γραφημάτων
• Παναγιώτη Σπύρου: Θεωρία Γραφημάτων  
• Reinhard Diestel: Graph Theory, Springer
• John Adrian Bondy, U. S. R. Murty: Graph Theory With Applications, Elsevier Science Ltd/North-Holland
• Μάριος Μαυρονικόλας: Θεωρία γράφων, Ελληνικό Ανοικτό Πανεπιστήμιο
• Σταύρος Νικολόπουλος, Λουκάς Γεωργιάδης, Λεωνίδας Παληός: Αλγοριθμική θεωρία γραφημάτων,  ΚΑΛΛΙΠΟΣ
• Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης, Γ. Σταματίου: Εισαγωγή στους Γράφους, Gutenberg
• Ι. Μανωλόπουλος, Α. Παπαδόπουλος, Κ. Τσίχλας: Θεωρία και Αλγόριθμοι Γράφων, Εκδόσεις Νέων Τεχνολογιών
• C.L. Liu: Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης 
• Kenneth Rosen: Διακριτά Μαθηματικά και Εφαρμογές τους, Εκδόσεις Τζιόλα
• Sussana S. Epp: Διακριτά Μαθηματικά με εφαρμογές, Εκδόσεις Κλειδάριθμος