457-0305/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
Year1Semestersummer
Study languageCzech
Year of introduction2003/2004Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesFollow-up Master, Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOV16 doc. Mgr. Petr Kovář, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined 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). In the course are many real life problems solved by the methods of graph theory.

Compulsory literature:

D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999). J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2000).

Recommended literature:

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001).

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 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

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: 1) Graphs, simple graphs. Graph isomorphisms. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex. Paths and cycles. 2) Trees, bridges and cuts. Connectivity and blocks. 3) Matching and covers in general and bipartite graphs. Perfect matchings. 4) Edge colorings. Chromatic index, Vizing's Theorem. 5) Vertex colorings, Chromatic number, Brook's Theorem. 6) Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Folor Theorem. 7) Eulerian and Hamiltonian graphs. 8) Oriented graphs. Oriented paths and cycles. 9) Flows in networks, cuts. Maximal flow and minimal cut Theorem. Discussions: 1) Graphs, simple graphs. Degree of a vertex. Paths and cycles. Important graph classes. 2) Trees, bridges and cuts. Connectivity, blocks and articulations. 3) Graph connectivity. 4) Matching and covers in general and bipartite graphs. Perfect matchings. 5) Edge colorings. Chromatic index. 6) Vertex colorings, Chromatic number. 7) Planar graphs. Euler's formula for general planar graphs. 8) Eulerian and Hamiltonian graphs. 9) Oriented graphs. Oriented paths and cycles.

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Examination Examination 80  41
        Exercises evaluation Credit 20  10
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2009/2010 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2009/2010 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2008/2009 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2008/2009 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2007/2008 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2007/2008 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2006/2007 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2006/2007 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 2 Choice-compulsory study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 2 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 2 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 2 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner