A) Consider the triangle graph G = (V, E) with 3 nodes and 3 edges and the match
ID: 3141425 • Letter: A
Question
A) Consider the triangle graph G = (V, E) with 3 nodes and 3 edges and the matching polytope P_M = {x Element R^E | sigma_e Element delta (v) x_e lessthanorequalto 1; x_e greaterthanorequalto 0} associated with it. Write it in form P_M = {x Element R^E | Ax lessthanorequalto b} and give the 6 times 3 constraint matrix A. What 3 times 3 submatrix A_I of A has det(A_I) NotElement {- 1, 0, 1} ? What is det(A_I)? Compute A^-1 _1. Which is the extreme point x = A^-1 _I b_I that belongs to this submatrix? b) Which of the following matrices is TU? Argue why or why not! A_1 = (1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0), A_2 = (-1 0 1 0 -1 0 0 0 1 0 1 1 0 1 -1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 -1 0).Explanation / Answer
b) A matrice is Totally unimodular if-
1) its determinant or the submatrix determinant is either 0,1,-1
2) Every column of matrix contains at most two non-zero entries;
3)Every entry in matrix 0, +1, or 1;
4) None of the submatrix should be of the form ( ....1 .....1....)
(.....1.....-1...)
First taking A1
Applying row operation in A1 R2=R2-R3, we get
A1= ( 1 0 1 0 1 )
(0 1 1 0 -1)
(0 0 0 1 1)
( 1 1 0 0 0)
so without solving further we can clearly see in row 1 and 2 that there is a submatrix whose determinant is -2 i,e (1 1)
(1 -1)
Hence A1 is not a TU Matrice
Now looking at A2
if we apply the row operation R3=R3-R1
we will get the result but none of the submatrix will give determinant other than 0,1,-1
Hence A2 is a TU Matrice.
We checked that all the conditions mentioned above are fulfilled.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.