| Course Type | Elective Course |
|---|
| Course Level | Bachelor's Degree |
|---|
| Year of Study | - |
|---|
| Semester | - |
|---|
| ECTS | 5 |
|---|
| Name of Lecturer(s) |
|
| Learning Outcomes |
At the end of this course, the students;
- Learn the basic concepts and techniques of graph theory.
- Select appropriate models and algorithms of graph theory to solve the problems arising in computer science, engineering and operations research.
- Learn Euler circuits and related application problems, solve them using algorithms.
- Have theoretical knowledge on Hamilton circuits. Gain an understanding of the challenges arising in solving the traveling salesman problem.
- Learn algorithms used for solution of the shortest path problem and compare their computational complexity.
- Solve the problem of maximum flow. Implement the algorithms for matching and assignment problems.
- Solve problems by applying the tree algorithms.
|
| Mode of Delivery | Face to face |
|---|
| Prerequisites | No |
|---|
| Recommended Optional Programme Components | None |
|---|
| Course Description | Graphs 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 Repeat. |
|
| Recommended or Required Reading | 1. 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 |
|
| ECTS Allocated Based on Student Workload |
| Activities |
Quantity |
Duration (Hour) |
Total Workload (Hour) |
| Midterm exam |
1 |
1.5 |
1.5 |
| Preparation for Quiz |
|
|
|
| Individual or group work |
|
|
|
| Preparation for Final exam |
1 |
20 |
20 |
| Course hours |
14 |
3 |
42 |
| Preparation for Midterm exam |
1 |
15 |
15 |
| Laboratory (including preparation) |
|
|
|
| Final exam |
1 |
1.5 |
1.5 |
| Homework |
|
|
|
| Project |
1 |
70 |
70 |
| Quiz |
4 |
0.5 |
2 |
| Total Work Load | 152 |
| Total Work Load / 30 (h) | 5.06 |
| ECTS Credit of the Course | 5 |
|
| Language of Instruction | Turkish |
|---|
| Work Placement(s) | No |
|---|
