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

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

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




Τελική βαθμολογία Ιανουαρίου 2018. Μπορείτε να δείτε το γραπτό σας, Παρασκευή 16.02.2018, ώρα 13:00-14:00.

 


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


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

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

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

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

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

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

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



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

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

Θα έχουμε κάποια σύνολα ασκήσεων και ένα τελικό διαγώνισμα.

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

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

Σημειώσεις

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

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

Διάλεξη 1: εισαγωγικοί ορισμοί
Διάλεξη 2: κορυφοδιαχωριστές, συνεκτικότητα
Διάλεξη 3: ακμοδιαχωριστές, ακμοσυνεκτικότητα
Διάλεξη 4: Θεώρημα του Menger
Διάλεξη 5: εναλλακτική απόδειξη και συνέπειες Θ. Menger
Διάλεξη 6: Θ. Menger (συνέχεια), ταιριάσματα, Θεώρημα Hall
Διάλεξη 7: ταιριάσματα και καλύμματα κορυφών ή ακμών
Διάλεξη 8: Θεώρημα του Tutte
Διάλεξη 9: Θεώρημα του Tutte (συνέχεια)
Διάλεξη 10: εμβαπτίσεις γραφημάτων, επίπεδα γραφήματα (τροποποίηση: Wed Nov 29 19:11:43 EET 2017)
Διάλεξη 11: βασικές ιδιότητες επίπεδων γραφημάτων, εξωεπιπεδότητα
Διάλεξη 12: εξωεπίπεδα γραφήματα, ισοδύναμες εμβαπτίσεις (τροποποίηση: Wed Nov 29 19:25:43 EET 2017)
Διάλεξη 13: μοναδικές εμβαπτίσεις, Θεώρημα του Whitney (τροποποίηση: Thu Nov 30 12:06:50 EET 2017)
Διάλεξη 14: πλάτος μονοπατιού (τροποποίηση: Mon Jan 15 13:23:16 EET 2018)
Διάλεξη 15: πλάτος μονοπατιού σε δέντρα (άνω φράγμα)
Διάλεξη 16: πλάτος μονοπατιού σε δέντρα (κάτω φράγμα), εύρεση μέγιστου ανεξάρτητου συνόλου (τροποποίηση: Fri Jan 12 14:35:09 EET 2018)
Διάλεξη 17: δενδροπλάτος
Διάλεξη 18: δενδροπλάτος (συνέχεια)
Διάλεξη 19: σχέση δενδροπλάτους και πλάτους μονοπατιού, εναλλακτικοί ορισμοί (τροποποίηση: Mon Jan 15 13:23:16 EET 2018)
Διάλεξη 20: χρωματισμός γραφημάτων (τροποποίηση: Thu Dec 7 14:08:34 EET 2017)
Διάλεξη 21: Θεώρημα του Brooks (τροποποίηση: Wed Nov 29 18:44:37 EET 2017)
Διάλεξη 22: Θεώρημα του Heawood, κατασκευή Mycielski
Διάλεξη 23: χρωματισμός και περιφέρεια γραφημάτων, ακμοχρωματισμός


Συνοδευτικό υλικό για πλάτος μονοπατιού (σύνολο παρεμπόδισης για pw=2) και για γραφήματα με φραγμένο δενδροπλάτος.

Η Θεωρία Γραφημάτων έχει πλήθος εφαρμογών στα πιο διαφορετικά επιστημονικά πεδία. Εδώ είναι μία από αυτές.

Ασκήσεις προετοιμασίας

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

Πρώτο σετ ασκήσεων προετοιμασίας (Ανακοίνωση: Fri Oct 6 16:54:48 EEST 2017)

Δεύτερο σετ ασκήσεων προετοιμασίας (Ανακοίνωση: Wed Nov 1 11:00:46 EET 2017)

Τρίτο σετ ασκήσεων προετοιμασίας (Ανακοίνωση: Tue Nov 28 16:43:28 EET 2017)

Τέταρτο σετ ασκήσεων προετοιμασίας (Ανακοίνωση: Tue Dec 5 17:16:24 EET 2017)

Ασκήσεις

Πρώτη άσκηση (Ανακοίνωση: Thu Oct 19 16:15:13 EEST 2017, παράδοση μέχρι: 01.11.2017, ώρα 11:00)
(Διορθώθηκε η συνθήκη στο d στο Πρόβλημα 4, Fri Oct 27 13:44:10 EEST 2017)

Δεύτερη άσκηση (Ανακοίνωση: Wed Nov 8 09:48:20 EET 2017, παράδοση μέχρι: 16.11.2017, ώρα 11:00)

Τρίτη άσκηση (Ανακοίνωση: Fri Dec 22 14:03:40 EET 2017, διόρθωση Sun Jan 7 19:37:48 EET 2018, παράδοση μέχρι: 10.01.2018, ώρα 11:00)




http://www.di.uoa.gr/~sgk/teaching/GT/index.html
Τελευταία ανανέωση: Thu Feb 15 12:22:03 EET 2018