INTRODUCTION TO GRAPH THEORY

Course Code:

MATH 440

Course Type:

Area Elective

P:

3

Lab:

0

Laboratuvar Saati:

0

Credits:

3

ECTS:

7

Course Language:

English

Course Objectives:

Çizgeler, bilimdeki, işletmedeki ve endüstrideki pek çok problemde model olarak kullanılır. Bu dersin amacı, öğrencilere grafikler, yönlendirilmiş grafikler ve ağaçlar gibi çizgelerin temel bilgileriyle birlikte, çizgelerin gerçek hayat uygulamalarını ve çok bilinen bazı algoritmalarını tanıtmaktır.

Course Content:

Fundamental concepts of graphs and digraphs. Trees and distance. Matching and factorization. Connectivity, networks. Graph coloring. Planar.

Course Methodology:

1: Lectures, 2: Problem Solving

Course Evaluation Methods:

A: Written examination, B: Homework

Vertical Tabs

Course Learning Outcomes

Learning Outcomes	Teaching Methods	Assessment Methods
1) Manipulate the basic concepts associated with graphs such as paths, cycles, vertex degrees, and counting. Directed graphs. Use these definitions in proofs, and calculate specific values.	1,2	A
2) The concept of tree, spanning trees, optimization.	1,2	A
3) Cuts and connectivity. Network Flow problems and algorithms	1,2	A
4) Matching and Covers. Algorithms and Applications	1,2	A
5) Vertex Colorings	1,2	A
6). Characterization of Planar Graphs. Parameters of Planarity.	1,2	A

Course Flow

COURSE CONTENT
Week	Topics	Study Materials
1	What Is a Graph? Paths, Cycles, and Trails. Vertex Degrees
2	Counting. Directed Graphs
3	Basic Properties of Trees. Spanning Trees and Enumeration
4	Optimization and Trees
5	Matching and Covers. Algorithms and Applications.
6	Matching in General Graphs.
7	Cuts and Connectivity. K-connected Graphs.
8	Network Flow Problems
9	Vertex Colorings and Upper Bounds
10	Structure of k-chromatic Graphs. Enumerative Aspects.
11	Embeddings and Euler's Formula. Characterization of Planar Graphs.
12	Parameters of Planarity.
13	Line Graphs and Edge-Coloring. Hamiltonian Cycles.
14	Planarity, Coloring, and Cycles.

Recommended Sources

RECOMMENDED SOURCES
Textbook	1. Douglas B. West - Introduction to Graph Theory (Pearson) 2. Wilson RJ - Introduction to Graph Theory (Longmans)
Additional Resources

Assessment

ASSESSMENT
IN-TERM STUDIES	NUMBER	PERCENTAGE
Mid-terms	1	100
Quizzes	-	0
Assignments	-	0
Total		100
CONTRIBUTION OF FINAL EXAMINATION TO OVERALL GRADE	1	60
CONTRIBUTION OF IN-TERM STUDIES TO OVERALL GRADE		40
Total		100

Course’s Contribution to Program

COURSE'S CONTRIBUTION TO PROGRAM
No	Program Learning Outcomes	Contribution
No	Program Learning Outcomes	1	2	3	4	5
1	Relate mathematics to other disciplines and develop mathematical models for multidisciplinary					X
2	Acquiring fundamental knowledge on fundamental research fields in mathematics and its application to science, industry, and business.					X
3	Ability form and interpret the relations between research topics in mathematics					X
4	Ability to define, formulate and solve mathematical problems					X
5	Consciousness of professional ethics and responsibility			X
6	Ability to communicate actively			X
7	Ability of self-development in fields of interest					X
8	Ability to learn, choose and use necessary information technologies			X
9	Lifelong education			X

ECTS

Activities	Quantity	Duration (Hour)	Total Workload (Hour)
Course Duration (14x Total course hours)	14	3	42
Hours for off-the-classroom study (Pre-study, practice)	14	6	84
Mid-terms (Including self study)	2	10	20
Quizzes	-
Assignments	-
Final examination (Including self study)	1	20	20
Total Work Load			166
Total Work Load / 25 (h)			6.64
ECTS Credit of the Course			7

Search form