Graafid/Graphs

Aine kood/Code: MTAT.05.080
Õppejõud/Lecturer: Jan Willemson
Praktikumijuhendajad/Tutors: Liina Kamm ja Meelis Kull
Maht/Credits: 4AP/6ECTS
Õppevorm/Study routine: loengud ja praktikumid/lectures and tutorials
Hindamisvorm/Course assessment: eksam/examination
Toimub/takes place in: 2007.-2008. õppeaasta sügissemestril/autumn term
Aeg ja koht/time and place: loeng/lecture R/Fri 12.15-14.00, Liivi 2-405; praktikumid/tutorials E/Mon 14.15-16.00 Liivi 2-403 (Meelis Kull) ja/and N/Thu 12.15-14.00 Liivi 2-206 (Liina Kamm)

Õppekorraldus/How it works

Hinde saamine on eelmistest aastatest jälle veidi erinev. Semestri jooksul toimub 4 kontrolltööd, igaühe eest on võimalik saada 28 punkti; kokku kogutud kuni 112st punktist saadud osa järgi kujuneb siis ka hinne (91-112 punkti "A" jne).

There will be 4 tests during the term, each worth of 28 points. The mark will be determined by the points obtained out of the theoretically possible 112 (91-112 gives "A", 81-90 gives "B", 71-80 gives "C", 61-70 gives "D", 51-60 gives "E" and 0-50 gives "F").

Exam session

During the exam session, the tests may be taken as follows:

Test 1 -- January 17th, 10.15-12.00, Liivi 2-111
Test 2 -- January 17th, 12.15-14.00, Liivi 2-111
Test 3 -- January 18th, 10.15-12.00, Liivi 2-111
Test 4 -- January 18th, 12.15-14.00, Liivi 2-111

Out of the two tries for each test, the maximal amount of points will be counted.

Exam

Here are the problems together with hints and solutions. Here are the results. The table of the results also contains the proposed mark. It is possible to discuss the mark on Thursday, January 24th at 15.15 in Liivi 2-338.

The marking scehmes were as follows.

Test 1

Problem 1:

Drawing/understanding the graph -- 1 point
Proved that the given graphs are not connected -- 3 points
Made the final conclusion -- 3 points

Problem 2:

The idea to use Ore theorem -- 2 points
Made all the necessary computations -- 5 points

Problem 3:

This problem was rather 0/7, most of the students who tried it, got it right

Problem 4:

Found the correct graph -- 2 points
Proved that there are no others -- 5 points

Test 2

Problem 1:

Found the correct maximal flow of value 1 -- 2 points
Found the corresponding minimal cut -- 5 points

Problem 2:

Proved that the minimal weigth spanning tree algorithm produces unique output -- 5 points
Proved that the minimal weigth spanning tree algorithm can in principle output every minimal weigth spanning tree -- 2 points

Problem 3:

The idea to count the sum of degrees -- 1 point
Obtained the correct equation -- 4 points
Solved the equation correctly -- 2 points

Problem 4:

Proved that the deck can not have more that 7 cards -- 4 points
Proved that the trick is possible with 7 cards -- 3 points

Test 3

Problem 1:

Found 13 automorphisms -- 1 point
Found 26 automorphisms -- 2 points
Found 52 automorphisms -- 4 points

Problem 2:

Shown that r(3,5)<=14 -- 3 points
Shown that r(3,5)>13 -- 4 points
Partial credit: shown that r(3,5)<=15 -- 1 point

Problem 3:

Observed that m>=1.5n -- 3 points
Substituted correctly to the Euler formula -- 2 points
Solved the inequality -- 2 points

Problem 4:

Observer that the answer may be either 3 or 4 -- 1 point
Shown that 3 is notpossible -- 6 points

Test 4

Problem 1:

