Information Package / Course Catalogue
Graph Theory I
Course Code: MTK545
Course Type: Area Elective
Couse Group: Second Cycle (Master's Degree)
Education Language: Turkish
Work Placement: N/A
Theory: 3
Prt.: 0
Credit: 3
Lab: 0
ECTS: 8
Objectives of the Course

The purpose of this course is to introduce students to the topics in the course content.

Course Content

Graphs, subgraphs, isomorphic graphs, connected graphs, weighted graphs, distance in graphs, shortest path problems, Eulerian and Hamiltonian graphs, Chinese postman problem, travelling salesman problem, planar graphs, Kuratowski’s theorem, coloring, chromatic number, four color theorem, directed graphs, tournaments, Eulerian and Hamiltonian directed graphs, orientable graphs, independent sets.

Name of Lecturer(s)
Prof. Adnan MELEKOĞLU
Learning Outcomes
1.Ability to understand the fundamental concepts of graph theory.
2.Ability to solve the problems by applying graph theoretical methods.
3.Ability to determine whether a graph is planar.
4.Ability to determine the chromatic number a graph.
5.Ability to understand the notion directed graph.
Recommended or Required Reading
1.R. Diestel, Graph Theory, Springer, 2017.
2.J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.
Weekly Detailed Course Contents
Week 1 - Theoretical
Graphs and Subgraphs
Week 2 - Theoretical
Trees and Connectivity
Week 3 - Theoretical
Weighted Graphs
Week 4 - Theoretical
Distance in Graphs
Week 5 - Theoretical
Shortest Path Problems
Week 6 - Theoretical
Eulerian and Hamiltonian Graphs
Week 7 - Theoretical
Chinese Postman Problem, Travelling Salesman Problem
Week 8 - Theoretical
Planar Graphs, Kuratowski’s Theorem, Midterm exam
Week 9 - Theoretical
Coloring, Chromatic Number, Four Color Theorem
Week 10 - Theoretical
Directed Graphs
Week 11 - Theoretical
Tournaments
Week 12 - Theoretical
Eulerian and Hamiltonian Directed Graphs
Week 13 - Theoretical
Orientable Graphs
Week 14 - Theoretical
Independent Sets
Assessment Methods and Criteria
Type of AssessmentCountPercent
Midterm Examination1%30
Final Examination1%70
Workload Calculation
ActivitiesCountPreparationTimeTotal Work Load (hours)
Lecture - Theory140342
Individual Work1408112
Midterm Examination118220
Final Examination124226
TOTAL WORKLOAD (hours)200
Contribution of Learning Outcomes to Programme Outcomes
PÇ-1
PÇ-2
PÇ-3
PÇ-4
PÇ-5
PÇ-6
PÇ-7
PÇ-8
PÇ-9
PÇ-10
PÇ-11
PÇ-12
PÇ-13
PÇ-14
PÇ-15
OÇ-1
2
2
3
3
2
OÇ-2
2
4
3
4
2
OÇ-3
2
2
2
2
2
OÇ-4
2
2
2
2
2
OÇ-5
2
3
2
3
3
Adnan Menderes University - Information Package / Course Catalogue
2026