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

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

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

Πρόγραμμα: Τρίτη       18.00-20.00 (Αίθ. 4)

                        Τετάρτη  12.00-14.00 (Αίθ. 4)


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

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

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

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

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

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


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

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

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

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

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



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