CENG715 Graph Theory

6 ECTS - 3-0 Duration (T+A)- . Semester- 3 National Credit

Information

Code CENG715
Name Graph Theory
Term 2023-2024 Academic Year
Semester . Semester
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 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

Update Time: 16.05.2023 01:44