The idea to remove the middle edge -- 1 point
Found the chromatic number of C₆ -- 3 points
Found the chromatic number of the graph obtained by contracting the midle edge -- 3 points
Any other logic that gave the correct answer was given 7 points, any other logic that resulted in some other 6th degree polynomial was given 1 point

Problem 2:

Again, this problem was pretty 0/7. The students who referred to Kuratowsi's or Wagner's theorem and counted the number of edges in K₅ and K_3,3 solved most of the problem.

Problem 3:

The idea to consider the vertex with the maximal degree -- 1 point
Defined and proved a suitable dominating set -- 6 points

Problem 4:

The idea to use Problem 3 -- 1 point
Used Brooks theorem in the setting $\chi(G)\leq\Delta(G)$ -- 3 points
Proved the special case $\Delta(G)=2$ -- points
All the students missed the last 3 points

Problems and solutions of the tests

First test and the results

Marking scheme for Problem 1:

Noting connectedness -- 1 point
Proving that all the presented graphs are Eulerian -- 2 points
Proving that all the presented graphs are Hamiltonian -- 4 points

Marking scheme for Problem 2:

Reduced the problem to proving that kl<=(k+l)^2/4 -- 2 points
Proving the inequality -- 4 points

Dealing with the equality case -- 1 point

Marking scheme for Problem 3 was pretty much 0/7, the correct idea most of the points and unclarity of the presentation reduced some
Marking scheme for Problem 4:

Part (a) -- 2 points
Part (b) -- 5 points

Second test and the results

Marking scheme for Problem 1 (partial credits):

Induction of the type "Add one C atom somewhere to go from n to n+1" -- up to 4 points

Marking scheme for Problem 2:

Drawing/understanding the graph -- 1 point
Finding the correct minimal weight -- 4 points
Finding the number of minimal weight spanning trees -- 2 points

Marking scheme for Problem 3:

Construgting the correct bipartite graph -- 2 points
Finishing the argument with Hall's theorem -- 5 points

Marking scheme for Problem 4 (partial credits):

Exhibiting the maximal flow, but no minimal cut -- 5 points
Finding a flow of value 23 -- 3 points
Finding a flow of value 22 -- 1 point

Third test and the results

Marking scheme for Problem 1:

Drawing/understanding the graph -- 1 point
Reaching 2n automorphisms -- 2 points
Reaching 4n automorphisms -- 4 points

Marking scheme for Problem 2 (partial credits):

Construction of a small example -- 1 point
Presenting a correct algorithm for constructing the coloring -- 3-5 points, depending on the efficiency of the algorithm

Marking scheme for Problem 3 (partial credit):

Proof that r(4,5)<=35 -- 1point

Marking scheme for Problem 4:

Proving that 3n=2m -- 2 points
Proving that 3n=>5f -- 3 points
Completing the proof with Euler formula -- 2 points

Fourth test and the results

Marking scheme for Problem 1:

Drawing/understanding the graph -- 1 point
Proving that R₂ is planar -- 1 point
Proving that R₃ is not planar -- 3 points
Proving that R_n (n>3) is not planar -- 2 points

Marking scheme for Problem 2 (partial credits):

Stating that there are k options to color the first vertex and that these options remain later as well -- 3 points
Referring to the general theorem about the coefficients of the chromatic polynomial -- 0 points

Marking scheme for Problem 3

Correct answer -- 3 points
Proof of the answer -- 4 points

Problem 4 had no specific marking scheme. In order to score any points, the student had to come up with the idea of splitting the faces into "inner" and "outer" ones, and this mostly already meant solving most of the problem.

Loengumaterjalid/Course materials

Loengus kasutame A. Buldase, P. Laua ja J. Willemsoni õpikut ning P. Laua slaide. Õpikust on olemas ka täiendatud ja parandatud versioon, aga see on alles toimetamisel ja võib veel ebatäpsusi sisaldada.

Most of the relevant material (including the proofs) is given on the slides presented during the course. The problems of the tutorials are also translated into English by Meelis Kull.