Θεωρία Γράφων

Βασικοί παράμετροι γραφημάτων. Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων. Προσανατολισμένοι γράφοι, πλήρεις, διμερείς, επίπεδοι, υπογράφοι, ισομορφισμός γράφων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: Εφαρμογές στα δίκτυα τηλεπικοινωνιών. Κωδικοποίηση γράφων. Δένδρα επικάλυψης (minimum spanning tree). Αλγόριθμοι διάσχισης. Βέλτιστα μονοπάτια. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow-min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Πρόβλημα ταιριάσματος. Προβλήματα NP - πλήρη. Κομβική επικάλυψη. Προβλήματα χρωματισμού. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογράφου. 

Χειμ. Εξάμηνο 2015 - 2016. Μάθημα επιλογής 4ου έτους.

Πρόγραμμα: Τετάρτη 16.00-18.00, Αίθ. 4

                       Παρασκευή 10.00-12.00, Αίθ. 4

                        


Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα: 

Διακριτά Μαθηματικά, Δομές Δεδομένων, Αλγόριθμοι και Πολυπλοκότητα

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

- Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων

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

- Αλγόριθμοι σε γραφήματα


Μέθοδοι Διδασκαλίας:

Διαλέξεις θεωρίας (4 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).

Τρόπος Εξέτασης:

Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

Υλικό: Σημειώσεις



Δείτε εδώ την περιγραφή των θεμάτων που έχουμε συζητήσει.



Ενημέρωση: 20-Νοε-2017                                                                                                                            email: emarkou@ucg.gr