470-4302/02 – Graph Theory (TG)

Gurantor department	Department of Applied Mathematics	Credits	6
Subject guarantor	doc. Mgr. Petr Kovář, Ph.D.	Subject version guarantor	doc. Mgr. Petr Kovář, Ph.D.
Study level	undergraduate or graduate	Requirement	Optional
Year		Semester	summer
		Study language	English
Year of introduction	2015/2016	Year of cancellation
Intended for the faculties	FEI	Intended for study types	Follow-up Master

Instruction secured by
Login	Name	Tuitor	Teacher giving lectures
KOV16	doc. Mgr. Petr Kovář, Ph.D.
ZHA0057	Yifan Zhang

Extent of instruction for forms of study
Form of study	Way of compl.	Extent
Full-time	Credit and Examination	2+2
Part-time	Credit and Examination	10+10

Subject aims expressed by acquired skills and competences

Each student is supposed to - analyze real life problems - express them as a graph theory problem - solve the problem using graph theory methods - give an interpretation of the theoretical results in the terms of the original problems At the same time he should decide what are the limits of an ideal theoretical solution in contrast to the real situation.

Teaching methods

Lectures
Individual consultations
Tutorials
Project work

Summary

The course covers both basic and advanced topics of Graph Theory, often overlapping with other branches of mathematics (algebra, combinatorics). A mandatory part of the course is one or sometimes two projects focused on real life problems that are solved using methods of graph theory.

Compulsory literature:

J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2010).

Recommended literature:

D. B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371.

Way of continuous check of knowledge in the course of semester

During the semester each student prepares one or two projects. Topic of each project is chosen among topics presented in the lecture. The sumbission date and all assignments are available on the instructor webpage or in the university electronic information system. (Each student has to register for a topic.) For a pass it is necessary to have at least one project graded for at least 10 points.

E-learning

Other requirements

There are no other requirements.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures and discussions: - Graphs, simple graphs. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex. - Paths and cycles. - Trees, bridges and cuts. - Graph isomorphisms. - Connectivity and blocks. Cut sets. - Matching and covers in general and bipartite graphs. Perfect matchings. - Edge colorings. Chromatic index, Vizing's Theorem. - Vertex colorings, Chromatic number, Brook's Theorem. - Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Color Theorem. - Non-planar graph, measures of non-planarity. - Eulerian and Hamiltonian graphs. - Oriented graphs. Oriented paths and cycles. - Tournaments and graph models

Conditions for subject completion

Full-time form (validity from: 2015/2016 Winter semester)

Task name	Type of task	Max. number of points (act. for subtasks)	Min. number of points	Max. počet pokusů
Credit and Examination	Credit and Examination	100 (100)	51
Credit	Credit	20 (20)	10
Semestral project	Project	20	10
Examination	Examination	80 (80)	41	3
Written Part of the Exam	Written examination	60	30
Theory Part of the Exam	Oral examination	20	5

Mandatory attendence participation: participation at all exercises is obligatory, 2 apologies are accepted

Show history

Conditions for subject completion and attendance at the exercises within ISP: Completion of all mandatory tasks within individually agreed deadlines.

Show history

Occurrence in study plans

Academic year	Programme	Branch/spec.	Zaměření	Form	Study language	Tut. centre	Year	Type of duty
2024/2025	(N0541A170007) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	K	Czech	Ostrava	2	Compulsory	study plan
2024/2025	(N0541A170007) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	P	Czech	Ostrava	2	Compulsory	study plan
2024/2025	(N0541A170007) Computational and Applied Mathematics	(S02) Computational Methods and HPC		P	Czech	Ostrava		Optional	study plan
2024/2025	(N0541A170007) Computational and Applied Mathematics	(S02) Computational Methods and HPC		K	Czech	Ostrava		Optional	study plan
2024/2025	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	P	English	Ostrava	2	Compulsory	study plan
2023/2024	(N0541A170007) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	P	Czech	Ostrava	2	Compulsory	study plan
2023/2024	(N0541A170007) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	K	Czech	Ostrava	2	Compulsory	study plan
2023/2024	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	P	English	Ostrava	2	Compulsory	study plan
2023/2024	(N0541A170007) Computational and Applied Mathematics	(S02) Computational Methods and HPC		P	Czech	Ostrava		Optional	study plan
2023/2024	(N0541A170007) Computational and Applied Mathematics	(S02) Computational Methods and HPC		K	Czech	Ostrava		Optional	study plan
2022/2023	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics	NMS	P	English	Ostrava	2	Compulsory	study plan
2021/2022	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics		P	English	Ostrava		Choice-compulsory type B	study plan
2021/2022	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2020/2021	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2020/2021	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics		P	English	Ostrava		Choice-compulsory type B	study plan
2019/2020	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2019/2020	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		K	English	Ostrava		Optional	study plan
2019/2020	(N0541A170008) Computational and Applied Mathematics	(S01) Applied Mathematics		P	English	Ostrava		Choice-compulsory type B	study plan
2018/2019	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2018/2019	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		K	English	Ostrava		Optional	study plan
2017/2018	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2017/2018	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		K	English	Ostrava		Optional	study plan
2016/2017	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2016/2017	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		K	English	Ostrava		Optional	study plan
2015/2016	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		P	English	Ostrava		Optional	study plan
2015/2016	(N2647) Information and Communication Technology	(1103T031) Computational Mathematics		K	English	Ostrava		Optional	study plan

Occurrence in special blocks

Block name	Academic year	Form of study	Study language	Type of block	Block owner
V - ECTS - mgr.	2023/2024	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2022/2023	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2021/2022	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2020/2021	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2019/2020	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2018/2019	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2017/2018	Full-time	English	Optional	401 - Study Office	stu. block
V - ECTS - mgr.	2016/2017	Full-time	English	Optional	401 - Study Office	stu. block

Assessment of instruction

2017/2018 Summer