Syllabus ( MATH 438 )

Basic information


Course title: 
Graph Theory and Combinatorics 
Course code: 
MATH 438 
Lecturer: 
Prof. Dr. Sibel ÖZKAN

ECTS credits: 
6 
GTU credits: 
3 (3+0+0) 
Year, Semester: 
4, Spring 
Level of course: 
First Cycle (Undergraduate) 
Type of course: 
Departmental Elective

Language of instruction: 
English

Mode of delivery: 
Face to face

Pre and corequisites: 
Math 115 
Professional practice: 
No 
Purpose of the course: 
The aim of the course is to introduce students to the fundamentals of graph theory and combinatorial structures. It has been a must to introduce the interested students to these concepts since they have an increasing application in chemistry, biology, engineering and computer science nowadays. In these course, trees, cycles and basic graph types will be introduced as well as the combinatorial, algebraic and geometric relations within and advanced counting techniques will be analyzed. 



Learning outcomes


Upon successful completion of this course, students will be able to:

Formulate proofs in combinatorics and graph theory
Contribution to Program Outcomes

Having the knowledge about the scope, applications, history, problems, and methodology of mathematics that are useful to humanity both as a scientific and as an intellectual discipline.

Describing, formulating, and analyzing reallife problems using mathematical and statistical techniques.

Having improved abilities in mathematics communications, problemsolving, and brainstorming skills.

Being fluent in English to review the literature, present technical projects, and write journal papers.

Exhibiting professional and ethical responsibility.
Method of assessment

Written exam

Homework assignment

Model some real life problems with graph theory.
Contribution to Program Outcomes

Having the knowledge about the scope, applications, history, problems, and methodology of mathematics that are useful to humanity both as a scientific and as an intellectual discipline.

Communicating between mathematics and other disciplines, and building mathematical models for interdisciplinary problems.

Describing, formulating, and analyzing reallife problems using mathematical and statistical techniques.

Having improved abilities in mathematics communications, problemsolving, and brainstorming skills.

Being fluent in English to review the literature, present technical projects, and write journal papers.
Method of assessment

Written exam

Relate algebra, linear algebra and geometry with graph theory.
Contribution to Program Outcomes

Having the knowledge about the scope, applications, history, problems, and methodology of mathematics that are useful to humanity both as a scientific and as an intellectual discipline.

Communicating between mathematics and other disciplines, and building mathematical models for interdisciplinary problems.

Describing, formulating, and analyzing reallife problems using mathematical and statistical techniques.

Having improved abilities in mathematics communications, problemsolving, and brainstorming skills.
Method of assessment

Written exam

Grasp advanced counting techniques and perform various operations with generating functions
Contribution to Program Outcomes

Describing, formulating, and analyzing reallife problems using mathematical and statistical techniques.

Having improved abilities in mathematics communications, problemsolving, and brainstorming skills.
Method of assessment

Written exam


Contents


Week 1: 
History, Fundamental Definitions, Eulerian graphs 
Week 2: 
Degree, Walk, Path, Cycle and Trees 
Week 3: 
Adjacency and Incidence Martices of Graphs 
Week 4: 
Directed Graphs

Week 5: 
Midterm exam 1,Matchings and Applications

Week 6: 
Connectivity

Week 7: 
Planar Graphs and The Famous 4coloring problem

Week 8: 
Vertex coloring and its Applications

Week 9: 
Edge coloring and its Applications 
Week 10: 
Hamilton Cycles and The Traveling Salesman Problem 
Week 11: 
Midterm Exam 2, Latin squares 
Week 12: 
Recursive Relations 
Week 13: 
Generating Functions 
Week 14: 
Integer Partitions

Week 15*: 


Week 16*: 
Final Exam 
Textbooks and materials: 

Recommended readings: 
1. Douglas West, Introduction to Graph Theory (2nd Edition), Prentice Hall 2. J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, North Holland 3. Richard Brualdi, Introductory Combinatorics (3rd Edition), Pearson 

* Between 15th and 16th weeks is there a free week for students to prepare for final exam.




Assessment



Method of assessment 
Week number 
Weight (%) 

Midterms: 
5  11 
60 
Other interm studies: 

0 
Project: 

0 
Homework: 

0 
Quiz: 

0 
Final exam: 
16 
40 

Total weight: 
(%) 



Workload



Activity 
Duration (Hours per week) 
Total number of weeks 
Total hours in term 

Courses (Facetoface teaching): 
3 
14 

Own studies outside class: 
5 
14 

Practice, Recitation: 
0 
0 

Homework: 
0 
0 

Term project: 
0 
0 

Term project presentation: 
0 
0 

Quiz: 
0 
0 

Own study for midterm exam: 
10 
2 

Midterm: 
4 
2 

Personal studies for final exam: 
10 
1 

Final exam: 
2 
1 



Total workload: 



Total ECTS credits: 
* 

* ECTS credit is calculated by dividing total workload by 25. (1 ECTS = 25 work hours)



>