MA010 Graph Theory (an online guide)

Course organization

The primary teaching language is English (selected tutorials will be held in Czech).

Předmět MA010 je od roku 2009 vyučován primárně anglicky (některá cvičení budou stále česky).

All the MA010 lectures will be held in English. However, some of the tutorials will be in Czech, and so the students should take care of this fact. This will be announced when the timetable is available. Generaly, all announcements for the students of MA010 will be posted in the MA010 news thread https://is.muni.cz/auth/df/aktuma010/ (in English), and only the most important ones will be also sent via email. Students should read this forum regularly and pay attention to the announcements. No excuses will be allowed for not reading these announcements.

Studentům MA010 je doporučována aspoň základní pasivní znalost angličtiny. Pro ty, kteří nejsou až tak sběhlí v angličtině, je k dispozici původní plnohodnotný učební text v češtině a na přednáškách budou paralelně promítány i české slidy. Při hlášení na cvičení si dejte pozor, která z nich budou anglicky a která česky. Rozdělení cvičení bude oznámeno při zveřejnění rozvrhu. Obecně oznámení a aktuality pro studenty MA010 budou vždy oznamovány na tematickém fóru předmětu https://is.muni.cz/auth/df/aktuma010/ (obvykle anglicky) a jen ty nejdůležitější z nich budou rozeslány i emailem. Nebude odpovídáno na samostatné dotazy, které již jsou na web stránkách zodpovězeny, ani nebudou přijímány omluvy z důvodu neznalosti těchto oznámení.

This online syllabus in IS MU

All the teaching materials of MA010 are organized and posted online in IS MU. Refer to the list of study materials and weekly syllabus below... (There you can find all you need.)

Course discussion group in IS MU

Our subject has its discussion group in IS MU where students should post their questions and comments regarding both the curriculum and course organization. We advise students to use this discussion since the answers then serve all other students (and so we strongly prefer to answer there and not in private emails).

Attendance of lectures and tutorials  -  Docházka

MA010 lectures are 2h each week while tutorials are 2h bi-weekly, see in your timetable. Attendance of lectures is voluntary, and videorecording of lectures will be available later on. On the other hand, tutorials are compulsory and penalties will be imposed on students not coming to their tutorials regularly.

Tutorial attendance rules: Out of the usual six (of bi-week frequency) tutorials, one can be skipped without any consequence. If a student skips two tutorials without a proper excuse recorded in IS(!), then he receives -5 "malus" points, and if he skips more than two tutorials, then the penalty is -10 points. Beware that these negative points count towards the semester limit of >=10 points, see below!

Docházka na cvičení: Ta jsou povinná a studenti mohou bez následků vynechat jen jedno z běžných šesti cvičení za semestr. Při vynechání dvou bez omluvenky v IS student získá malus -5 bodů, při více už -10 bodů. Tyto penalizace se počítají do semestrálního hodnocení s dolním limitem 10 bodů, viz níže!

Study materials MA010

For start (prior to 2009), all the course materials had been prepared in Czech, including an extensive self-contained study text of Graph Theory (Teorie grafů) with all lectures and tutorials. These materials are provided here to all students understanding Czech language. For English-only-speaking students, the following materials are provided:

  • A very good introductory textbook Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil) is available in the library, from Google books (restricted), or on the market. Significant parts of our curriculum are originally based on this book, and references to it are provided throughout the lectures in this guide. It is highly advised for every student to (at least) look into this book. While our course is interested in chapters from number 4 "Graphs: an introduction", the first three chapters cover basic discrete mathematics which students should already know from, e.g., the IB000 course. 
  • A Czech edition of the book, Kapitoly z diskrétní matematiky, is available as well (quite cheap). There are only slight differences in the section numbering between these editions.
  • The course slides are translated from Czech into English, and posted on the web. Some materials from the tutorials will also be collected and posted later on. No translation of the whole study text is planned (since there are so many more textbook available in English).
  • Many other, online available, graph-theory related study materials are collected in the course, and posted on the web as well. The collected materials are (or will be) referenced from this online guide.

Lectures MA010

The whole curriculum of MA010 is organized into the lectures where each lecture corresponds to one week of teaching (of semester). The content of each lecture is summarized in the syllabus below (and is supplemented with online accessible references), and will be posted on the web as the course slides (in PDF). The first eight lectures constitute the mandatory core curriculum which every student must learn to pass the MA010 course. Subsequent lectures (nine to higher) present, time depending, some additional interesting graph material which may vary from year to year, and which will not be examined directly (though its knowledge will also be helpful at the final exam).

Every lecture of MA010 is complemented with a tutorial hour (organized bi-weekly), which is devoted to informal explanation of the presented material and practicing graph theory exercises. In tutorials, students should learn how to understand and use the theoretical knowledge from lectures. Notice (cf. above) that attendance to the MA010 tutorials is compulsory.

