Graph Theory (7ΕΠ02)
Instructor :
Course typeElective
Semester7
TermFall Semester
ECTS5
Teaching hours3
Laboratory hours
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
  • Θεωρία και Αλγόριθμοι Γράφων, Ι. Μανωλόπουλος, Α. Παπαδόπουλος, Κ. Τσίχλας, Εκδόσεις Νέων Τεχνολογιών Μον. ΕΠΕ, 2013.
  • Εισαγωγή στους γράφους, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης, Γ. Σταματίου, Εκδόσεις Γ. Δαρδάνος - Κ. Δαρδάνος Ο. Ε., 1999.
  • Εισαγωγή στους Αλγόριθμους τόμος 1, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009.
  • Θεωρία Γραφημάτων, Α. Παπαϊωάννου, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2010.
Assessment method
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Course material
Notes