ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE

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: Elective
Language of instruction: English
Mode of delivery: Face to face
Pre- and co-requisites: 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 Up

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

  1. Formulate proofs in combinatorics and graph theory

    Contribution to Program Outcomes

    1. 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.
    2. Describing, formulating, and analyzing real-life problems using mathematical and statistical techniques.
    3. Having improved abilities in mathematics communications, problem-solving, and brainstorming skills.
    4. Being fluent in English to review the literature, present technical projects, and write journal papers.
    5. Exhibiting professional and ethical responsibility.

    Method of assessment

    1. Written exam
  2. Model some real life problems with graph theory.

    Contribution to Program Outcomes

    1. 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.
    2. Communicating between mathematics and other disciplines, and building mathematical models for interdisciplinary problems.
    3. Describing, formulating, and analyzing real-life problems using mathematical and statistical techniques.
    4. Having improved abilities in mathematics communications, problem-solving, and brainstorming skills.
    5. Being fluent in English to review the literature, present technical projects, and write journal papers.

    Method of assessment

    1. Written exam
  3. Relate algebra, linear algebra and geometry with graph theory.

    Contribution to Program Outcomes

    1. 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.
    2. Communicating between mathematics and other disciplines, and building mathematical models for interdisciplinary problems.
    3. Describing, formulating, and analyzing real-life problems using mathematical and statistical techniques.
    4. Having improved abilities in mathematics communications, problem-solving, and brainstorming skills.

    Method of assessment

    1. Written exam
  4. Grasp advanced counting techniques and perform various operations with generating functions

    Contribution to Program Outcomes

    1. Describing, formulating, and analyzing real-life problems using mathematical and statistical techniques.
    2. Having improved abilities in mathematics communications, problem-solving, and brainstorming skills.

    Method of assessment

    1. Written exam
   Contents Up
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 4-coloring 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: Douglas West, Introduction to Graph Theory (2nd Edition), Prentice Hall
Recommended readings: 1. J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, North Holland
2. 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 Up
Method of assessment Week number Weight (%)
Mid-terms: 5, 11 60
Other in-term studies: 0
Project: 0
Homework: 0
Quiz: 0
Final exam: 16 40
  Total weight:
(%)
   Workload Up
Activity Duration (Hours per week) Total number of weeks Total hours in term
Courses (Face-to-face 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 mid-term exam: 10 2
Mid-term: 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)
-->