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

  • Γενικά

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

    Διδάσκων : Χ. Παπαδόπουλος

    Περιγραφή:

    Bασικές έννοιες γραφημάτων. Δένδρα. Διαδρομές και αποστάσεις. Συνδεσιμότητα. Διαμερίσεις. Αναπαράσταση γραφημάτων. Σκελετικά δένδρα, απαρίθμηση, καταμέτρηση και παραγοντοποίηση. Μονοπάτια και κύκλοι Euler και Hamilton. Αριθμοί ελαχίστης κάλυψης, κυριαρχίας, ανεξαρτησίας. Eπίπεδα γραφήματα. Θεώρημα Kuratowski (χωρίς απόδειξη). Χρωματισμοί κορυφών, πρόβλημα των τεσσάρων και πέντε χρωμάτων. Δυϊκά γραφήματα. Δίκτυα ροής. Δυσεπίλυτα προβλήματα γραφημάτων. Υλοποίηση και μελέτη αλγορίθμων στο εργαστήριο. Αλγόριθμοι: Dijkstra, Prim, συνεκτικότητας, δένδρου, επιπεδότητας, μεγίστης σύζευξης, κινέζου ταχυδρόμου, χρωματικών πολυωνύμων, ροής.

    Μαθησιακοί Στόχοι Μαθήματος:

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

    Ο στόχος του μαθήματος είναι

    • η εισαγωγή στην θεωρία γραφημάτων
    • η κατανόηση αλγοριθμικών τεχνικών  για προβλήματα που σχετίζονται με γραφήματα.

    Λέξεις κλειδιά: Γραφήματα, Συνεκτικότητα, Σκελετικά Δέντρα, Eulerian & Hamiltonian γραφήματα, Χρωματικός αριθμός, Κλίκα, Ανεξάρτητα σύνολα, Κάλυμμα κορυφών, Επίπεδα γραφήματα

  • 1. Εισαγωγικά μαθήματος

    Περιγραφή θεματικής ενότητας: Βασικές έννοιες γραφημάτων, ιστορικά στοιχεία και αναφορά στα διαδικαστικά του μαθήματος

    Λέξεις κλειδιά: διμελή σχέση, υπογράφημα, γράφημα, σύνολα κορυφών και ακμών. γειτονικές κορυφές 

  • 2. Εισαγωγή σε βασικές έννοιες

    Περιγραφή θεματικής ενότητας: Αναπαράσταση γραφημάτων, ειδικά γραφήματα και πράξεις μετασχηματισμοί γραφημάτων.  Ισομορφισμός - βαθμοί και γραφική ακολουθία

    Λέξεις κλειδιά: μονοπάτι, κύκλος, κλίκα, γινόμενο, δύναμη, σύνδεση, ένωση γραφημάτων, ακτίνα και διάμετρος γραφήματος

  • 3. Συνεκτικότητα και Δισυνεκτικότητα

    Περιγραφή θεματικής ενότητας: Συνεκτικές συνιστώσες και ιδιότητες. Γέφυρες, κόμβοι τομής και δισυνεκτικά γραφήματα. Ιδιότητες μεγιστοτικών μονοπατιών.

    Λέξεις κλειδιά: διαχωριστές, Θεώρημα του Menger, εσωτερικώς διακεκριμένα μονοπάτια

  • 4. Δέντρα

    Περιγραφή θεματικής ενότητας: Δάση και δέντρα. Χχαρακτηρισμός δέντρων σε σκελετικά δέντρα και ριζωμένα δέντρα. Πλήθος διαφορετικών δέντρων - Ακολουθία Prüfer

    Λέξεις κλειδιά: άκυκλα γραφήματα, πλήθος σκελετικών δένδρων, ακολουθία Pruffer

  • 5. Eulerian και Hamiltonian γραφήματα

    Περιγραφή θεματικής ενότητας: Τα Eulerian και Hamiltonian γραφήματα. Χαρακτηρισμός Eulerian γραφημάτων. Παραδείγματα εύρεσης μιας περιήγησης Euler. Το πρόβλημα του κινέζου ταχυδρόμου.

    Λέξεις κλειδιά: άρτιοι βαθμοί, Θεωρήματα του Ore και του Dirac, αλγόριθμος εύρεσης συντομότερου περιπάτου

  • 6. Προβλήματα βελτιστοποίησης σε γραφήματα: χρωματισμοί, κλίκες και ανεξάρτητα σύνολα

    Περιγραφή θεματικής ενότητας: Χρωματισμοί γραφημάτων και παραδείγματα αυτών. Κλίκες, ανεξάρτητα σύνολα και ο αριθμός ανεξαρτησίας. Άνω και κάτω φράγμα και γραφήματα Turán.

    Λέξεις κλειδιά: αριθμοί Ramsey, μέγιστη κλίκα, μέγιστο ανεξάρτητο σύνολο, έγκυρος χρωματισμός, πλήρη κ-μερή γραφήματα

  • 7. Προβλήματα βελτιστοποίησης σε γραφήματα: καλύμματα κορυφών και ταιριάσματα

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

    Λέξεις κλειδιά: εναλλασόμενο μονοπάτι, Θεώρημα του Berge, μέγιστα και τέλεια ταιριάσματα

  • 8. Επίπεδα γραφήματα

    Περιγραφή θεματικής ενότητας: Ενεπίπεδα, εξωεπίπεδα και επίπεδα γραφήματα. Ιδιότητες χαρακτηρισμοί και χρωματισμοί επίπεδων γραφημάτων. Ομοιομορφισμοί και μέγιστα επίπεδα γραφήματα. Χάρτες, όψεις και χρωματισμός γραφημάτων ως προς τις όψεις.

    Λέξεις κλειδιά: το Θεώρημα τεσσάρων χρωμάτων, εμβάπτυνση γραφήματος, ομοιομορφισμός γραφήματος, όψεις, εξωεπίπεδα γραφήματα, τριγωνοποίηση γραφημάτων

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

    Προτείνονται τα ακόλουθα δύο βιβλία που βρίσκονται στο σύστημα «Εύδοξος».

    • Εισαγωγή στους γράφους 
      Κωδικός Βιβλίου στον Εύδοξο: 31356 
      Συγγραφείς: Κυρούσης Λ., Μπούρας Χ. , Σπυράκης Π. , Σταματίου Γ.
    • Μαθήματα Θεωρίας Γράφων 
      Κωδικός Βιβλίου στον Εύδοξο: 3472 
      Συγγραφείς: Γ. Μανωλόπουλος

    Επίσης θα διατεθούν σημειώσεις από τον διδάσκοντα:

    • Σημειώσεις στη Θεωρία Γραφημάτων,
      Χάρης Παπαδόπουλος,
      Πανεπιστήμιο Ιωαννίνων. 

    Επιπρόσθετα υπάρχουν τα ακόλουθα βιβλία στα αγγλικά:

    • Επιπρόσθετο υλικό

      • Εργασίες - Ασκήσεις