1. FIRST CYCLE - BACHELOR'S DEGREE
  2. FACULTY OF ENGINEERING
  3. COMPUTER ENGINEERING DEPARTMENT
  4. 253 Computer Engineering
Course Information Course Learning Outcomes Course's Contribution To Program ECTS Workload Course Details
Print

COURSE INFORMATION
Course CodeCourse TitleL+P HourSemesterECTS
CENG 481GRAPH THEORY AND ITS APPLICATIONS3 + 08th Semester5

COURSE DESCRIPTION
Course Level Bachelor's Degree
Course Type Elective
Course Objective Aim of this course, to give basic graph definitions, modeling of them with graphs when some of the problems encountered in real-world and to ensure a solution to graph theory techniques.
Course Content Graph theory and modeling, graph operations, ısomorphism problems on graphs, consept of connectivity, graph parameters, königsberg bridge problem, coloring on graphs, chromatic polynomials, planar graphs, spanning subtrees and algorithms, matching, algebraic structures of graphs, weighted graphs and shortest path algorithms, networks, graph algorithms (DFS, BFS, Bellman-Ford and Foyd algorithms), cut vertex.
Prerequisites No the prerequisite of lesson.
Corequisite No the corequisite of lesson.
Mode of Delivery Face to Face

COURSE LEARNING OUTCOMES
1Defines the basic concepts of Graph Theory.
2Produces alternative solutions to a problem.
3Defines the important graph parameters.
4Models the graphs using in the solution of current real-world problems.
5Uses the graphs algorithms.

COURSE'S CONTRIBUTION TO PROGRAM
PO 01PO 02PO 03PO 04PO 05PO 06PO 07PO 08PO 09PO 10PO 11PO 12
LO 001            
LO 002            
LO 003            
LO 004            
LO 005            
Sub Total            
Contribution000000000000

ECTS ALLOCATED BASED ON STUDENT WORKLOAD BY THE COURSE DESCRIPTION
ActivitiesQuantityDuration (Hour)Total Work Load (Hour)
Course Duration (14 weeks/theoric+practical)14342
Hours for off-the-classroom study (Pre-study, practice)14228
Mid-terms13030
Final examination13030
Total Work Load

ECTS Credit of the Course





130

5
COURSE DETAILS
 Select Year   


 Course TermNoInstructors
Details 2022-2023 Spring1TUFAN TURACI


Print

Course Details
Course Code Course Title L+P Hour Course Code Language Of Instruction Course Semester
CENG 481 GRAPH THEORY AND ITS APPLICATIONS 3 + 0 1 Turkish 2022-2023 Spring
Course Coordinator  E-Mail  Phone Number  Course Location Attendance
Prof. Dr. TUFAN TURACI tturaci@pau.edu.tr MUH A0226 %60
Goals Aim of this course, to give basic graph definitions, modeling of them with graphs when some of the problems encountered in real-world and to ensure a solution to graph theory techniques.
Content Graph theory and modeling, graph operations, ısomorphism problems on graphs, consept of connectivity, graph parameters, königsberg bridge problem, coloring on graphs, chromatic polynomials, planar graphs, spanning subtrees and algorithms, matching, algebraic structures of graphs, weighted graphs and shortest path algorithms, networks, graph algorithms (DFS, BFS, Bellman-Ford and Foyd algorithms), cut vertex.
Topics
WeeksTopics
1 The concept of graph and importance of graph theory.
2 Constructing graphs. Havel-Hakim Theorem, complement of a graph, regular graphs, star graph, (Complete) Bipartite graphs, induced subgraphs, isomorphic graphs.
3 Connectivity of graphs and some theorems. Graph operations (union, sum and product). Definition of trees and some theorems. Average degree of graphs, spanning subgraphs.
4 The process of coloring. Vertex color. Edge color. Some theorems of coloring. solution of a some problems with coloring.
5 Contraction, chromatic polynomials, chromatic polynomial and spanning subtree number finding algorithms with contraction.
6 Representing graphs on computer. Vertex-vertex and vertex-edge adjacency matrices. The properties of these matrices and theorems on it.
7 Vertex-cut, Vertex-cut matrices, basic vertex-cut and its matrix .
8 Matching. Maximal matching, perfect matching, (augmenting path), assignment problem, the modeling of assignment problem with graphs and Hungarian algorithm.
9 Connectivity number and Algorithms.
10 Distance in Graphs and Algorithms.
11 Graph Algorithms and Analysis
12 Graph Algorithms and Analysis
13 Modelling communication networks and Vulnerability
14 Modelling communication networks and Vulnerability
Materials
Materials are not specified.
Resources
ResourcesResources Language
Chartrand, G.-Lesniak, L., (1986) : Graphs and Digraphs, Wadsworth & Brooks, CaliforniaEnglish
West D.B. (2001) : Introduction to Graph Theory, Prentice Hall, USA. English
Graf Teoriye Giriş, Şerife Büyükköse ve Gülistan Kaya Gök, Nobel Yayıncılık Türkçe
Discrete Mathematical Structures for Computer Science, Ronald E. Prather, Houghton Mifflin Company, (1976). English
Christofides, N., 1986. Graph Theory an Algorithmic Approach, Academic Press, London English
Course Assessment
Assesment MethodsPercentage (%)Assesment Methods Title
Final Exam50Final Exam
Midterm Exam30Midterm Exam
Homework20Homework
L+P: Lecture and Practice
PQ: Program Learning Outcomes
LO: Course Learning Outcomes