470-4302/02 – Graph Theory (TG)

Gurantor departmentDepartment of Applied MathematicsCredits6
Subject guarantordoc. Mgr. Petr Kovář, Ph.D.Subject version guarantordoc. Mgr. Petr Kovář, Ph.D.
Study levelundergraduate or graduateRequirementOptional
YearSemestersummer
Study languageEnglish
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOV16 doc. Mgr. Petr Kovář, Ph.D.
ZHA0057 Yifan Zhang
Extent of instruction for forms of study
Form of studyWay 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.

Additional study materials

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

Core materials are available on the instructor's website: http://homel.vsb.cz/~kov16/predmety_tg.php

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

Part-time form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)		Min. number of pointsMax. 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, absence of 20% can be excused

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 yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2025/2026 (N0541A170007) Computational and Applied Mathematics (S01) Applied Mathematics NMS P Czech Ostrava 2 Compulsory study plan
2025/2026 (N0541A170007) Computational and Applied Mathematics (S01) Applied Mathematics NMS K Czech Ostrava 2 Compulsory study plan
2025/2026 (N0541A170007) Computational and Applied Mathematics (S02) Computational Methods and HPC P Czech Ostrava Optional study plan
2025/2026 (N0541A170007) Computational and Applied Mathematics (S02) Computational Methods and HPC K Czech Ostrava Optional study plan
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 nameAcademic yearForm of studyStudy language YearWSType of blockBlock 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