This is an undergraduate Advanced Algorithms class. Stick to the undergraduate topics and only do what is said in the assignment sheet. I will attach an assignment pdf with the question solve those step by step and DONTOT COPY FROM INTERNET SOURCES SUCH AS CHEGG, COURSEHERO. I also have subscription and access to solution on those websites I want a 100% plagiarism free solution. I want the solution to have step by step and clear explanation to each question. I want solutions typed clearly on a document. Donot cut down on explanation.
Assignment 4 no late homework would be accepted 1 (Exercise 26.1-1) Using the definition of a flow, prove that if (u, v) 6∈ E and (v, u) 6∈ E, then f(u, v) = f(v, u) = 0. 2 (Exercise 26.1-9) Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately both the professor’s house and the school are on corners, but beyond that he is not sure if it is going to be possible to send both of his children to the same school. The professor has a map of his own. Show how to formulate the problem of determining if both his children can go to the same school as a maximum-flow problem. 3 (Exercise 26.2-4) Prove that for any pair of vertices u and v and any capacity and flow functions c and f , we have cf (u, v) + cf (v, u) = c(u, v) + c(v, u). 4 (Exercise 26.2-8) Show that a maximum flow in a network G = (V,E) can always be found by a sequence of at most |E| augmenting paths. (Hint: After finding the maximum flow, decompose it into at mos |E| paths with flow equal to maximum capacity on the path.) 5 (Exercise 26.3-5) We say that a bipartite graph G = (L,R,E) is d-regular if every vertex v ∈ L∪R has degree exactly d. Prove that every d-regular bipartite graph has a matching of size |L|. 6 There are n students who studied at a late-night study for final exam. The time has come to order pizzas. Each student has his own list of required toppings (e.g. mushroom, pepperoni, onions, garlic, sausage, etc). Everyone wants to eat at least half a pizza, and the topping of that pizza must be in his reqired list. A pizza may have only one topping. How to compute the minimum number of pizzas to order to make everyone happy? 7 Consider bipartite graph G = (U, V,E). Let H be the collection of all subgraphs H that for every u ∈ U , H has at most one edge incident to u. Let E(H) denote the edge set of H and 1 I = {E(H) | H ∈ H}. Show that (a) (E, I) is a matroid and (b) all matchings in G form an intersection of two matroids. 8 Consider a bipartite graph with nonnegative edge weight. Discribe an augmenting path method to find its maximum-weight matching. 2