TÜRKÇE
ENGLISH
Information
| Unit | INSTITUTE OF NATURAL AND APPLIED SCIENCES |
| COMPUTER ENGINEERING (PhD) (ENGLISH) | |
| Code | CENG715 |
| Name | Graph Theory |
| Term | 2018-2019 Academic Year |
| Term | Fall |
| 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 |
The current term course schedule has not been prepared yet.
|
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
Resources
Notes
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Knows graphs, applies it to problems |
| LO02 | Knows connected graphs |
| LO03 | Knows spanning trees |
| LO04 | Knows bipartite graphs |
| LO05 | Knows Hamilton and Euler paths |
| LO06 | Knows vertex and edge coloring |
| LO07 | Knows 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. | |
| 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. | |
| PLO08 | Beceriler - Bilişsel, Uygulamalı | Being aware of new and emerging applications of Computer Engineering examines and learns them if necessary. | |
| 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. | |
| 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. | |
| 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 | |
| 2 | Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path | Reading related chapter in lecture notes | |
| 3 | Spanning trees | Reading related chapter in lecture notes | |
| 4 | Bipartite graphs, line graphs, chordal graphs | Reading related chapter in lecture notes | |
| 5 | Eulerian graphs, Fleury algorithm, chinese-postman problem | Reading related chapter in lecture notes | |
| 6 | Hamilton graphs | Reading related chapter in lecture notes | |
| 7 | Review for midterm exam | Reading related chapter in lecture notes | |
| 8 | Mid-Term Exam | Study to lecture notes and apllications | |
| 9 | Independent-covering-mathcing graphs, perfect matchings | Reading related chapter in lecture notes | |
| 10 | Vertex colorings, chromatic number and cliques, greedy coloring, Brook theorem | Reading related chapter in lecture notes | |
| 11 | Edge colorings, Gupta-Vizing theorem, class-1 and class-2 graphs | Reading related chapter in lecture notes | |
| 12 | Planar graphs, 4 and 5 coloring | Reading related chapter in lecture notes | |
| 13 | Directed graph, underlying graph, outdegree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments | Reading related chapter in lecture notes | |
| 14 | Students Presentations | Reading related chapter in lecture notes | |
| 15 | Review for final exam | Reading related chapter in lecture notes | |
| 16 | Term Exams | Study to lecture notes and apllications | |
| 17 | Term Exams | Study to lecture notes and apllications |
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 | ||