Θεωρία Γραφημάτων και Εφαρμογές

Σταύρος Κοσμαδάκης

Περιγραφή

ΣΗΜΑΝΤΙΚΗ ΑΝΑΚΟΙΝΩΣΗ  Το μάθημα θα εξεταστεί, το 2021 - 22, με ανοιχτά βιβλία και σημειώσεις. Οι φοιτητές θα μπορούν να έχουν μαζύ τους ΜΟΝΟ το βιβλίο και τις σημειώσεις του διδάσκοντα, και δικές τους χειρόγραφες σημειώσεις. 

Το μάθημα αποτελεί εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων. Δίνεται έμφαση στην περιγραφή και χρήση των εννοιών με μαθηματικά ακριβή τρόπο. Εξετάζεται η εφαρμογή της θεωρίας (i) στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και (ii) στην επαλήθευση της ορθότητας αυτών των αλγορίθμων. Καλύπτονται: Συνεκτικότητα, ισχυρή συνεκτικότητα, δισυνεκτικότητα, επαγωγή και αναδρομή για γραφήματα, βασική θεωρία δέντρων, στοιχειώδεις κύκλοι.

Το κύριο σύγγραμμα του μαθήματος είναι οι διδακτικές σημειώσεις: Εισαγωγή στα Γραφήματα, Θεωρία - Ασκήσεις, του Σ. Κοσμαδάκη. Όλη η απαιτούμενη ύλη, καθώς και η ορολογία που χρησιμοποιείται στις παραδόσεις, καλύπτεται στις διδακτικές σημειώσεις.

Το δεύτερο σύγγραμμα είναι το βιβλίο: Διακριτά μαθηματικά κ

Περισσότερα  
Διδακτικό Υλικό

Στο πεδίο "Έγγραφα" καταχωρούνται:

(i) Τα συγγράμματα του μαθήματος.

(ii) Συμπληρωματικό υλικό (άλλα βιβλία, σημειώσεις κοκ), που μπορεί να χρησιμοποιηθεί ως επιπλέον βοήθημα - για ορισμένα από τα θέματα που καλύπτει το μάθημα.

(iii) Μια σειρά από "Συνοπτικά Μαθήματα" και "Προτεινόμενες Ασκήσεις". 

Τα "Συνοπτικά Μαθήματα" είναι καταγραφές παραδόσεων του μαθήματος - η σειρά τους δεν είναι χρονολογική. Περιέχουν αναλυτικές λεπτομέρειες της ύλης που έχει παρουσιαστεί στις παραδόσεις, μαζύ με επιπλέον παραδείγματα, παρατηρήσεις κλπ. Δίνονται παραπομπές σε σχετικά μέρη του άλλου διδακτικό υλικού, για επιπλέον μελέτη.

Οι "Προτεινόμενες Ασκήσεις" είναι ενδεικτικές του αναμενόμενου επιπέδου κατανόησης, της σχετικής ύλης.

Ενότητες

Στοιχεία προτασιακής λογικής. Σύνολα, σχέσεις, ιδιότητες σχέσεων. Σχέσεις ισοδυναμίας. Μαθηματική επαγωγή.

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

Συνεκτικά γραφήματα. Συνεκτικές συνιστώσες μη-κατευθυνόμενου γραφήματος. Κομβικά σημεία, γέφυρες.

Mη-επεκτάσιμα μονοπάτια. Αναδρομή και επαγωγή για συνεκτικά γραφήματα. Αναδρομή και επαγωγή για άκυκλα συνεκτικά γραφήματα.

 

Μοναδικότητα μονοπατιών, ιδιότητα Helly. Δυναμικός προγραμματισμός για δέντρα. Επαναληπτική διάτρεξη δέντρου. Επαγωγή για δέντρα: κέντρα δέντρου, εύρεση μέγιστου μονοπατιού.

Άθροισμα κύκλων. Ο γραμμικός χώρος των κύκλων ενός γραφήματος, ενώσεις κύκλων χωρίς κοινές ακμές.

Στοιχειώδεις κύκλοι ως προς δεδομένο δέντρο επικάλυψης. Βάσεις του γραμμικού χώρου των κύκλων.

Ισχυρά συνεκτικά κατευθυνόμενα γραφήματα. Ισχυρά συνεκτικές συνιστώσες, ιδιότητές τους. Γράφημα των ισχυρά συνεκτικών συνιστωσών.

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

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

Ημερολόγιο