Study materials in English
Study materials MA010 for English-speaking students. English is the primary teaching language of MA010 since 2009, however, old study materials in Czech are provided as well in a separate directory.
Lecture recordings
Here you can find videorecorded lectures of MA010. It is, however, not suggested to rely on these recordings, come to the lectures.
Učební materiály CZ
Dokumenty a další podklady k výuce. Plnohodnotné, ale mají především doplňkový význam, neboť od 2009 probíhá výuka MA010 primárně v angličtině.
Grafy - učební text CZ
Učební text předmětu MA010 na FI MU v češtině. Určeno pro plnohodnotné doplňkové samostudium, neboť od 2009 probíhá výuka primárně v angličtině.
Grafy - učební text čb CZ
Aktuální učební text předmětu MA010 na FI MU v češtině. Určeno pro plnohodnotné doplňkové samostudium, neboť od 2009 probíhá výuka primárně v angličtině. Černobílá verze.

Course examination requirements

Students are expected to learn all the presented curriculum of (at least) the first eight mandatory lectures on Graph theory. This includes understanding the definitions, knowledge of the presented statements (theorems) and algorithms, and ability to reproduce the presented mathematical proofs and give new similar proofs. To be very accurate, this subject is not about memorizing the statements (definitions, proofs, etc.), but about understanding them, and so the exams will be given such that even perfectly memorized knowledge will be useless.

Understand, not memorize!

Examination score will consist of three parts summed up together:

  • 20% Compulsory midterm classroom test, about basic graph properties, composed of questions similar to those given in the online questionaries below. Maximum score will be 20 points, and at least 10 points will be required for the final exam. A failed midterm test can be repeated once.
  • 80% Final written exam (cf. also sample past exams):
    • Up to 40 points will be given for answering routine questions about graphs and their properties. Though routine, not all the questions will be easy.
    • Up to 40 additional points will be given for solving rather difficult graph problems. It is expected that only mathematically-skilled students will be able to fully solve this part since it requires creative mathematical thinking and ability to give formal mathematical proofs.
  • bonus See below for possibilities of getting extra bonus points.

Altogether, more than 50 points will be required to pass the exam. Final grade will be determined from the final point score, using a scale announced during the course exam period.

Velmi stručně česky

Při testech a zkouškách obvykle bude (často, ale ne vždy) na výběr mezi češtinou a angličtinou. Body bude možné získat na povinném semestrálním testu (nejvýše 20, požadováno je aspoň 10 ke zkoušce) zhruba v třetině až půli semestru. Dále pak na zkoušce bude možno získat až 40 bodů za příklady testující rutinní (ale ne až tak snadné) porozumnění teorii grafů a dalších až 40 bodů za obtížné příklady zkoušející vaši schopnost řešit nové matematické problémy a podávat matematické důkazy. Pro úspěšné složení zkoušky je nutno v součtu získat více než 50 bodů.

Pamatujte, jedná se o matematický předmět. Musíte mu porozumnět, ne se učit nazpaměť!

Self-testing: online questionaries
These automated questionaries give students an opportunity to test their basic knowledge about graphs online (any time). It is highly recommended to practice them -- first, they show you how good you are in the most basic graph-theory terms, and second, similar questionaries will be given at the compulsory midterm test of MA010.
Past sample exams
This folder contains sample final exams of MA010 from past years. They are provided for the students to see what they can (roughly) expect at their final exam, and for self-practicing.
Procvičovací odpovědníky
Odpovědníky o grafech k domácímu procvičení. Ve stejném duchu, ale už pod dozorem v učebně, bude dán povinný semestrální test.
Staré zkoušky CZ
Ukázkové zkouškové písemky z minulých let v češtině.

Voluntary bonus assignments and points

In addition to mandatory term test(s) and final exams, some (actually the best) students can receive extra bonus points during the semester which count already toward the semester limit of >=10 points. Generally, these bonus points are awarded only for extraordinary achievements by the students, and their allocation is at sole decision of the teacher. For instance:

  • During the first weeks of the semester, bonus homework assignments will be announced. These will be, usually, some relatively hard mathematical problems concerning graph theory. Interested students are expected to think about these problems, and come up with some new ideas towards solution of the selected problem. The good (and the best) solutions will then be awarded a bonus which may reach from 5 up to 80 points. Often even partial solutions or just nice related side ideas may be awarded.
  • Another (non-exclusive) possibility to receive some bonus points is to find a (significant) mistake somewhere in the course materials or tests, and come up with a detailed analysis of the issue and some suggestions of a solution.
Bonus submissions
This folder is provided for submissions of voluntary bonus homework assignments (details appear also in this folder whenever announced at the lecture).