TÜRKÇE
ENGLISH
Information
| Code | CENG715 |
| Name | Graph Theory |
| Term | 2022-2023 Academic Year |
| Term | Spring |
| Duration (T+A) | 3-0 (T-A) (17 Week) |
| ECTS | 6 ECTS |
| National Credit | 3 National Credit |
| Teaching Language | İngilizce |
| Level | Doktora Dersi |
| Type | Normal |
| Mode of study | Yüz Yüze Öğretim |
| Catalog Information Coordinator | Prof. Dr. UMUT ORHAN |
| Course Instructor |
1 |
Course Goal / Objective
The aim is to understand the theoretical background of graphs and to apply graph algorithms into the most known problems.
Course Content
Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path, Spanning trees, Bipartite graphs, Eulerian graphs, Hamilton graphs, Independent-covering-mathcing graphs, Vertex colorings, Edge colorings, Planar graphs, Directed graph
Course Precondition
none
Resources
D. B. West, Introduction to Graph Theory,Prentice-Hall of India/Pearson, 2009.
Notes
J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, 2008.
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Knows the graphs, applies it to problems |
| LO02 | Knows the connected graphs |
| LO03 | Knows the spanning trees |
| LO04 | Knows the bipartite graphs |
| LO05 | Knows Hamilton and Euler paths |
| LO06 | Knows vertex and edge coloring |
| LO07 | Knows the planar graphs |
Relation with Program Learning Outcome
| Order | Type | Program Learning Outcomes | Level |
|---|---|---|---|
| PLO01 | Bilgi - Kuramsal, Olgusal | On the basis of the competencies gained at the undergraduate level, it has an advanced level of knowledge and understanding that provides the basis for original studies in the field of Computer Engineering. | 4 |
| PLO02 | Bilgi - Kuramsal, Olgusal | By reaching scientific knowledge in the field of engineering, he/she reaches the knowledge in depth and depth, evaluates, interprets and applies the information. | 4 |
| PLO03 | Yetkinlikler - Öğrenme Yetkinliği | Being aware of the new and developing practices of his / her profession and examining and learning when necessary. | 3 |
| PLO04 | Yetkinlikler - Öğrenme Yetkinliği | Constructs engineering problems, develops methods to solve them and applies innovative methods in solutions. | 3 |
| PLO05 | Yetkinlikler - Öğrenme Yetkinliği | Designs and applies analytical, modeling and experimental based researches, analyzes and interprets complex situations encountered in this process. | 4 |
| PLO06 | Yetkinlikler - Öğrenme Yetkinliği | Develops new and / or original ideas and methods, develops innovative solutions in system, part or process design. | |
| PLO07 | Beceriler - Bilişsel, Uygulamalı | Has the skills of learning. | 3 |
| PLO08 | Beceriler - Bilişsel, Uygulamalı | Being aware of new and emerging applications of Computer Engineering examines and learns them if necessary. | 2 |
| PLO09 | Beceriler - Bilişsel, Uygulamalı | Transmits the processes and results of their studies in written or oral form in the national and international environments outside or outside the field of Computer Engineering. | 2 |
| PLO10 | Beceriler - Bilişsel, Uygulamalı | Has comprehensive knowledge about current techniques and methods and their limitations in Computer Engineering. | 3 |
| PLO11 | Beceriler - Bilişsel, Uygulamalı | Uses information and communication technologies at an advanced level interactively with computer software required by Computer Engineering. | 2 |
| PLO12 | Bilgi - Kuramsal, Olgusal | Observes social, scientific and ethical values in all professional activities. |
Week Plan
| Week | Topic | Preparation | Methods |
|---|---|---|---|
| 1 | Introduction to Graphs, isomorphism, subgraphs, matrix representations, degree | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 2 | Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 3 | Spanning trees | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 4 | Bipartite graphs, line graphs, chordal graphs | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 5 | Eulerian graphs, Fleury algorithm, chinese-postman problem | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 6 | Hamilton graphs | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 7 | Review for midterm exam | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 8 | Mid-Term Exam | Study to lecture notes and apllications | Ölçme Yöntemleri: Proje / Tasarım |
| 9 | Independent-covering-mathcing graphs, perfect matchings | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 10 | Vertex colorings, chromatic number and cliques, greedy coloring, Brook theorem | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 11 | Edge colorings, Gupta-Vizing theorem, class-1 and class-2 graphs | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 12 | Planar graphs, 4 and 5 coloring | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 13 | Directed graph, underlying graph, outdegree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 14 | Students Presentations | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 15 | Review for final exam | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 16 | Term Exams | Study to lecture notes and apllications | Ölçme Yöntemleri: Yazılı Sınav |
| 17 | Term Exams | Study to lecture notes and apllications | Ölçme Yöntemleri: Yazılı Sınav |
Student Workload - ECTS
| Works | Number | Time (Hour) | Workload (Hour) |
|---|---|---|---|
| Course Related Works | |||
| Class Time (Exam weeks are excluded) | 14 | 3 | 42 |
| Out of Class Study (Preliminary Work, Practice) | 14 | 5 | 70 |
| Assesment Related Works | |||
| Homeworks, Projects, Others | 0 | 0 | 0 |
| Mid-term Exams (Written, Oral, etc.) | 1 | 15 | 15 |
| Final Exam | 1 | 30 | 30 |
| Total Workload (Hour) | 157 | ||
| Total Workload / 25 (h) | 6,28 | ||
| ECTS | 6 ECTS | ||