| Homepage |
| Curriculum vitae |
| Publikace |
| Výuka |
| Kontakt |
Graph theory ST 2022/2023
Course: 470-4302: Graph Theory (TG)
Teacher: Petr Kovář
Hours: 6 credits (2/2/0/0/2)
Academic year: 2022/2023
Course outline is available in Edison system.
Semester
Lectures
Lectures will take place once a week. Tentative schedule: lectures on Thursday at 14:15. Participation on the lectures is required.
The seminar class starts after the lecture around 16:00 or sooner.
Homework (20 points)
During the semester students have to submit homework weekly (for a total of 20 points).
The textbook referred in the assignments is D.B. West: Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-014400-2. (available in the University Library).
The due date is always Wednesday of the following week.
Course credit "zápočet" will be given to those, who receive at least 10 points for the homework.
Week 27.2.-3.3.2023
Chapter 1. Reading
- Section 1.1. Basic concepts, isomorphism
Week 6.-10.3.2023
Chapter 1. Reading
- Section 1.1. Walks and paths, Petersen graph,
Week 13.-17.3.2023
Chapter 1. Reading
- Section 1.2. connection, components, cut-vertex, cut-edge, Eulerian trail
Chapter 1. Homework
- Exercise 1.1.2, 1.1.18 and 1.2.8
Week 20.3-24.3.2023
Chapter 1. Reading
- Section 1.2. bipartite graphs, Konig's Theorem on bipartite graphs, Section 1.3: degree-sum formula and some its corollaries. Theorem 1.3.9 and 1.3.13.
Chapter 1. Homework
- Exercise 1.1.12, Exercise 1.3.2, and Exercise 1.3.7.
Week 27.3.-31.3.2023
Chapter 1. Reading
- Sections 1.3. graphic sequences including Havel-Hakimi Theorem 1.3.31 and the construction of graphs with a given degree sequence. Next we started Chapter 2. The concept of trees, Lemma 2.1.3 and Theorem 2.1.4 with the main proof ideas.
Chapter 1. Homework
- 1. demonstrate whether the following 4 sequences are graphic sequences: (8,6,6,5,4,3,3,3,2), (8,6,6,5,5,3,3,2,2), (8,6,6,6,4,3,3,2,2), (8,6,6,6,5,3,2,2,2).
- 2. represent the order of a tree as a function of its average degree.
- 3. at least how many cycles are there in a graph of order n and size m? prove it.
Week 3.-6.4.2023
Chapter 2. Reading
- Section 2.1.: Corollary 2.1.5. with proof ideas; Definition of distance, eccentricity and graph radius, center of a graph and spanning trees, Theorem 2.1.11.
- Section 2.2.: Cayley's formula, the concept of graph decomposition and graceful labeling. Caterpillars.
Chapter 1. Homework
- 1. If a simple graph has diameter at least 4, can its complement have diameter bigger than 2? prove it.
- 2. Cayley's formula counts the number of spanning trees in K_n, the complete graph. How many spanning trees are there in the graph formed by deleting 1 edge from K:n, denoted by K_n-e? prove it.
- 3. If a Eulerian graph G has a graceful labelling, show that its size is congruent to 0 or 3 modulo 4. Hint: Try to sum the labels in a grace labelling, and think whether it is even or odd.
Week 11.-14.4.2023
No class due schedule change.
Week 17.4.-21.4.2023
Chapter 2. Reading
- Section 2.3. up to page 100.
- Section 3.1. up to page 110.
Chapter 2. Homework
- show that the radius and diameter of a graph satisfy: rad(G) <= diam(G) <= 2*rad(G).
- use Prim's algorithm to find a minimum spanning tree in the following weighted graph, represented as a matrix: (each entry \infty means there is no edge between the two vertices, 0 only between the same vertex)
0, \infty, 3, \infty, \infty; \infty, 0, 10, 4, \infty; 3, 10, 0, 2, 6; \infty, 4, 2, 0, 1; \infty, \infty, 6, 1, 0.
- use Kruskal's algorithm to find a minimum spanning tree in the following weighted graph:
0, 28, \infty, \infty, \infty, 1, \infty; 28, 0, 16, \infty, \infty, \infty, 14; \infty, 16, 0, 12, \infty, \infty, \infty; \infty, \infty, 12, 0, 22, \infty, 18; \infty, \infty, \infty, 22, 0, 25, 24; 1, \infty, \infty, \infty, 25, 0, \infty; \infty, 14, \infty, 18, 24, \infty, 0.
Please show the procedures clearly rather than simply give a solution.
Week 24.4.-28.4.2023
Chapter 3. Reading
- Section 3.1. M-alternating and M-augmenting paths, Berges Theorem 3.1.10, Halls condition 3.1.11 and its Corollary 3.1.13 up to page 111.
- Section 3.3. 1-factors and matchings, Tutte's Theorem 3.3.3 up to page 138.
Chapter 2. Homework
- Can a tree have 2 different perfect matchings? Prove it.
- Give an example of a 3-regular graph with a 1-factor and with a cut-vertex. Can it be decomposed into 1-factors?
- Use Dijkstra's algorithm to compute the distance (cheapest weight of travel) between the vertices in the following weighted graph, represented in a matrix: (\infty means no edge between the 2 vertices, 0 only between the same vertex),/li>
0, 10, 20, \infty, 17; 7, 0, 5, 22, 33; 14, 13, 0, 15, 27; 30, \infty, 17, 0, 10; \infty, 15, 12, 8, 0.
Week 2.5.-5.5.2023
Chapter 4. Reading
- Section 4.1. up to page 156. Vertex cut, edge cut, Theorem 4.1.9., Theorem 4.1.11. Blocks and the block-cutpoint graph.
- Section 4.2. up to page 163. Internally disjoint paths, Theorem 4.2.2. Theorem 4.2.17.
Chapter 2. Homework
- for each k, construct a k-connected graph having k+1 vertices that do not lie on a cycle.
- is there a simple graph G with maximum degree at most 3, such that its vertex connectivity and edge connectivity differ?
- two people play a game on a graph G, alternately choosing distinct vertices. Player 1 starts by choosing any vertex. Each subsequent choice must be adjacent to the preceding choice of the other player, thus together they follow a path. The last player able to move wins. Prove that the second player has a winning strategy if G has a perfect matching, and otherwise the first player has a winning strategy. (hint: when G has no perfect matching, consider a maximum matching.)
- Besides, in Homework 6, the last question concerning Dijkstra's algorithm was probably too complicated and not made clear enough. If you did not provide a completely correct solution, do it again in Homework 7 and you will get the point nevertheless. The question asked you to give a 5x5 matrix representing the shortest path from any vertex i to any vertex j. Today I will briefly talk about the direct graphs for better understanding the situation. In the discussion today, we shall also cover some exercises about connectivity.
Week 9.5.-12.5.2023
Chapter 4. Reading
- Section 5.1. k-coloring, proper coloring, k-chromatic graph, clique number, Theorem 5.17. Greedy algorithms for coloring. Brooks Theorem 5.1.22.
- Section 5.2. Mycielski construction.
Exam (80 points)
The exam will take place in the examining period. Registering is magaged through Edison. The exam will follow standing epidemiological regulations.
The exam has a written part and oral examination. The written part contains 6 problem to solve 10 points each. The expected required time is 60 minutes. Extension of the time is possible. For the written part you can use your notes and the textbook by D.B. West, since you do not need to remember the number of theorems. However, no computer, no phone and no communication is allowed. The solutions are not in the textbook. You are required to solve the problems by yourself.
A sample exam can include the following problems:
- Ex 1.3.8.
- Ex 2.1.2.
- Ex 3.1.8.
- Ex 4.1.7.
- Ex 5.1.13.
- Ex 7.1.3.
More problems to pratice before the exam are: Ex 1.2.8., Ex 1.3.2., Ex 1.3.57, Ex 2.2.21, Ex 3.1.2, Ex 3.1.9., Ex 4.1.2, Ex 5.1.3, Ex 5.2.5, Ex 6.1.3, Ex 6.1.6, Ex 6.1.8.
The oral part of the exam has two questions 10 points each. You are required to demonstrate an overview of each of the covered sections.
Suggested reading
- D.B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-014400-2. (available in the University Library)
- P. Kovář, Teorie grafů, (2022). (in Czech)
- pdf for print: short (skriptum_teorie_grafu_tisk.pdf) and extended (skriptum_teorie_grafu_rozsirene_tisk.pdf)
- pdf for electronic use: short (skriptum_teorie_grafu.pdf) and extended (skriptum_teorie_grafu_rozsirene.pdf)
- pdf for eBook readers (bez okrajů): short (skriptum_teorie_grafu_kindle.pdf) and extended (skriptum_teorie_grafu_rozsirene_kindle.pdf)
- J. Matoušek, J. Nešetřil, An Invitation to Discrete Mathematics, 2nd Edition, Oxford University Press (2008), ISBN-10: 0198570422, ISBN-13: 978-0198570424.
- R. Diestel, Graph Theory, online edition (2000), eISBN 978-3-96134-005-7.
Other books might be used, but beware: terminology might differ! (definitions) and at the exams we build on terminology from the lectures.
Animations
For better uderstanding of certain parts.
- to the proof by Cayley
- to the proof of Eulers' Theorem
- example of Eulerian trail construction
- excentricity of vertices
- to the proof of Halls' Theorem
- hypercube construction
- isomorphism of graphs
- to proof of the existence of kings in a tournament
- storing graph structures in a computer
- difference of a diamtric and a longest path in a graph
- walks, trails and paths in a graph
- on the vertex- and edge-connectivity
Office hours
Zastihnete mne nejlépe osobně během konzultačních hodin, případně (po dohodě emailem) on-line přes MS Teams.
Best way to reach me is during my office hours. It is also possible to arrange (ahead via e-mail) an on-line appointment in MS Teams.
| Den | Čas | Místnost |
|---|---|---|
| Čtvrtek/Thursday | 9:00-10:00 | EA536* |
| **Dne 11.4.2024 konzultace nebudou. | Konzultace on-line po předchozí domluvě. | |
Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.
 |
Petr<tečka>Kovar<zavináč>vsb<tečka>cz kancelář EA536, tel. 597 325 972 |
Upraveno: 11.05.2023 |