Students are required to check the course news thread frequently! https://is.muni.cz/auth/df/aktuma010/
This noticeboard contains up to date organization information, dates of term tests, exceptional circumstances, etc...
Studenti jsou povinni pravidelně číst aktuality v tomto tematickém fóru ve vyučovacím jazyce angličtině.

Discussion group MA010: https://is.muni.cz/auth/diskuse/diskusni_forum_predmet.pl?lang=en;guz=13662342
The subject has its general 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).

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.

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ěť!

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.

Outline

• What is a graph
  vertices (sometimes "nodes") and edges, simple graphs, cycles, paths, complete graphs
  
• Vertex degrees
  vertex degree (also minimal and maximal), degree sequence of a graph (score) and its properties
• Subgraphs and isomorphism
  subgraph and induced subgraph, cycles (triangles) and paths in a graph, cliques and independent sets;
  isomorphism between two graphs, how to recognize (non-)isomorphic graphs
  
• Digraphs and Multigraphs
  directed graphs (with arrows), multigraphs (with multiple edges and loops)

Goals

This is the basic introduction which shows what is a graph and what are the few basic terms needed to describe a graph (its vertices and edges, subgraphs, and isomorphism with other graphs). Students should learn about vertex degrees and the properties of a degree sequence (score) of a graph. Then about subgraphs and induced subgraphs in a graph (when, and how many times, our graph contains a specific subgraph, say a triangle or a path of length four...). The most important knowledge or ability from the first lecture (so important that it will be repeated also in the tutorials of some next lectures) is to recognize the relation of isomorphism of graphs (i.e. decide whethe given pair(s) of graphs are isomorphic or non-isomorphic), meaning that the presented graphs are "essentially the same".

Graphs versus Multigraphs

It is not a big deal, but all students should understand from the beginning that there exist graphs which we mean simple (edges are two-element subsets, hence no bunches of parallel edges and no loops are possible), and then there are multigraphs in which a bunch of edges may share the same pair of endvertices (parallel edges) and even an edge with both ends in the same vertex may exist (called a loop). When we say a graph, we mean simple graph! 

Pictures of graphs

When dealing with graphs (on a paper, not in a computer), the best way to "get grip" on it is to draw a nice graph picture. One of the early goals of our course is to teach you to draw graphs nicely, and see their properties in the pictures. Often, one has to try several pictures of the same graph before (s)he finds the right one - the one on which the answer or solution appears obvious. Likewise the next example (how many nonisomorphic graphs can you see?)...

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]

Study Sections 4.1 (from page 109), starting part of 4.2, and whole 4.3.

Remarks
In the basic graph terminology, there exists one annoying ambiguity -- with the notation P_n for a path, some authors mean the index n to be the number of vertices, not the length. We stick with the course book and thus P_n is the path of length n.

Older editions of the book (both English and Czech) lack one of the starting chapters, and so the graph theory chapters start with number 3, not 4 as referred above. Intelligent students can surely subtract 1 from the chapter number in such a case... Furthermore, some of the book sections, mainly concerning Eulerian graphs and shortest paths, are arranged differently in the older or Czech editions. All our references are based on the 2008 English edition (see on google books).

About embedded interactive demonstrations

For practical illustration of some of the graph theory terms from our curriculum, we provide their interactive demonstrations in some lectures. These demonstrations usually use java which may slow down your browser, and so they are not shown by default. Open the respective subsections when you want to access the demonstrations.

About interactive tutorials

Whenever possible, we complement the theoretical content of the lectures with online available tutorials and demonstrations. These are provided as external links and you are encouraged to try them. Again, some notations of these external tutorials may conflict with our lectures, and then (let us know) we will explain the differences before the link.

IS Questionaries

Besides tutorials, all students have a good chance to test their routine graph-theory skills in these online IS MU questionaries below. The questionaries are provided only for the first few basic lectures (since, obviously, more difficult math theory cannot be seriously tested online). Still, problems analogous to the provided questionaries will be used at the compulsory midterm test.

Glossary

