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

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

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




Η εγγραφή στην η-τάξη είναι απαραίτητη για όποιον επιθυμεί να παρακολουθήσει το μάθημα ή να εξεταστεί σε αυτό ώστε να λαμβάνει έγκαιρα τις ανακοινώσεις του μαθήματος.


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


 


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

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

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

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

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

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

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



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

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

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

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

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

Σε περίπτωση που η τελική εξέταση είναι γραπτή ο διδάσκων διατηρεί το δικαίωμα για δειγματοληπτική, πρόσθετη, προφορική εξέταση.

Σημειώσεις

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

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

Διάλεξη 1: εισαγωγικοί ορισμοί (ανανέωση: Mon Apr 19 17:41:48 EEST 2021)
Διάλεξη 2: κορυφοδιαχωριστές, συνεκτικότητα
Διάλεξη 3: ακμοδιαχωριστές, ακμοσυνεκτικότητα
Διάλεξη 4: Θεώρημα του Menger (ανανέωση: Sat Mar 18 13:47:20 EET 2023)
Διάλεξη 5: εναλλακτική απόδειξη και συνέπειες Θ. Menger
Διάλεξη 6: Θ. Menger (συνέχεια), ταιριάσματα, Θεώρημα Hall (ανανέωση: Sat Mar 18 13:47:20 EET 2023)
Διάλεξη 61: Ο αλγόριθμος του Karger για την εύρεση ελάχιστης τομής. Σημειώσεις εδώ ή εδώ.
Διάλεξη 7: ταιριάσματα και καλύμματα κορυφών ή ακμών (ανανέωση: Wed May 4 17:58:17 EEST 2022)
Διάλεξη 8: Θεώρημα του Tutte (ανανέωση: Mon Apr 19 17:41:48 EEST 2021)
Διάλεξη 9: Πορίσματα του Θεωρήματος του Tutte (ανανέωση: Mon Apr 19 17:41:48 EEST 2021)
Διάλεξη 91: O αλγόριθμος του Edmonds (ανανέωση: Wed Apr 5 12:32:11 EEST 2023)
Διάλεξη 10: εμβαπτίσεις γραφημάτων, επίπεδα γραφήματα (ανανέωση: Thu Apr 22 16:26:28 EEST 2021)
Διάλεξη 11: βασικές ιδιότητες επίπεδων γραφημάτων, εξωεπιπεδότητα (ανανέωση: Fri Apr 23 15:05:29 EEST 2021)
Διάλεξη 12: εξωεπίπεδα γραφήματα, ισοδύναμες εμβαπτίσεις
Διάλεξη 13: μοναδικές εμβαπτίσεις, Θεώρημα του Whitney
Διάλεξη 14: πλάτος μονοπατιού (ανανέωση: Wed May 25 19:28:21 EEST 2022)
Διάλεξη 15: πλάτος μονοπατιού σε δέντρα (άνω φράγμα)
Διάλεξη 16: πλάτος μονοπατιού σε δέντρα (κάτω φράγμα), εύρεση μέγιστου ανεξάρτητου συνόλου (ανανέωση: Wed May 25 19:28:21 EEST 2022)
Διάλεξη 17: δενδροπλάτος
Διάλεξη 18: δενδροπλάτος (συνέχεια)
Διάλεξη 19: σχέση δενδροπλάτους και πλάτους μονοπατιού, εναλλακτικοί ορισμοί
Διάλεξη 20: χρωματισμός γραφημάτων
Διάλεξη 21: Θεώρημα του Brooks
Διάλεξη 22: Θεώρημα του Heawood, κατασκευή Mycielski
Διάλεξη 23: χρωματισμός και περιφέρεια γραφημάτων, ακμοχρωματισμός


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

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

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

Δεν υπάρχουν ανακοινωμένες ασκήσεις.



http://www.di.uoa.gr/~sgk/teaching/GT/index.html
Τελευταία ανανέωση: Tue Mar 26 11:54:15 EET 2024