#
FI:MA010 Graph Theory - Course Information

## MA010 Graph Theory

**Faculty of Informatics**

Autumn 2021

**Extent and Intensity**- 2/1/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).

Taught online. **Teacher(s)**- prof. RNDr. Daniel Kráľ, Ph.D., DSc. (lecturer)

Jacob Cooper (seminar tutor) **Guaranteed by**- prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Department of Computer Science - Faculty of Informatics

Contact Person: prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Supplier department: Department of Computer Science - Faculty of Informatics **Prerequisites**- !
**PřF:M5140**Graph Theory &&! NOW (**PřF:M5140**Graph Theory )

Discrete mathematics. IB000 (or equivalent from other schools) is recommended. **Course Enrolment Limitations**- The course is also offered to the students of the fields other than those the course is directly associated with.

The capacity limit for the course is 200 student(s).

Current registration and enrolment status: enrolled:**0**/200, only registered:**0**/200, only registered with preference (fields directly associated with the programme):**0**/200 **fields of study / plans the course is directly associated with**- there are 26 fields of study the course is directly associated with, display
**Course objectives**- This is a standard introductory course in graph theory, assuming no prior knowledge of graphs. The course aims to present basic graph theory concepts and statements with a particular focus on those relevant in algorithms and computer science in general. Selected advanced graph theory topics will also be covered. Although the content of this course is primarily targeted at computer science students, it should be accessible to all students.
**Learning outcomes**- At the end of the course, students shall understand basic concenpts in graph theory; be able to reproduce the proofs of some fundamental statements in graph theory; be able to solve unseen simple graph theory problems; and be ready to apply their knowledge particularly in computer science.
**Syllabus**- Basic graph theory notions: graphs, subgraph, graph isomorphism, vertex degree, paths, connected components, directed graphs.
- Trees and the Minimum Spanning Tree problem.
- Vertex and edge connectivity.
- Planar graphs, duality of planar graphs, Euler's formula and its applications.
- Graph coloring, its basic properties and variants, including edge-coloring and list coloring.
- Matchings in graphs and packing problems.
- Computationally hard graph problems.
- Selected advanced topics (to be chosen from): Interval graphs, chordal graphs, graph minors, graph embeddings on surfaces, Ramsey theory.

**Literature**- DIESTEL, Reinhard.
*Graph theory*. 4th ed. Heidelberg: Springer, 2010. xviii, 436. ISBN 9783642142789. info - BONDY, J. A. and U. S. R. MURTY.
*Graph theory*. [New York, N.Y.]: Springer, 2008. xiv, 657. ISBN 9781846289699. info - http://diestel-graph-theory.com/
- MATOUŠEK, Jiří and Jaroslav NEŠETŘIL.
*Kapitoly z diskrétní matematiky*. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007. 423 s. ISBN 9788024614113. info - HLINĚNÝ, Petr. Základy teorie grafů.
*Elportál*. Brno: Masarykova univerzita, 2010. ISSN 1802-128X.*URL*info

*recommended literature*- DIESTEL, Reinhard.
**Teaching methods**- MA010 is taught in weekly 2-hour lectures, which are primarily focused on introducing the material (concepts, statements, proofs). The lectures are complemented with bi-weekly 2-hour (compulsory) tutorials where examples and problems related to the material presented during the lectures are made available to practise.
**Assessment methods**- The resulting grade will based either on the final written exam or a remote oral exam; the type of the exam will be determined by the COVID situation. To register for the exam, it is necessary to obtain at least 16 points from homework assignments; most of the homework assignments will have deadlines during the term.
**Language of instruction**- English
**Follow-Up Courses****Further comments (probably available only in Czech)**- The course is taught annually.

The course is taught: every week. **Listed among pre-requisites of other courses**- PřF:
**M5140**Graph Theory

!M5145 && !(FI:MA010)

- PřF:
**Teacher's information**- https://www.fi.muni.cz/~dkral/ma010.html

Basic information regarding course curriculum and examination can be found in the online syllabus MA010 in the Information System - "https://is.muni.cz/auth/el/1433/podzim20**/MA010/index.qwarp". More detailed information can be found on the course webpage maintained by the lecturer.Since 2020, the grade is determined by the final exam only.

Since 2016, grading of MA010 changes by including a written homework assignment worth 20% and decreasing the weight of the final exam to 60%.

Since 2009, MA010 is taught in English. Předmět MA010 je od roku 2009 vyučován primárně anglicky. Informace v angličtině mají přednost, české materiály jsou doplňkové.

- Enrolment Statistics (Autumn 2021, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2021/MA010