Homework 1 november 2, 2018 Deadline and delivery: november 9, 2018, 12:00-14:00 in C403 The homework can be solved by teams of at most two students. For LaTeX written solutions a bonus of 1 point is reserved. Identical or copied solutions will receive no points. The solutions must be written (printed) on papers, signed by its author(s), and physically delivered not by e-mail. Dont write again the texts of the problems! Each problem needs at most 1 2 pages. 1. We consider the street network of a given city. Prove that if we can remove all the cycles in this network by creating at most p blockings (blocking means obstructing one way of a street), then we can remove all the cycles in the city network by reversing one way of at most p streets. (Reversing one way of a given two ways street means to transform it into a one-way-street; reversing an one-way-street means to transform it into the other one-way-street.) (2 points) 2. We consider the following binary operation on graphs: if Gi = (Vi; Ei) (i = 1; 2) are two graphs, then G1 G2 is the following graph V (G1 G2) = V (G1) V (G2) and E(G1 G2) = f(u1; u2)(v1; v2) : u1v1 2 E(G1); u2v2 2 E(G2)g Prove that G1 G2 is connected if and only if G1 and G2 are connected and one of them contains an odd circuit. (2 + 2 = 4 points) 3. Let MG be the transpose of the vertex-edge incidency matrix of a given graph G = (V; E), that is MG = (mij)16i6m 16j6n , where V = fv1; v2; : : : ; vng; E = fe1; e2; : : : ; emg: mij = 1 if 0 otherwise ei is incident with vj (a) Prove that if T is a tree, then by removing from MT a column corresponding to a given vertex we get a quadratic non-singular matrix. (b) Prove that if C is a cycle, then MC is a non-singular matrix if and only if C is odd. (1 + 2 = 3 points) 4. Let G = (V; E) be a digraph, a : E ! R+ be a cost function defined on its arcs, and s; t 2 V such that 2 6 dG(s; t) < 1. We consider the following version of Dijkstras algorithm that starts in the same time from both s and t in order to find a minimum cost path from s to t. for (i 2 V n fsg) do uF i asi; before[i] s; uB k akt; after[k] t; // forward from s and backward from t S fsg; T ftg; U 1; before[s] 0; after[t] 0; while ( min j2V nS uF j + min l2V nT uB l < U) do find j 2 V n S such that uF j = min j2V nS uF j ; S S [ fjg; find l 2 V n T such that uB l = min l2V nT uB l ; for (j 2 V n S) do if (uF j > uF j + ajj) then uF j uF j + ajj; before[j] j; if ((j 2 T) and (uF j + ajj + uB j < U)) then U uF j + ajj + uB j ; i j; if (uF j + uB l > U) then return i; U; T T [ flg; for (l 2 V n T) do if (uB l > all + uB l) then uB l all + uB l; after[l] l; if ((l 2 S) and (uF l + all + uB l < U)) then U uF l + all + uB l; i l; return i; U; (a) Prove that after each iteration in the while loop min j2V nS uF j and min l2V nT uB l cannot decrease. (b) Suppose that we are after the completion of an iteration in the while loop and Pst 2 Pst is a path and j; l 2 V (Pst) such that j all the vertices before it are in S, l and all the vertices after it are in T; j is the last vertex on Pst from S and l is the first vertex on Pst from T; the successor of j is j0 on Pst and the predecessor of l on ; Pst is l0. If j0 6= l and l0 6= j, then a(Pst) > uF j + ajj0 + al0l + uB l > min h2V nS uF h + min k2V nT uB k . (c) Show that s; : : : ; before(i); i; after(i); : : : ; t is a minimum cost path from s to t and its cost is U (i is the vertex returned by the algorithm). (1 + 2 + 2 = 5 points)