(Solved): Homework For Graph Algorithms

Homework 2 - november 12, 2021 Deadline: 07:00 am, november 19, 2021, by e-mail delivery - The homework can be solved by teams of at most two students. - LaTeX (correctly) written solutions will receive a bonus of 2 points. - Don’t write again the texts of the problems! Each problem needs at most 1 or 1 and a half pages. - ANY COPIED SOLUTION FOR A PROBLEM FROM BELOW WILL RECEIVE −2 POINTS. - The solutions will be delivered by e-mail until 07:00 am, november 19, 2021, at one of the following addresses: olariu@info.uaic.ro, fe.olariu@gmail.com - The e-mail must contain the source (a .doc, .odt or .tex file) and the .pdf file, both with the following name format: Name1 group Name2 group Homework1.tex (or .doc, .odt) Name1 group Name2 group Homework1.pdf - Examples: IonescuPVasile A8 VasilescuTIon X1 Homework1.tex (or .doc, .odt, .pdf) IonescuPVasile B6 VasilescuTIon E5 Homework1.tex (or .doc, .odt, .pdf) 1. You are given a set of cities, along with the pattern of highways between them, in the form of an undirected graph G = (V,E). Each stretch of highway e ∈ E connects two of the cities, and you know its length, ce. You want to get from city s to city t (s, t ∈ V , s 6= t). There’s one problem: your car can only hold enough gas to cover L km. There are gas stations in each city, but not between cities. a) Show how to determine in O(|V |+ |E|) time complexity whether there is a feasible route from s to t (a route you can ride using your car). b) You are now planning to buy a new car, and you want to know the optimum (hence minimum) distance you can ride with a full fuel tank in order to travel from s to t given the circumstances. Give an efficient algorithm to determine this. (2 + 2 = 4 points) 2. Let G = (V,E) be a connected graph and c : E → R an injective cost function defined on its edges. For a spanning tree T of G and u, v ∈ V we denote by ET (u, v) the set of edges of the unique path from u to v in T ; an edge uv ∈ E is called T -red if there exists an edge xy ∈ ET (u, v) such that c(uv) < c(xy). (a) Let T be a spanning tree of G such that there exists a T -red edge in G. Prove that T is not of minimum cost. (b) Let T be a spanning tree of G such that there is no T -red edge in G. Let T ′ be another spanning tree of G (T 6= T ′). Then there exists a sequence of spanning trees T = T1, T2, . . . , Tk = T ′ such that Ti+1 = Ti− ei + e′i, where ei ∈ E(Ti) and e′i ∈ E(T ′), and c(Ti+1) > c(Ti), for all 1 6 i < k. (c) Let T be a spanning tree of G. Prove that T is a minimum cost spanning tree of G if and only if there is no T -red edge in G. (d) Using the above results prove that G contains only one minimum cost spanning tree. (1 + 3 + 1 + 1 = 6 points) 3. Let G = (V,E) be a graph and H a subgraph of G. A H-chain in G is a cycle or a path of non- zero length of G, P , which intersects H only in its endpoints (if P is a cycle, then |V (P )∩V (H)| = 1, otherwise |V (P ) ∩ V (H)| = 2). A c-decomposition of G is a sequence of graphs, G1, G2, . . . , Gp (p > 1) such that (i) G1 is a cycle and Gp = G; (ii) for each 1 6 i < p, there exists a Gi-chain in Gi+1, Pi, such that V (Gi+1) = V (Gi) ∪ V (Pi) and E(Gi+1) = E(Gi) ∪ E(Pi). (a) Prove that G (|G| > 3) is 2-edge-connected if and only if there exists a c-decomposition of G. * Consider now the following algorithm: for (v ∈ V ) label[v]← −1; parent[v]← 0; E [v]← ∅; // E[v] (a queue) will contain backward edges starting in v. k ← 0; S.push(s); label[s]← 0; // S is a stack containing s. for(i = 1, n) vertex[i]← 0; vertex[1]← s; while(S 6= ∅){ u← S.top(); if(v ← A[u].next 6= null) if(label[v] < 0) k + +; S.push(v); parent[v]← u; label[v]← k; vertex[k]← v; else E [v].push(vu); else S.delete(u); } for(v ∈ V ) visited[v]← 0; i← 0; for(k = 1, n) { x← vertex[k]; if(visited[x] = 0) { visited[x]← 1; while(E [x] 6= ∅) { xy ← E [x].pop(); i + +; Pi ← {xy}; while(visited[y] = 0) Pi ← Pi ∪ {parent[y]y}; y ← parent[y]; visited[y]← 1; } } } (b) For a 2-edge-connected graph G = (V,E) prove that the algorithm builds a c-decomposition of G. What is its time complexity? (c) Show how to modify this algorithm in order to decide if its input, the graph G = (V,E), is 2-edge-connected. (3 + 2 + 1 = 6 points)

Homework For Graph Algorithms

Related Study Services

Post your Answer - free or at a fee

Answer Review

Homework For Graph Algorithms

Related Study Services

Post your Answer - free or at a fee

Login to your tutor account to post an answer