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

ΠΠΣ (ΘΠ10) -- ΠΜΣ (Μ152) -- ΜΠΛΑ -- ΑΛΜΑ
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Χειμερινό Εξάμηνο 2016-2017

Ώρες διδασκαλίας: Τετάρτη 11:00-13:00, Αίθουσα ΣΤ & Πέμπτη 11:00-13:00, Αίθουσα Z.
Διδάσκων: Σταύρος Κολλιόπουλος
Email: id@host.uoa.gr όπου id sgk και host di
Ώρες επικοινωνίας: Τετάρτη, 14:00 - 15:00 στο γραφείο Β6 ή με ραντεβού.




 
 


 
Η δήλωση του μαθήματος την κατάλληλη εξεταστική περίοδο είναι υποχρέωση του φοιτητή. Ο διδάσκων δεν αναλαμβάνει καμία ευθύνη για την έκδοση ή αρχειοθέτηση αποτελεσμάτων για όσους/όσες δεν εμφανίζονται στις επίσημες καταστάσεις. H ένδειξη "εκτός λίστας" δεν εξαντλεί απαραίτητα όλες τις σχετικές περιπτώσεις.
 


Γενικές Πληροφορίες

Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/GT/. (Επίσης μέσω http://eclass.uoa.gr/).
Περιέχει χρήσιμες πληροφορίες, συνιστάται να την επισκέπτεστε συχνά. Εκεί θα βρίσκετε πληροφορίες για το μάθημα, σημειώσεις, ασκήσεις, ανακοινώσεις, κλπ.

Περιγραφή μαθήματος:

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

Μια ενδεικτική λίστα θεμάτων που θα μας απασχολήσουν:

Συγγράμματα: Υπάρχουν πολύ καλά εγχειρίδια στην Αγγλική γλώσσα που καλύπτουν την ύλη του μαθήματος, όπως:

Δεκάδες (κυριολεκτικά) άλλες πηγές κάθε είδους είναι διαθέσιμες στο διαδίκτυο.



Διαδικαστικά

Εξετάσεις - Ασκήσεις - Βαθμολογία:

Θα έχουμε κάποια σύνολα ασκήσεων και ένα τελικό διαγώνισμα. Σε κάθε διάλεξη, κυκλικά, ένας φοιτητής/μία φοιτήτρια θα κρατάει σημειώσεις, υποχρεωτικά σε LaTex, χρησιμοποιώντας το αρχείο μορφοποίησης scribe-gr.sty. Ένα υπόδειγμα σημειώσεων βρίσκεται εδώ και όλα τα σχετικά πηγαία αρχεία εδώ . Οι σημειώσεις συνεισφέρουν 20% στον τελικό βαθμό. Είναι υποχρεωτικές για τους μεταπτυχιακούς φοιτητές. To κάθε σετ σημειώσεων θα πρέπει να παραδίδεται σε τελική μορφή μία εβδομάδα μετά την αντίστοιχη παράδοση. Δεν δίνεται όμως εγγύηση για τον ακριβή χρόνο ανάρτησης του. H τελική μορφή προϋποθέτει έλεγχο από το διδάσκοντα και συνεργασία για τη διόρθωση τυχόν λαθών. Για τους προπτυχιακούς φοιτητές που ενδιαφέρονται θα τηρηθεί σειρά προτεραιότητας.

Το τελικό διαγώνισμα θα μετρήσει (100-f(Χ)*10 - Υ)% στον τελικό βαθμό, όπου Χ το πλήθος των ασκήσεων και 0<= Υ <= 20, η συμμετοχή των σημειώσεων. Η συνάρτηση f(X) ορίζεται ως το κάτω ακέραιο μέρος του (Χ/2 +1/2). Η συνολική βαθμολογία σε όλες τις ασκήσεις θα καθορίσει ποσοστό f(Χ)*10 του τελικού βαθμού.

Η οριστικοποίηση του βαθμού των ασκήσεων θα γίνεται ύστερα από προφορική εξέταση. Αντιγραφή από οποιαδήποτε πηγή οδηγεί σε μηδενισμό για ολόκληρο το ακαδημαϊκό έτος.
Δεν θα σταλεί βαθμός για τους μεταπτυχιακούς που δεν έρχονται τακτικά, κατά την κρίση του διδάσκοντα, στις παραδόσεις.
Οι προπτυχιακοί που δεν θα έρθουν σε όλες τις παραδόσεις θα έχουν σοβαρή δυσκολία στην κατανόηση της ύλης.
Θα υπάρξουν διαφορές στα θέματα μεταξύ των προπτυχιακών και μεταπτυχιακών φοιτητών. Στην πορεία θα εξεταστεί αν χρειάζεται και κάποια (μικρή) διαφοροποίηση της ύλης.
Για να περάσετε το μάθημα πρέπει να έχετε τουλάχιστον 5 στο τελικό διαγώνισμα, ακόμα και αν και η συνεισφορά των ασκήσεων και των σημειώσεων είναι υψηλή.

Σημειώσεις

Προειδοποίηση: Έχει καταβληθεί προσπάθεια ώστε οι παρακάτω σημειώσεις να μην περιέχουν λάθη ή ασάφειες. Δεν δίνεται όμως εγγύηση.

Δεν επιτρέπεται η αναπαραγωγή ή ιδιοποίηση αυτών των σημειώσεων με σκοπό το κέρδος ή άλλα προσωπικά οφέλη.

Διάλεξη 1: εισαγωγικοί ορισμοί
Διάλεξη 2: κορυφοδιαχωριστές, συνεκτικότητα (Προσθήκη: Thu Nov 3 15:27:54 EET 2016)
Διάλεξη 3: ακμοδιαχωριστές, ακμοσυνεκτικότητα (Προσθήκη: Mon Nov 14 14:16:01 EET 2016)
Διάλεξη 4: Θεώρημα του Menger
Διάλεξη 5: εναλλακτική απόδειξη και συνέπειες Θ. Menger (Προσθήκη: Mon Nov 14 14:16:01 EET 2016, ανανέωση: Sat Jan 7 12:16:21 EET 2017)
Διάλεξη 6: Θ. Menger (συνέχεια), ταιριάσματα, Θεώρημα Hall (Προσθήκη: Fri Nov 18 19:28:07 EET 2016)
Διάλεξη 7: ταιριάσματα και καλύμματα κορυφών ή ακμών (Προσθήκη: Thu Dec 8 16:03:24 EET 2016)
Διάλεξη 8: Θεώρημα Tutte (Προσθήκη: Thu Dec 15 13:48:03 EET 2016)
Διάλεξη 9: Θεώρημα Tutte (συνέχεια) (Προσθήκη: Tue Jan 3 14:12:20 EET 2017)
Διάλεξη 10: εμβαπτίσεις γραφημάτων, επίπεδα γραφήματα (Προσθήκη: Wed Dec 14 16:43:53 EET 2016)
Διάλεξη 11: βασικές ιδιότητες επίπεδων γραφημάτων, εξωεπιπεδότητα (Προσθήκη: Tue Dec 6 17:36:26 EET 2016)
Διάλεξη 12: εξωεπίπεδα γραφήματα, ισοδύναμες εμβαπτίσεις
Διάλεξη 13: μοναδικές εμβαπτίσεις, Θεώρημα Whitney
Διάλεξη 14: πλάτος μονοπατιού
Διάλεξη 15: πλάτος μονοπατιού σε δέντρα (άνω φράγμα)
Διάλεξη 16: πλάτος μονοπατιού σε δέντρα (κάτω φράγμα), εύρεση μέγιστου ανεξάρτητου συνόλου (Προσθήκη: Wed Jan 11 23:55:17 EET 2017)
Διάλεξη 17: δενδροπλάτος
Διάλεξη 18: δενδροπλάτος (συνέχεια) (Προσθήκη: Sat Jan 7 12:16:21 EET 2017)
Διάλεξη 19: σχέση δενδροπλάτους και πλάτους μονοπατιού, εναλλακτικοί ορισμοί (Προσθήκη: Sat Jan 14 10:41:16 EET 2017, ανανέωση Tue Jan 17 13:20:13 EET 2017)
Διάλεξη 20: χρωματισμός γραφημάτων (Προσθήκη: Wed Jan 11 23:55:17 EET 2017)
Διάλεξη 21: Θεώρημα του Brooks
Διάλεξη 22: Θεώρημα Heawood, κατασκευή Mycielski (Προσθήκη: Thu Jan 19 15:28:35 EET 2017)
Διάλεξη 23: χρωματισμός και περιφέρεια γραφημάτων, ακμοχρωματισμός


Συνοδευτικό υλικό για πλάτος μονοπατιού (σύνολο παρεμπόδισης για pw=2) και για γραφήματα με φραγμένο δενδροπλάτος. (Προσθήκη: Thu Dec 8 16:03:24 EET 2016)

Ασκήσεις

Πρώτη άσκηση (Ανακοίνωση: Thu Oct 13 13:13:33 EEST 2016, παράδοση μέχρι: 20.10.2016, ώρα 11:00) | Βαθμολογία (Προσθήκη Wed Nov 2 18:09:25 EET 2016)

Δεύτερη άσκηση (Ανακοίνωση: Wed Nov 2 18:09:25 EET 2016, παράδοση μέχρι: 11.11.2016 ώρα 11:00)| Βαθμολογία (Προσθήκη Fri Nov 25 11:12:27 EET 2016)

Τρίτη άσκηση (Ανακοίνωση: Tue Dec 6 17:28:29 EET 2016, παράδοση μέχρι: 15.12.2016 ώρα 11:00)|




http://www.di.uoa.gr/~sgk/teaching/GT/index.html
Τελευταία ανανέωση: Thu Jul 20 18:49:26 EEST 2017