PAÜ .:. Eğitim Öğretim Bilgi Sistemi

COURSE INFORMATION

Course Code	Course Title	L+P Hour	Semester	ECTS
CENG 533	GRAPH THEORY AND ALGORITHMS	3 + 0	2nd Semester	7,5

COURSE DESCRIPTION

Course Level	Master's Degree
Course Type	Elective
Course Objective	To teach the basic definitions and concepts in graph theory. To model some problems encountered in daily life with graphs and to provide the solution of the modeled problem with graph theory algorithms and techniques.
Course Content	Basic graph definitions, Graph Operations. Isomorphism Problem in Graphs, Graph Parameters. Königsberg Bridge Problem. Coloring Problem in Graphs. Chromatic Polynomials. Planer Graphs. Spanning Trees and Tree Algorithms, Matching. Algebraic Structures of Graphs. Graph connectivity, Cut vertices. Weighted Graphs, Shortest Path Problems, Networks. Graph Algorithms and Analysis (DFS, BFS, Bellman-Ford and Floyd Algorithms).
Prerequisites	No the prerequisite of lesson.
Corequisite	No the corequisite of lesson.
Mode of Delivery	Face to Face

COURSE LEARNING OUTCOMES

1	Expresses the basic definitions and theorems in graphs.
2	Models problems with graphs.
3	Calculates the connectivity value in networks.
4	Solves a given problem with an appropriate graph algorithm.
5	Analyzes Graph Algorithms.

COURSE'S CONTRIBUTION TO PROGRAM

	PO 01	PO 02	PO 03	PO 04	PO 05	PO 06	PO 07	PO 08	PO 09	PO 10	PO 11	PO 12
LO 001	3	2	2	5		3					2
LO 002	3	2	2	5		3					2
LO 003	3	2	2	5		3					2
LO 004	3	2	2	5		3					2
LO 005	3	2	2	5		3					2
Sub Total	15	10	10	25		15					10
Contribution	3	2	2	5	0	3	0	0	0	0	2	0

ECTS ALLOCATED BASED ON STUDENT WORKLOAD BY THE COURSE DESCRIPTION

Activities	Quantity	Duration (Hour)	Total Work Load (Hour)
Course Duration (14 weeks/theoric+practical)	14	3	42
Hours for off-the-classroom study (Pre-study, practice)	14	5	70
Assignments	5	8	40
Mid-terms	1	15	15
Final examination	1	28	28
Total Work Load ECTS Credit of the Course			195 7,5

COURSE DETAILS

Select Year

	Course Term	No	Instructors
Details	2023-2024 Fall	1	TUFAN TURACI

Course Details

Course Code	Course Title	L+P Hour	Course Code	Language Of Instruction	Course Semester
CENG 533	GRAPH THEORY AND ALGORITHMS	3 + 0	1	Turkish	2023-2024 Fall

Course Coordinator	E-Mail	Phone Number	Course Location	Attendance
Prof. Dr. TUFAN TURACI	tturaci@pau.edu.tr		MUH A0257	%70

Goals		To teach the basic definitions and concepts in graph theory. To model some problems encountered in daily life with graphs and to provide the solution of the modeled problem with graph theory algorithms and techniques.
Content		Basic graph definitions, Graph Operations. Isomorphism Problem in Graphs, Graph Parameters. Königsberg Bridge Problem. Coloring Problem in Graphs. Chromatic Polynomials. Planer Graphs. Spanning Trees and Tree Algorithms, Matching. Algebraic Structures of Graphs. Graph connectivity, Cut vertices. Weighted Graphs, Shortest Path Problems, Networks. Graph Algorithms and Analysis (DFS, BFS, Bellman-Ford and Floyd Algorithms).

Topics

Weeks	Topics
1	Graph concept and Importance of Graph Theory.
2	Constructing graphs. Havel-Hakim Theorem. Basic graph definitions.
3	Graph Operations. Tree definition and some Theorems. Induced subgraph.
4	Independence number, Covering number and Domination number in Graphs and Algorithms.
5	Coloring of graphs and Chromatic Polynomials.
6	Representing graphs on computer and Matrices.
7	Matching. Maximal matching, perfect matching, (augmenting path), assignment problem, the modeling of assignment problem with graphs and Hungarian algorithm.
8	Connectivity number in Networks and Algorithms.
9	Menger's Theorem and the Maximum flow problem.
10	Graph Algorithms and Analysis: Search algorithms, Depth first search, Breath first search
11	Graph Algorithms and Analysis: Djikstra's algorithm
12	Graph Algorithms and Analysis: Bellman-Ford and Floyd Algorithm
13	Graph Algorithms and Analysis: Prim Algorithm, Kruskal Algorithm
14	Applications of Graf Theory to Daily Life Problems

Materials

Materials are not specified.

Resources

Resources	Resources Language
Chartrand, G.,Lesniak L. GraphsandDigraphs.WadsworthInc., ISBN : 0534063241.	English
Bondy, J. A., 1976. “GraphTheorywith Applications”. ElsevierScienceLtd, ISBN: 0444194517.	English
Buckley,F. AndHarary,F.,Distance in Graphs,AddisonWesleyPub.California.	English
Ronald E. Prather, Discrete Mathematical StructersforComputerScience, HoughtonMiffinCompany,	English

Course Assessment

Assesment Methods	Percentage (%)	Assesment Methods Title
Final Exam	50	Final Exam
Midterm Exam	50	Midterm Exam

L+P: Lecture and Practice
PQ: Program Learning Outcomes
LO: Course Learning Outcomes

Prospective Student