Information Package
baskent.edu.tr

Program of Computer Engineering (English)

CSE475

GRAPH THEORY

Course Code
CSE475
Semester
-
Theory+Practice
3 + 0
ECTS
5
Course TypeElective Course
Course LevelBachelor's Degree
Year of Study-
Semester-
ECTS5
Name of Lecturer(s)
Learning Outcomes

At the end of this course, the students;

  1. Learn the basic concepts and techniques of graph theory.
  2. Select appropriate models and algorithms of graph theory to solve the problems arising in computer science, engineering and operations research.
  3. Learn Euler circuits and related application problems, solve them using algorithms.
  4. Have theoretical knowledge on Hamilton circuits. Gain an understanding of the challenges arising in solving the traveling salesman problem.
  5. Learn algorithms used for solution of the shortest path problem and compare their computational complexity.
  6. Solve the problem of maximum flow. Implement the algorithms for matching and assignment problems.
  7. Solve problems by applying the tree algorithms.
Mode of DeliveryFace to face
PrerequisitesNo
Recommended Optional Programme ComponentsNone
Course DescriptionGraphs and graph models, connected graphs. Multigraphs and digraphs. Isomorphic graphs. Trees, the minimum spanning tree problem. Connectivity. Eulerian graphs. Hamiltonian graphs. Matchings and factorization. Planarity and planar graphs. Coloring graphs, the four color problem. Vertex coloring, edge coloring. Matrices and graph algorithms. Flows and cuts, constructing maximal flows.
Course Contents
WEEK TOPICS
1st Week Graphs and graph models, connected graphs.
2nd Week Multigraphs and digraphs.
3rd Week Isomorphic graphs.
4th Week Trees, the minimum spanning tree problem.
5th Week Connectivity. Eulerian graphs.
6th Week Hamiltonian graphs.
7th Week Matchings and factorization.
8th Week Mid-term
9th Week Planarity and planar graphs.
10th Week Coloring graphs, the four color problem.
11th Week Vertex coloring, edge coloring.
12th Week Matrices and graph algorithms.
13th Week Flows and cuts, constructing maximal flows.
14th Week Flows and cuts, constructing maximal flows.
15th Week General Review
Recommended or Required Reading1. Buckley F., Lewinter M., Friendly introduction to Graph Theory, Prentice Hall, 2003
2. Grimaldi R.P., Discrete and Combinatorial Mathematics, 5/E, Addison Wesley, 2003
3. Rosen K.H., Discrete Mathematics and Its Applications, 6/E, McGraw-Hill, 2007
Planned Learning Activities and Teaching Methods
  • Questions/Answers
  • Other
  • Presentation
  • Report Preparation
  • Project
  • Problem Solving
  • Practice
  • Experiment
Assessment Methods and Criteria
Quantity Percentage (%)
Mid-term 3 30
Assignment 7 15
Project 1 15
Total(%) 60
Contribution of In-term Studies to Overall Grade(%) 60
Contribution of Final Examination to Overall Grade(%) 40
Total(%) 100
Language of InstructionEnglish
Work Placement(s)No

Programme Qualifications / Learning Outcomes

LO1 LO2 LO3 LO4 LO5 LO6 LO7
K1 X X X X X X X
K2 X X X X X X
K3
K4
K5
K6
K7
K8
K9
K10
K11