Про нас
Кафедри
Дистанційне навчання
Вступнику
Конференції
Наші партнери
Довідка
Підрозділи
Посилання
Програми

Graph Theory

Each Thursday on (16:40 till 19:30) in the room 111 at the Faculty of Applied Mathematics and Informatics (lecturer: Dr. Yuriy Ishchuk)

* * *

 On 17-21 November 2014 there will be an intensive block course "Algorithmic Graph Theory" by Dr. Joachim Spoerhase (University of Würzburg)

 

Block course: In the week 17–21 November 2014, Dr. Joachim Spoerhase will deliver the course "Algorithmic Graph Theory" according to the following schedule (in Room 301 of the main building of the University):

 

09:00-10:30 Lecture

10:30-12:00 Solving Exercises

12:00-12:30 Discussion of solutions

12:30-13:30 Lunch

13:30-15:00 Lecture

15:00-16:00 Solving Exercises

16:00-16:30 Discussion of solutions

 

In 5 days (Mon to Fri) we plan to cover 5x2=10 topics from the following list:

 


 

Program and Slides of the Block Course

0. Graphs: An Introduction

1. Eulerian Walks, Hamiltonian Cycles.   Exercises.

 2. TSP + Flows + Exercises.

 3. Flow Algorithms + Exercises

 4. Matchings  + Exercises

 5. Matchings II + Exercises

 6. Rooted Spanning Trees + Exercises

 7. Randomized Algorithms for Min-Cut + Exercises

 8. Colorings, Cliques, Independent Sets + Exercises

 9. Planar Graphs I (Euler's Formula, Kuratowski) + Exercises

10. Introduction to Fixed-Parameter Tractability + Exercises

 

Exercises ("Übungen" in German) to each lecture can be found here.

Textbook:

S.O. Krumke,  H.Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer, 2009.

 


  

Results of the exam (held on 11 December 2014) can be downloaded here.

The final grade for the course can be calculated by the formula:

Final score = 2x(grades for exam) + (grades for homeworks).

 

According to this formula the following students have got more than 50:

1. Pylypovych M. (2x32+31=95)

2. Spodar N. (2x20+28=68)

3. Kryven M. (2x19+26=64)

4. Parubochyi V. (2x9+33=51)

 

A discussion of the results of the exam is planned on 26 December 2014 in (or near) Room 377 at 13:00. 

  


 

1.      Introducing graphs and algorithmic complexity.  (Introducing graphs. Introducing algorithmic complexity. Dijkstra’s shortest path algorithm. A longest simple path algorithm. Adjacency matrices and adjacency lists. Depth-first searching.)

2.      Spanning-trees, branchings and connectivity. (Optimum weight spanning-trees. Optimum branchings. Enumeration of spanning-trees. Fundamental circuits of a graph. Fundamental cut-sets of a graph. Connectivity.)

3.      Planar graphs. (Basic properties of planar graphs. Genus, crossing-number and thickness Characterisations of planarity. Dual graphs. A planarity testing algorithm.)

4.      Networks and flows. (Networks and flows. Maximising the flow in a network. Menger's theorems and connectivity. A minimum-cost flow algorithm.)

5.      Matchings. (Definitions. Maximum-cardinality matchings.Maximum-weight matchings.)

6.      Eulerian and Hamiltonian tours. (Eulerian paths and circuits. Finding Eulerian circuits. Postman problems. Counting Eulerian circuits. The Chinese postman problem for undirected graphs. The Chinese postman problem for digraphs. Hamiltonian tours. Finding all Hamiltonian tours by matricial products. The travelling salesman problem. 2-factors of a graph.)

7.      Colouring graphs. (Dominating sets, independence and cliques. Edge-colouring. Vertex-colouring. Chromatic polynomials. Face-colourings of embedded graphs.)

  

Textbook:

Alan Gibbons: Algorithmic Graph Theory, Cambridge University Press, 1985.

 

Grades for the Homeworks:

  

NoNameFacultyCh.1Ch.2-7Total
1Kryven M.Appl.Math.17926
2Pylypyvych M.Mathematics112031
3Kasperska L.Mathematics91322
4Spodar N.Appl.Math.101828
5Beshley A.Appl.Math.77
6Parubochyi V.Electronics.161733
7Borachuk I.Appl.Math.
8Skvarko K.Appl.Math.151934
9Hrytsyk Yu.Appl.Math.1414
10Borachuk I.Appl.Math.
11Basiuk Yu.Mathematics
12Pavliv U.Mathematics99
13Zhydyk V.Mathematics71219
14Bereza O.Mathematics81624
15Kinash N.Mathematics1212
16Bokalo I.Mathematics1010
17Kryzhanovskyi V.Electronics.161935
18Duban M.Mathematics66
19Barabash O.Appl.Math.77
20Tytar I.Mathematics88

 

Exercises:

1.1. Draw every connected simple graph with 4 vertices.

1.2. Mark by bold line all edges of spanning trees for graphs constructed in exercise above.

1.3. Count all non-isomorphic graphs with 5 vertices and 4 edges. For one of them write it adjacency matrix and adjacency list with their tabular representation.

1.4. Apply Dijkstra’s algorithm for the weighted graph shown in the figure 1.11 (see [AGT], p.15) and find shortest paths from vertex v3 to any other vertex. Write the table which lists the values of the labels L(v) and set T for each iteration.

1.5. Modify Dijkstra’s algorithms of the figure 1.10 (see [AGT], p.14) using priority queue (see [AGT], Ex. 1.16, p.36) and estimate it complexity.

1.6. Construct matrices W0, W1, W2, W3, W4  for undirected weighted graph shown on page 34, using matrical (Floyd’s) algorithm of the figure 1.14 (see [AGT], p.20).

1.7. Modify the Depth-First Search (DFS) algorithm of the figure 1.15 by implementation of tabular representation of adjacency list, stack which contains traversed vertices and drawing the edges of spanning forest by solid line (the back-edges – by dash line).

1.8. For the graph of the figure 1.16 (a) apply above DFS algorithm and write table which lists DFI(v) and content of stack for each iteration.

1.9. Apply DFS algorithm for the graph of the figure 1.16 (a) with reversed order of vertices  and draw DFS spanning forest.

1.10.        Count the number N4(i,j) of all paths which consist of the 4 edges (from  vertex vi to vertex vj) of the digraph of Fig. 1.11 (see [AGT], p.15). (Instruction: Let u=v5, then N4(I,j)=A4(i,j), where A is the adjacency matrix of digraph.)

1.11.        Apply Breadth-First Search (BFS) algorithm (see [AGT], p.35) for the graph of Fig. 1.16 (a). Write table which lists BFI(v) and content of queue for each iteration.

 

1.12.        Modify the above BFS algorithm to construct a breadth-first spanning forest with reversed order of vertices of the graph shown on Fig. 1.16 (a)

.  

2.1. Given a specific edge e of an undirected graph G, how would you construct a spanning-tree of G which contains e? How can a graph be constructed given the setoff all its spanning-trees?

2.2. Use theorem 2.5 (see, p.53 [AGT]) to derive Cayley’s theorem that the number of spanning-trees of Kn is nn-2.

2.3. Prove that Kruskal’s algorithm finds a minimum-weight spanning-tree and show that it operates in polynomial time.

2.4. Construct a counterexample to show that following ‘algorithm’ does not always construct a maximum branching, MB, of a weighted digraph G=(V,E).
1. Relabel the elements of E so that
               if w(ei)>w(ej) then i>j.
2. MB:= empty set
3. For i=1 to |E| do
               if  w(ei)>0 and MB join {ei} is acyclic then
                               MB:=MB join {ei}.

3.1. Given an arbitrary simple planar graph with n vertices and |E| edges, show that the maximum number of edges, M, that can be added to the graph, subject to it remaining planar is given by
M=3n-|E|-6    (Use Euler’s formula. When no more edges can be added every face of an embedding is triangular. Every simple planar graph is thus a subgraph of such a planar triangulation.)

3.2. Demonstrate that every simple graph with |E|<9 or with n<5 is a planar.

3.3. A self-dual is a simple planar graph which is isomorphic to its dual. Show, using Euler’s formula, that if G is self-dual then  2n=|E|+2. How might a self-dual be constructed for n>3.
(Not every simple planar graph with 2n=|E|+2 is a self-dual.  Take care with vertices of degree 2.)

3.4. The complement c(G) of a graph G=(V,E) with n vertices is given by c(G)=(Kn-E). Show that if n>10, then at least one of G and c(G) is non-planar.)

4.1. A manufacturer has two dispatch points D1 and D2 for his goods which he sends to three market points M1, M2 and M3 across the following network: {(D1,P1), c(D1,P1)=20; (D1,D2), c(D1,D2)=5; (D2,P2), c(D2,P2)=5; (D2,P3), c(D2,P3)=6; (P1,P2), c(P1,P2)=5; (P1,P4), c(P1,P4)=10; (P2,P4), c(P2,P4)=6; (P2,P5), c(P2,P5)=5; (P3,P2), c(P3,P2)=5; (P4,P5), c(P4,P5)=4; (P4,M1), c(P4,M1)=20; (P5,M3), c(P5,M3)=15; (M1,M2), c(M1,M2)=6; (M3,M2), c(M3,M2)=6}, where c(Pi,Pj) is maximum flow of goods which edge (Pi,Pj) can sustain. There is market demand t(M) at each of the market points as follows:  t(M1)=10, t(M2)=8 and t(M3)=8.  Can the network meet the demand? If a factory is sited at D1 and another at D2, determine (non-unique) separate outputs in order to meet the situation. Find all bottleneck-edge relative to network flow and augmenting path. (Modify the network by adding a new source S and new sink (target) M, new edges (S,D1), (S,D2) each with an infinite capacity, edges (M1,M), (M2,M), (M3,M) with capacities 10, 8, 8 correspondently  and maximize the network flow.)

5.1. A multinational army has a tank corps. Each tank requires a crew of two who speak a common language. Each possible crew member generally speaks more than one language.  How might the problem of maximizing the number of crews be reduced to the problem of finding a maximum-cardinality matching for a graph in which each vertex represents a possible crew member?

5.2. (The stable marriages problem.) In a community of n men and n women each person ranks those of the opposite sex according to his or her preference for a marriage partner. The problem is to marry of all members of the community in such a way that the set of marriages is stable. The set is unstable if a man and a women exist who are not married to each other but prefer each other to their actual mates. (Use Gale and Shapley algorithm to solve a problem, see 151p.[AGT].)

6.1. In what graphs is an Eulerian circuit also a Hamiltonian circuit?

6.2. Using the proof of Theorem 6.1 (see [AGT, p.155]) as a basis, carefully describe the details of an algorithm of O(|E|) complexity which finds Eulerian circuit of the digraph G=(V,E), where V={a,b,c,u,v} and E={(a,b); (a,u); (b,c); (b,v); (c,a); (c;b); (u,c); (u;v); (v,a); (v;u)}.                                            

7.1. Show that any graph with n vertices and at least [n2 /4] edges contains a triangle. (Use theorem 7.4. (Túran) p.194 [AGT].)

7.2. In a group of eight people one person knows three others, two know four others, three know five others, while remaining two each know two others. Show that there must be a group of three mutual acquaintances. (Use theorem 7.4. (Túran) p.194 [AGT])

7.3. Prove that in every connected graph there are two disjoint minimal dominating sets. (If V is a vertex-set and X is a minimal dominating set, show that (V-X) is a (not necessarily minimal) dominating set).

7.4. There are 2N contestants in a chess tournament. No contestant plays more than one match in a day and must, in the course of tournament, play every other player. Justify the following scheme to complete the tournament in (2N-1) days. (Properly colour the edges of the complete graph K2N using a minimum number of colours. Let vertices of K2N represent the players. On the i-th day those players connected by edges coloured by i are drawn together.

 

7.5. Show that every planar Hamiltonian graph has a 4-face-colouring. (Any Hamiltonian circuit divides the plane into two regions. Consider using two colours for the faces in either region.)