Graph Theory and Network Flows

Course Code:

ISE 428

Course Type:

Area Elective

Credits:

3

Theoric:

3

Practice:

0

Laboratory Hour:

0

ECTS:

5

Prerequisite Courses:

Operations Research I

Course Language:

English

Course Objectives:

This course aims to define basic concepts of graph theory and network flows and to provide an introduction to the algorithms and fundamental methods used to solve important problems in graph theory and network flows.

Course Content:

Topics covered include the structure and solution approaches of the problems in graph theory and network flows. Particularly, shortest path problem, minimum spanning tree problem, maximum flow problem, minimum cost network flow problem, transportation problem, colouring problem, Chinese postman problem, Hamiltonian cycle problem and matching problems will be discussed.

Course Methodology:

1: Lecture, 2: Question-Answer

Course Evaluation Methods:

A: Testing, B: Experiment, C: Homework

Vertical Tabs

Ders Tanimlari

Course Learning Outcomes

Course Learning Outcomes	Program Learning Outcomes	Teaching Methods	Assessment Methods
1. Builds models for graph theory and network flows problems arising in different settings	1,2	1,2	A,C
2. Applies various solution approaches according to the hardness graph theory and network flows problems	1,2	1,2	A,C
3. Interpret results obtained from the solution of graph theory and network flows problems	1,2	1,2	A,C
4. Applies solution procedures for the extensions and variants of the for graph theory and network flows problems	1,2	1,2	A,C
5. Identifies and models graph theory and network flow problems that arise in different contexts	2	1,2	A,C
6. Interpret the computational hardness of the variation of the graph theory and network flows problems	1,2	1,2	A,B

Course Flow

COURSE CONTENT
Week	Topics	Study Materials
1	INTRODUCTION TO GRAPH THEORY AND NETWORK FLOWS	Textbook, Course Notes
2	BASIC CONCEPTS OF GRAPH THEORY AND NETWORK FLOWS	Textbook, Course Notes
3	SHORTEST PATH PROBLEM (LABEL SETTING& LABEL CORRECTING ALGORITHMS)	Textbook, Course Notes
4	MINIMUM SPANNING TREE PROBLEM (KRUSKAL & PRIM ALGORITHMS)	Textbook, Course Notes
5	MAXIMUM FLOW PROBLEM (FLOWS AND CUTS)	Textbook, Course Notes
6	MINIMUM COST NETWORK FLOW PROBLEM (NETWORK SIMPLEX)	Textbook, Course Notes
7	TRANSPORTATION PROBLEM	Textbook, Course Notes
8	MIDTERM EXAM 1	Textbook, Course Notes
9	GRAPH COLOURING PROBLEMS	Textbook, Course Notes
10	MATCHING PROBLEMS (CARDINALITY & WEIGTHED)	Textbook, Course Notes
11	HAMILTONIAN CYCLE PROBLEM	Textbook, Course Notes
12	CHINESE POSTMAN PROBLEM	Textbook, Course Notes
13	EXTENSIONS OF THE GRAPH THEORY AND NETWORK FLOW PROBLEMS	Textbook, Course Notes
14	MIDTERM EXAM 2	Textbook, Course Notes

Recommended Sources

RECOMMENDED SOURCES

Textbook

Operations Research: Applications and Algorithms,

W. L. WINSTON, THOMPSON – BROOKS/COLE, 2004

Operations Research, Hamdy A. Taha, Prentice Hall; 9th edition, 2010

Network Flows: Theory, Algorithms, and Applications, R.K. Ahuja, T.L. Magnanti, J.L. Orlin, Prentice Hall; 1993

Additional Resources

Material Sharing

MATERIAL SHARING
Documents	Lecture notes, old exam keys
Assignments	Homeworks 1-7
Exams	Midterm 1-2, Quizzes 1-6, Final Exam

Assessment

ASSESSMENT
IN-TERM STUDIES	NUMBER	PERCENTAGE
Midterm 1	1	36
Midterm 2	1	28
Quizzes	6	36
Total		100
CONTRIBUTION OF FINAL EXAMINATION TO OVERALL GRADE		30
CONTRIBUTION OF IN-TERM STUDIES TO OVERALL GRADE		70
Total		100

Course’s Contribution to Program

COURSE'S CONTRIBUTION TO PROGRAM
No	Program Learning Outcomes	Contribution
No	Program Learning Outcomes	1	2	3	4	5
1	Adequate background in Mathematics, Natural Sciences and the Industrial and Systems Engineering discipline.					X
2	Ability to identify, model and solve complex problems in the area of Industrial and Systems Engineering.					X
3	Ability to design a complex system, process, device or product under realistic constraints and conditions, in such a way as to meet the desired requirements.			X
4	Ability to employ information technologies effectively in Industrial and Systems Engineering applications and develop and/or use modern techniques and tools for these applications.					X
5	Ability to design and conduct experiments and interpret results to analyze problems in the area of Industrial and Systems Engineering.				X
6	Ability to take responsibility both individually and as a team member to solve unforeseen problems that arise in intra-disciplinary and inter-disciplinary projects.
7	Ability to access information in the area of Industrial and Systems Engineering and to report and communicate this information to others using a foreign language (English) at the European Language Portfolio C1 General Level.
8	Ability to follow current issues and recent developments in science and technology by accessing databases and other sources of information and to continue to educate oneself.
9	Awareness of scientific and ethical responsibility in professional matters.
10	Ability to initiate innovative projects in the area of Industrial and Systems Engineering and to manage these projects considering all aspects.
11	Ability to identify the impact of Industrial and Systems Engineering applications on health, environment and safety; awareness of the legal consequences of Industrial and Systems Engineering solutions.

ECTS

ECTS ALLOCATED BASED ON STUDENT WORKLOAD BY THE COURSE DESCRIPTION
Activities	Quantity	Duration (Hour)	Total Workload (Hour)
Course Duration (Excluding the exam weeks: 12x Total course hours)	12	3	36
Hours for off-the-classroom study (Pre-study, practice)	14	5	70
Midterm examination	2	2	4
Homework	7	4	28
Project	1	50	50
Final examination	1	2	2
Total Work Load			190
Total Work Load / 25 (h)			7.6
ECTS Credit of the Course			8

Search form

Graph Theory and Network Flows

Vertical Tabs

Ders Tanimlari