Finally, we provide a link to a brief glossary of graph theory notation (wikipadia). Use it only for a quick reference, but not for studying! Some parts may differ from the lectures, and then the lectured stuff takes precedence (such as for P_n; let us know if this happens elsewhere).

For practical illustration of some of the graph theory terms from our curriculum, we provide their interactive demonstrations in each lecture. These demonstrations usually use java which may slow down your browser, and so they are not shown by default. Look at them as you like...

Basic graph classes - interactive constructions

Playing with subgraphs (draw the graph yourself)

Finally: "ISO-morphing" the CUBE ...

These demonstration applets are taken (linked) from Graph Theory Lessons by Christopher P. Mawata, http://oneweb.utc.edu/~Christopher-Mawata/petersen/ .

Outline

• Connections in a graph, components
  walks in a graph,the equivalence relation of connections between pairs of vertices, connected components
  
• Searching through a graph
  principles of depth-first search and breadth-first search algorithms
  
• Higher levels of connectivity
  k-connected and k-edge connected graphs, characterization of 2-connected graphs ("ear addition", or subdivisions of edges), Menger's theorem (see also Lecture 6)
  
• Eulerian tours and trails
  tours (closed) or trails (not closed) in a graph - no repetition of edges, Eulerian tours or trails, Eulerian graphs ("seven bridges") and the even degree condition
  

Goals

This lecture is primarily devoted to the basic task a computer scientist (or engineer) has to do with a graph: to algorithmically "search through the graph". Students will learn about the concept of graph connectivity and see a skeleton of the two basic graph search algorithms DFS a BFS. Additionally, the extended concepts of higher vertex- and edge-connectivity are briefly surveyed, and a specific theoretical attention is paid to 2-connected graphs. Lastly, students will hear about the famous "seven bridges" problem which is considered as the historical basis of the whole modern graph theory, and its solution given by Euler - his even-degree condition.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study Sections 4.2 (a fragment on pages 120-121), whole 4.4, and voluntarily also 4.5 and 4.6.

On the other hand, the (rather simple) algorithmic part - searching through a graph (DFS, BFS, etc...), is not primarily covered by the book, and we refer to some great online resources below.

Remark
Some other literature use terms "path", "circuit", or "cycle" in a context where repetition of vertices (not edges though) is allowed. This is WRONG, and we shall always use the correct terms "trail" or "(closed) tour" there.

Interactive tutorials

IS Questionaries

Listing connected components of a graph (draw the graph yourself)

Showing directed Eulerian tours (draw the graph yourself)

Outline

• Distance in graphs
  definitions of ordinary distance and weighted distance (when edges have lengths), triangle inequality, radius and diameter
  
• All-pairs distances
  computation of the distances between all pairs of vertices - dynamic Floyd-Warshall algorithm, its proof
• Single-source shortest path
  Dijkstra's algorithm (a variant of graph searching, Lecture 2), its proof, and an outline of the A* algorithm which enriches Dijkstra

Goals

Students should understand the concept of distance in graphs (also in the weighted variant), and be able to compute the distance between two vertices. The main goal is to show the beautiful and educational Floyd-Warshall and Dijkstra's algorithms. These algorithms not only solve the mentioned shortest path problems, but each one also illustrates some very powerful algorithm design concepts which students will find useful in other areas of CS. 

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Finish studying the whole Section 4.2 (distances in graphs).

On the other hand, the algorithmic part of this lecture - finding shortest paths (Floyd-Warshall and Dijkstra), is not covered by the 2008 English edition of the book, and we refer to some great online resources below. (The 2010 new Czech edition already includes a dedicated section on Dijkstra's algorithm.)

IS Questionaries

The applet web page,  by Papagelis Athanasios.

The applet web page,  by Papagelis Athanasios.

Dijkstra's Shortest Path Algorithm

The applet home page (copyright Carla Laffra)

Outline

• Definition and basic properties of trees
  tree is a connected acyclic graph; basic equivalent characterizations - minimal connected, maximal acyclic, path uniqueness, number of edges
  
• Rooted trees and isomorhpism testing
  rooted, and planted (i.e. rooted plus ordered) trees, planted tree coding and decoding, tree center, isomorphism testing for trees via coding 
• Spanning trees
  definition, and enumeration of spanning trees in a graph

Goals

The main goal of this lecture is to survey (and prove) some basic theoretical properties of trees, i.e. the simplest graphs from a structural point of view. The numerous presented simple proofs, moreover, show "in action" several powerful proof methods and tools of discrete mathematics. Additionally, a nice and fast method of testing isomorphism between trees is outlined.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study the whole Sections 5.1, 5.2, and a few words from 5.3 and Chapter 8. Specifically, Section 8.5 gives a (difficult) proof of the determinant formula for the number of spanning trees of a graph.

Remark
Unlike in the book, we are pure computer scientists, and thus we depict rooted trees with the root on the top.

Outline

• Minimum spanning tree (MST) problem
  definition of MST, Kruskal's greedy algorithm (with a proof), Jarník's algorithm (later known as Prim's algorithm), other relations
• Principles of greedy algorithms
  local "greedy" optimization, a simple job assignment problem with a greedy solution, when greedy solutions do not work optimally
  
• Matroids and abstract greedy optimization
  three axioms of independent sets of a matroid, matroid bases, the cycle matroid on the edges of a graph (independent = acyclic), the relation between matroids and an abstract greedy algorithm

Goals

This lecture primarily introduces the "greedy" method of discrete optimization - a step-by-step search through local optima which eventually leads (or should lead) to the global optimum. The method is illustrated with greedy algorithms for the Minimum Spanning Tree problem (MST - one of the basic discrete optimization problems), and a simple variant of a job assignment. The abstract greedy algorithm then motivates the introduction of matroids - useful (though rather obscure) discrete structures generalizing graphs. 

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study the whole Sections 5.3, 5.4, and 5.5.

Furthermore, have a short look at extensive online resources about greedy algorithms and specifically the MST problem.

Minimum Spanning Tree, the greedy algorithm of Kruskal

The applet web page,  by Papagelis Athanasios.

Minimum Spanning Tree, the algorithm originally by Jarník (1930's!)

The applet web page,  by Papagelis Athanasios.

Outline

• Definition of a flow network
  flow network -- a weighted directed graph, with source and sink, capacity constraints of arcs; the flow conservation rule, total flow through the network
• Finding maximum flow
  minimum cut in a network, residual capacity of arcs and augmenting (residual or "unsaturated") paths, simple Ford-Fulkerson's augmentation algorithm, the "max-flow min-cut" theorem, overview of improved algorithms
  
• Generalized network flow problems and applications
  vertex capacities, (min-capacities, multi-commodity flow), applications in bipartite matching, Menger's theorem, systems of distinct representatives
  

Goals

The main goal of this lecture is to teach students about another basic problem of combinatorial optimization -- the network flow problem. Similarly as with the MST problem (Lecture 5), simple, elegant and fast algorithmic solutions of this problem are known. Moreover, the "max-flow min-cut" theorem is stated and proved, and its numerous consequences are given. Among the consequences; an efficient solution of the bipartite matching problem is outlined, a proof of Menger's theorem (Lecture 2) is given, and Hall's theorem about systems of distinct representatives is stated and proved as well.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Unfortunately, the network flow problem is not covered in this textbook. Besides the course lecture, students can read in the online resources linked below, and in Chapter 6 of Diestel's textbook for advanced study.

Network flow - an interactive animation  (change the capacities as you like)

Outline

• Graph colourings and chromatic number
  definition of a proper colouring, chromatic number, basic properties and two-colourable (bipartite) graphs, k-degenerated graphs and greedy colouring, graphs of high chromatic number
  
• Other related problems
  edge colouring and chromatic index, Vizing theorem, list colouring (choosability), Hamiltonian paths and cycles
• NP-complete problems on graphs
  3-colourability, independent set, vertex cover, dominating set, Hamiltonian circuit, etc
  
• The vertex-cover story
  some parameterized algorithms for the k-vertex cover problem

Goals

While the previous lectures mentioned numerous applications of graph theory in computer science which have efficient solutions, this lecture shows the opposite side -- graph problems which are NP-complete ("hopeless"). Prominent such a problem is the colourability one (and its variants), others include the Hamiltonian cycle/path, independent set, vertex cover, etc. Since especially the colourability problem has been a strong driving force of development of the whole graph theory since 19th century, we pay a special attention to it here and in the next lecture.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Again, the content of this lecture is not much covered by this textbook. However, read the definition of the graph colouring problem in Section 6.4. See the provided online references, or read Chapter 5 of Diestel's textbook for advanced study.

Proper graph colouring demonstration (draw the graph first)

Outline

• Drawings of graphs, planar graphs
  basic properties of planar embeddings of graphs, faces, Jordan curve theorem, Euler's formula, bounding the number of edges of a planar graph
  
• Characterization of planar graphs
  non-planarity of K5 and K3,3, Kuratowski theorem, uniqueness of embeddings
• Colouring maps and planar graphs
  the four colour problem, colouring planar graphs by 6 and 5 colours, (the four colour theorem)
• Practical "nice" drawings
  how to get aesthetical and understandable (or pleasurable) drawings of a graph, the spring model
  

Goals

The purpose of this lecture is to give a thorough introduction to planar graphs (those without "crossings" of edges), their basic properties and Kuratowski's characterization of them. From historical perspectives, planar graphs are tied with geometric polyhedra, and their practical importance should be quite obvious -- in many applications, planarity is essential or unavoidable. For historical reasons, we also look at the famous Four Colour Problem, continuing on the colouring topic from the last lecture. Finally, we touch the practical question how to find an aesthetical drawing of a nonplanar graph.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study Sections 6.1, 6.2, and 6.3. However, most of the content of 6.1 (about other surfaces) can be left till future Lecture 11.

Remark
Notice that the book first deals with nonplanarity of K5 (which is not so easy to prove in this context) and then introduces Euler's formula, while we first prove Euler's formula and then use it to "easily" prove nonplanarity of K5. The truth is that neither of these statements is actually easy and they both strongly rely on the powerful Jordan curve theorem (which we just briefly mention).

Interactive polyhedra

From ibiblio.org, the public's library and digital archive.

Planarity

Created by John Tantalo.
Instructions: Arrange the vertices such that no edges overlap.

Graph Layout - examples using the spring model

From JDK 1.4 Demo Applets by Sun.

alt="Your browser understands the tag but isn't running the applet, for some reason." Your browser is completely ignoring the tag!     alt="Your browser understands the tag but isn't running the applet, for some reason." Your browser is completely ignoring the tag!     alt="Your browser understands the tag but isn't running the applet, for some reason." Your browser is completely ignoring the tag!

Subsequent lectures (nine to higher) present, time depending, some additional interesting graph material which will not be examined directly (though its knowledge will also be helpful at the final exam). The contents of these additional lectures may vary from year to year, and not all extra topics outlined in this syllabus will be presented.

Generally, the additional topics are not covered at all by the course textbooks, and only online materials are presented for them.

Outline

• Intersection graphs (of objects or sets)
  definition of an intersection graph of a set family, interval graphs as an example
• Chordal graphs and their properties
  definition, simplicial decomposition, chordal graphs as intersection graphs of subtrees in a tree
  
• Some special classes of intersection graphs
  line graphs, interval graphs, circle graphs, disc graphs, etc, contact graphs,
  string and segment graphs

Goals

This lecture introduces some basic concepts of intersection representations of graphs, and of so called "graph classes" topics. Intersection graphs are mostly related to geometric objects, but some abstract results are also provided. For instance, the chordal graphs turn out to be very important in other parts of graphs theory (see Lecture 10*). Some parts of this lecture are also related to planarity (Lecture 8).

Remark (repeated)
Subsequent lectures (nine to higher) present, time depending, some additional interesting graph material which will not be examined directly (though its knowledge will also be helpful at the final exam). The contents of these additional lectures may vary from year to year, and not all extra topics outlined in this syllabus will be presented.

Generally, the additional topics are not covered at all by the course textbooks, and only online materials are presented.

Alternative book: [Topics in intersection graph theory, McKee - McMorris]
                                        [Graph classes: a survey, Brandstädt, Le, Spinrad]

Seven intervals of the real line and the corresponding interval graph.

A circular-arc graph (left) and a corresponding arc model (right).

             A 5-vertex graph (left) and its line graph (right) with former edges as the vertices.

Circle (left) and permutation (right) representations of the same (isomorphic) 5-vertex graph.

Unit disk graph representation.

Outline

• Solving hard problems on special graphs
  why NP-hard problems have efficient solutions on special graphs, e.g. colourability or independent set on interval graphs, on trees, and on chordal graphs in a more general setting
  
• Tree decompositions of graphs
  four distinct (and equivalent) views of graph tree-width, some other "tree-shaped" decompositions
  
• Efficient algorithms on tree-shaped decompositions
  independent set, matching enumeration, EMSO problems, etc
  
• Minors in graphs
  the Graph Minors theorem of Robertson and Seymour, and efficient algorithms (just a very short outline)
  

Goals

This lecture briefly outlines the following algorithmic phenomenon - many NP-hard problems can be efficiently solved if we restrict the input to graphs of certain global structure, usually to be "tree-shaped" in a particular sense. Such an input structure allows to apply the dynamic programming paradigm and obtain more efficient algorithms. Moreover, this topic is very closely related to a deep theory of graph minors, one of the deepest parts of modern discrete mathematics.

Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.

Alternative book: [Reinhard Diestel: Graph Theory, electronic edition 2005]

Study in section 12 of the book (quite advanced reading, though).

Further study: Interested students can take the subject MA052 at FI, focused on interesting advanced chapters in structural graph theory, i.e. extending all the topics of this lecture.

Briefly showing an example of a tree-decomposition of the depicted graph.

The three-element bags of the decomposition are shown below, together with a colourful illustration of the interpolation property.

Outline

• Topological surfaces, classification
  surface as a compact 2-manifold without boundary, orientable and nonorientable surfaces - just a short survey
  
• Embeddings of graphs on surfaces
  surface embedding, faces and Euler's formula, forbidden characterizations of embeddability (everything is very brief and without proofs)
• Planar cover and emulator problems
  a brief introduction to this very specialized topic
  
• Graph crossing number
  drawing graphs with possible edge crossings, crossing minimization problem

Goals

The goal of this lecture is to show some very basic introduction to topological graph theory, i.e. the branch of GT which deals with drawings of graphs on various surfaces, both from the topological and combinatorial point of view. Though this topic may not sound like a much applicable thing, it has surprisingly deep theoretical and algorithmic consequences (as mentioned already in Lecture 10). Students should learn about what is a "surface", how to embed graphs there and how to recognize embeddability, and finally they will meet the so called crossing number problem.

Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.

Alternative book: [Graphs on surfaces, Mohar - Thomassen: free preview]

Further study: Interested students can take the subject MA051 at FI, focused on interesting advanced topics in topological graph theory.

Outline

• Some exemplary problems
  the party problem, Schur's theorem, points in convex position
  
• Ramsey theorem
  proof of the infinite version, compactness argument to the finite version, fine bounds for special cases
  
• Hales-Jewett theorem
  why high-dimensional tic-tac-toe game cannot end in a draw, formal formulation, van der Waerden's theorem
  

Goals

Informally saying, Ramsey theory is a theory of numerous results in different areas of discrete mathematics, all basically showing that "a complete disorder is mathematically impossible". In other words, Ramsey theory is looking for order inside disorder. We very briefly introduce some fundamental directions of research of this interesting branch of mathematics. This lecture stands somehow aside of the rest of the whole subject, but is neverthless very interesting from theoretical point of view.

Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.

Alternative book: [Ramsey Theory, In: Handbook of combinatorics (vol. 2)]
                                                      [Ramsey theory, by Graham, Rothschild, Spencer]