Akademik Dersler - Tanıtım


Code - Course Title	MAT647 - Algorithmic Graph Theory
Course Type	Elective Courses
Language of Instruction	Türkçe
Laboratory + Practice	3+0
ECTS	7.5
Course Instructor(s)	PROFESÖR DOKTOR EMRAH AKYAR
Mode of Delivery	This course is conducted as face-to-face and/or distance education.
Prerequisites	None
Courses Recomended	Introduction to Graph Theory
Required or Recommended Resources	Gary Chartrand, Ortrud R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1992.
Recommended Reading List	Gary Chartrand, Ortrud R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1992.
Assessment methods and criteria	One midterm and one final exam.
Work Placement
Sustainability Development Goals

Weeks	Topics
Week - 1	Introduction to graphs, fundamental concepts, types of graphs, and modeling problems using graphs.
Week - 2	Introduction to algorithmic complexity, growth notations, and analysis of algorithm efficiency.
Week - 3	Data structures, graph representations, and depth-first search (DFS) algorithm.
Week - 4	Breadth-first search (BFS), shortest path concept, and comparison with DFS.
Week - 5	Spanning tree concept, properties of spanning trees, and their construction.
Week - 6	Minimum spanning tree problems and Kruskal’s and Prim’s algorithms.
Week - 7	Enumeration of spanning trees and Kirchhoff’s matrix-tree theorem.
Week - 8	Planar graphs, Euler’s formula, and planarity criteria.
Week - 9	Matchings in graphs, maximum matching, and Hall’s theorem.
Week - 10	Eulerian paths and circuits, Euler criteria, and postman problems.
Week - 11	Hamiltonian paths and cycles, existence theorems, and the traveling salesman problem.
Week - 12	Graph coloring, chromatic number, dominating sets, independent sets, and cliques.
Week - 13	Graph problems and complexity classes, concepts of P and NP, and reducibility.
Week - 14	NP-complete graph problems, including independent set, clique, Hamiltonian cycle, traveling salesman, and graph coloring problems.

Assessment Method and Passing Requirements
	Quamtity	Percentage (%)
1.Midterm Exam	1	40
Final Exam	1	60
Toplam (%)		100