Máte zapnutý náhled celé osnovy, zpět na běžné zobrazení.
Načítání a prohlížení osnovy může být v závislosti na množství obsahu pomalejší.
Course NEWS 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ě.
Students are required to check the course news frequently!
Discussion group MA010: https://is.muni.cz/auth/cd/1433/podzim20**/MA010
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).
-
How "deep" is this graph 6. 12. 2012
-
Stationary Cops Catching a Robber in a Graph 30. 11. 2011
-
One (mobile) Cop Catching a Robber in a Graph 30. 11. 2011
-
Labeled Neighbourhoods in Planar Graphs 6. 12. 2012
Course organization
The primary teaching language is English (lecture slides shown also in Czech).
Předmět MA010 je od roku 2009 vyučován primárně anglicky (přesto uvidíte i české slidy na přednášce).
All the MA010 lectures and tutorials will be held in English.
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 také můžete všimnout, která z nich mají vyučující českého původu. Rozdělení cvičení bude oznámeno při zveřejnění rozvrhu.
Obecně oznámení a aktuality pro studenty MA010 budou vždy dá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 až sedmi 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 lectures where each lecture corresponds to one week of teaching (of the 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ěť!
After final exams
Once the grading of your final exam is finished, you may see the results scanned into IS (not only your points, but also the scans of your corrected answer sheets). Read those carefully and learn from your mistakes. Graders should post their grading scheme and general comments on your solutions into the appropriate discussion thread in IS (usually a new one for this particular exam). If there is a clear mistake in grading of your exam, then you may contact the grader directly with a clear and rigorous explanation of what happened and why your solution deserves more points (referring to the posted grading scheme). Particularly, never ask to "look at my solution again since I want more points, but I do not know where to get them"! Such requests will simply be ignored.
If, after careful reading(!), you are still in doubt about your answers and what was wrong with them, then ask the graders in the appropriate discussion thread in IS - this is important since usually more than one student has the same mistakes and others may learn from them. For these reasons we will not answer individual emails about your mistakes.
You pass the exam if your total score after the final exam is strictly greater than 50 points. The final grade then depends on the total score; currently, the "exchange rate" is E above 50, D for >=57, C for >=64, B for >=71, A for >=80. This may, however (though unlikely), change with any future exam term.
Bonus Assignments
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.
Deadline for all bonus homework assignments: 6.12. 2011
If you submit your solution by 20.11. 2011, then you automatically receive +50% of bonus points.
General remarks concerning bonus assignments
If you have any specific questions, do not hesitate to ask your tutor, or me directly.
What do we expect in a properly written solution? Mainly a mathematically well-structured and sound text, explicit formulations of all the claims you make for the solution, and full formal proofs of these claims (or citations to external sources, see below). You should also define all terms which are not common in our course. And, of course, we expect a self-contained PDF file, no other format is allowed!
Notice that bonus point rewards for your solutions are given at sole decision of the teacher, and the points shall reflect also relative quality of your solution in comparison to other submitted solutions. So even if your solution is not complete, just better than the others, you may be rewarded. The general rule is that only the part that presents your own original added value in the solution will score. Particularly, every suspected copywork will be disregarded immediately.
The last remark concerns external sources and citations. Of course, we expect you not to solve everything from scratch, but to look first for related theory and results in the literature. However, you always must fully cite all the sources you use, inluding say discussions with your teachers or fellow students. Your solutions should then give a valuable original contribution on top of the other (cited!) sources.
How "deep" is this graph 6. 12. 2012
This assignment concerns the following view of a decomposition of a graph G:
- Select a subset X of vertices of G, and complement the edges induced by X in G. Precisely, a new graph G' is constructed on the same vertex set, such that {u,v} is an edge of G' if, and only if, either not both u,v are in X and {u,v} is an edge of G, or both u,v are in X and {u,v} is not an edge of G.
- Decompose the new graph G' into its connected components, and apply the previous point onto each component recursively (in parallel).
The depth of the graph G is then defined as the lowest possible depth of this recursive construction of G. In other words, if H1,...,Hk are the connected components of the graph obtained by complementing edges of G on a subset X of vertices, then recursively depth(G)= 1+ minX [ max(depth(H1),...,depth(Hk)) ] (where the minimum is taken over all subsets X of the vertex set of G).
You task is to examine which graphs have "high" depth (in depedence on their number of vertices):
- For start, prove that the depth of a path of length n is growing with n. How good lower and upper estimates on depth(Pn) can you get?
- Show also the relation between the depth of G and of the complement of G (where edges on all vertices are complemented).
- The main question is to find a sequence of graphs which contain neither arbitrarily long induced paths nor their complements, but whose depth grows to infinity.
- Could you, by chance, asymptotically describe all the graphs which have depth bounded by some (arbitrary) constant <=D ?
By asymptotically we mean something like this, say: All the graphs of depth <=10 have "this nice shape", and all graphs that have "this nice shape" are of depth <=10000... For instance, a sequence of trees has bounded depth iff these trees have bounded diameter. Is there a similar description among all graphs?
Do not hesitate to ask for details in the IS discussion.
Good luck...
Read the general remarks in parent section!
Stationary Cops Catching a Robber in a Graph 30. 11. 2011
One (mobile) Cop Catching a Robber in a Graph 30. 11. 2011
Labeled Neighbourhoods in Planar Graphs 6. 12. 2012
As a motivation, notice an interesting feature - while the complete graph K6 is not planar, one can find a planar graph G and label its vertices with labels 1,2,3,4,5,6 such that every vertex v of G has neighbours of all other labels than the label of v. Try to find this example by yourself, or look here. Of course, some (or all) labels must occur multiple times in G, and it may even be helpful if some vertex has several neighbours of the same label (instead of required one). On the other hand, one cannot achieve analogous solution with seven labels (for K7) since such a labeled planar graph would need to have all degrees at least six.
Your primary assignment is to prove (or try to) the following claim:
No finite planar graph G can have vertices labeled with labels 1,2,3,4,5,6,7 such that every vertex v of G has neighbours of all other labels than the label of v, except that if v is labeled 1 or 2, then v need not have a neighbour of label 2 or 1, respectively.
In mathematical terminology, this is to prove that there is no finite planar emulator G of the graph "K7-edge".
Secondly, you may analyze the following slightly modified situation - now the task is to look at an existence of a bipartite planar graph with vertices labeled 1,2,3,4 in one part and A,B,C,D in the other part, such that every vertex labeled with a number can see all the four letters in its neighbourhood, and vice versa. Again, this is obviously not possible since such a bipartite planar graph would need to have all degrees at least 4. Your assignment is to prove (or try to) the following (stronger) claim:
No finite bipartite planar graph G can have vertices labeled with labels 1,2,3,4 in one part and A,B,C,D in the other part such that every vertex v of G labeled with a number has neighbours of all labels A,B,C,D and every vertex v of G labeled with a letter has neighbours of all labels 1,2,3,4; except that if v is labeled 1 or A, then v need not have a neighbour of label A or 1, respectively.
In mathematical terminology, this is to prove that there is no finite planar emulator G of the graph "K4,4-edge".
We suggest interested students to read more details on this topic in Lecture 11 and in the bachelor theses of Martin Derka and of Matěj Klusáček. Since this bonus assignment is quite difficult (even we do not have satisfactory answers to all these questions yet), any reasonable and significant step forward on this topic is valuable and can earn you the points. It may even happen (though very unlikely, but it happened in 2010) that one of the above claims is wrong and such a labeled graph exists - try to find it. This is getting to real science!
So good luck...
Read the general remarks in parent section!
Lecture 1: What is a graph
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 Pn 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 Pn 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 Pn; let us know if this happens elsewhere).
Interactive demonstrations (need java)
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/ .
Common Topics and Applications of Graphs
Knowing already what a graph is, the following four lectures survey some most common and applicable areas of graphs theory -- ranging from connectivity, through shortest paths, network flows, all the way to trees.
Lecture 2: Connectivity in Graphs
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
Interactive demonstrations (need java)
Listing connected components of a graph (draw the graph yourself)
Showing directed Eulerian tours (draw the graph yourself)
Lecture 3: Graph distance
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
Interactive demonstrations (need java)
The applet web page, by Papagelis Athanasios.
The applet web page, by Papagelis Athanasios.
Dijkstra's Shortest Path Algorithm
Lecture 4: Network flows
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.
Interactive demonstrations (need java)
Network flow - an interactive animation (change the capacities as you like)
Lecture 5: Basics of trees
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.
Other Interesting Areas of Graphs
There exist many more interesting and useful problems studied by graph theory. We offer a representative selection of those that should be in the curriculum of every general course on graphs, in the next three lectures.
Lecture 6: MST and greedy algorithms
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.
Interactive demonstrations (need java)
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.
Lecture 7: Colourings, and other hard problems
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.
Interactive demonstrations (need java)
Proper graph colouring demonstration (draw the graph first)
Lecture 8: Planarity and drawings of graphs
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 demonstrations (need java and flash)
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.
Some Advanced Lectures on Graphs *
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.
Lecture 9*: Intersection graphs in brief
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]
Picture demonstration of intersection graphs
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.
Lecture 10*: Width measures and minors
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.
Lecture 11*: Advanced drawings of graphs
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.
Lecture 12*: Introduction to Ramsey 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]