Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

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

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

Κωδικός μαθήματος: ΜΥΕ014

Εβδομαδιαίες ώρες διδασκαλίας: 3,1,1

Εξάμηνο σπουδών: >=6

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο: NAI

Προαπαιτούμενα:

Περιεχόμενο:

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

  • Εισαγωγή και βασικοί ορισμοί
  • Γραφικές απεικονίσεις και ισομορφισμός γραφημάτων
  • Δέντρα – ειδικές ιδιότητες και εφαρμογές
  • Συνδεσιμότητα, Euler διαδρομές και Hamiltonian κύκλοι
  • Επικαλύψεις και ταιριάσματα
  • Κλίκες και ανεξάρτητα σύνολα
  • Χρωματισμός κόμβων και χρωματισμός ακμών
  • Κατευθυνόμενα γραφήματα και εφαρμογές
  • Επίπεδα γραφήματα και δίκτυα
  • Γενικές εφαρμογές.

 

Παρατηρήσεις: