Question 1: Let G = (V,E) be an undirected graph and s and t be the source and target nodes. Give an efficient algorithm to determine whether the number of minimum s − t cuts in G is at most two. Analyse your algorithm and provide its complexity.
Question 2: Suppose that X is a 2×1 matrix and Y is a 1×2 matrix. Prove that XY is not invertible.
Question 3: Let G = (V,E) be an undirected bipartite graph with parts AandB(V =A∪B,A∩B=∅)andthereisnoedgewithbothendpointsin A or both endpoints in B). Also, let X and Y be two sets of vertices such that X ⊆ A and Y ⊆ B. Suppose that G has two matchings M1 and M2 such that M1 covers all vertices in X and M2 covers all vertices in Y . Prove that G has a matching M such that M covers all vertices in X and Y . (A matching covers a vertex if one of the edges of the matching has that vertex as an endpoint.)
Question 4: Provide a linear program for the following problem:
A factory produces Aluminium plates of a standard width 3meters. But cus- tomers want to buy plates of shorter widths. So, the factory has to cut original 3m plates. One 3m plate can be cut, for instance, into two plates of 93cm width, one plate of width 108cm, and a rest of 6cm (which goes to waste). Suppose that we have the following orders:
• 97 plates of width 135cm • 610 plates of width 108cm
• 395 plates of width 94cm
• 211 plates of width 43cm.
What is the smallest number of 3m plates that have to be cut in order to satisfy this order? how should they be cut? (Hint: there are 12 different ways of cutting a plate into useful subpieces; you’ll need to figure them all out.)