Graph Theory

Course ID
7ΕΠ02
Επίπεδο
Undergraduate
Είδος
Optional (compulsory)
Εξάμηνο
7
Περίοδος
Fall Semester
ECTS
5
Ώρες Θεωρίας
3
Ώρες Εργαστηρίου
-

Instructor

Description

Basic Graph Parameters. Directed Graphs, Cliques, Bipartite and Planar Graphs. Euler and Hamilton Cycles. Minimum Spanning Trees, Depth First Search, Breadth First Search, Shortest Paths. Maximum Flows. The Matching problem. NP-complete problems: Vertex Cover, Vertex Coloring, Maximum Clique.

Course objectives

  • Modeling algorithmic problems in graphs
  • Analyzing and proving graph properties
  • Graph Algorithms

Textbooks/Bibliography

  • Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας, ΕΚΔΟΣΕΙΣ ΝΕΩΝ ΤΕΧΝΟΛΟΓΙΩΝ ΜΟΝ. ΕΠΕ, 1η/2013, ΑΘΗΝΑ, 33134148
  • Εισαγωγή στους Γράφους, Κυρούσης Λευτέρης Μ., Μπούρας Χρήστος Ι., Σπυράκης Παύλος Γ., Σταματίου Γ, Γ. ΔΑΡΔΑΝΟΣ – Κ. ΔΑΡΔΑΝΟΣ Ο.Ε., 1η έκδ./1999, ΑΘΗΝΑ, 31356

Assessment method

One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.

Course material

Notes