user_guide:tutorials:matching_polytopes

# Differences

This shows you the differences between two versions of the page.

 user_guide:tutorials:matching_polytopes [2019/01/25 09:27]oroehrig ↷ Links adapted because of a move operation user_guide:tutorials:matching_polytopes [2019/02/04 22:55] (current) 2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:matching_polytopes to user_guide:tutorials:matching_polytopes2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:matching_polytopes to user_guide:matching_polytopes2017/07/19 09:14 oroehrig fixed a bug 2017/07/19 09:12 oroehrig added some formatting to enable automated tests2014/01/03 15:45 external edit2010/06/07 20:49 silke 2010/06/07 08:47 silke 2010/06/07 08:43 silke created 2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:matching_polytopes to user_guide:tutorials:matching_polytopes2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:matching_polytopes to user_guide:matching_polytopes2017/07/19 09:14 oroehrig fixed a bug 2017/07/19 09:12 oroehrig added some formatting to enable automated tests2014/01/03 15:45 external edit2010/06/07 20:49 silke 2010/06/07 08:47 silke 2010/06/07 08:43 silke created Line 1: Line 1: - ===== Matching Polytopes ===== + {{page>​.:​latest:​@FILEID@}} - In this tutorial we will use ''​polymake''​ to construct and analyse matching polytopes. - - First we construct a graph, the complete graph on four nodes: - <​code>​ - > $K4=new props::​Graph(4);​ - > - > for (my$i=0; $i<4; ++$i) { - >   for (my $j=$i+1; $j<4; ++$j) { - >     ​$K4->​edge($i,​$j);​ - > } - > } - ​ - - (See also the [[apps_graph|Tutorial on Graphs]] for more on the construction of graphs.) - - Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of ''​polymake''​ does not yet support this, we have to write the function ourselves: - <​code>​ - > sub node_edge_incidences { - > my$g=shift; - > my $A=new Matrix<​Int>​($g->​nodes,​ $g->​edges);​ - > my$k=0; - > for (my $i=0;$i<​$g->​nodes-1;​ ++$i) { - >​ foreach (@{$g->​adjacent_nodes($i)}) { - > if ($_>$i) { - >​ $A->​[$i]->​[$k]=1;​ - >​$A->​[$_]->​[$k]=1;​ - >​ ++$k;​ - > } - > } - > } - > return$A; - > } - ​ - Now we can construct the node-edge-incidence matrix of our graph ''​K4'':​ - <​code>​ - > $A=node_edge_incidences($K4);​ - > print $A; - 1 1 1 0 0 0 - 1 0 0 1 1 0 - 0 1 0 1 0 1 - 0 0 1 0 1 1 - ​ - - With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x<​sub>​e<​html>&​ge;​0 ... - <​code>​ - >$I=new Matrix<​Int>​([[1,​0,​0,​0,​0,​0],​[0,​1,​0,​0,​0,​0],​[0,​0,​1,​0,​0,​0],​[0,​0,​0,​1,​0,​0],​[0,​0,​0,​0,​1,​0],​[0,​0,​0,​0,​0,​1]]);​ - > $Block1=new Matrix<​Int>​((new Vector<​Int>​([0,​0,​0,​0,​0,​0])) |$I); - ​ - - ... and a lower part for the constraints <​html>&​Sigma;<​sub>​e​ x<​sub>​e<​html>&​le;​1 for each vertex v<​html>&​isin;​V,​ where the sum is over all edges e containing v: - - <​code>​ - > $Block2=new Matrix<​Int>​((new Vector<​Int>​([1,​1,​1,​1])) | (-$A)); - ​ - - Now we can put both parts together and define the polytope: - <​code>​ - > $Ineqs=new Matrix<​Rational>​($Block1 / $Block2); - >$P=new Polytope<​Rational>​(INEQUALITIES=>​$Ineqs);​ - ​ - - The matching polytope of ''​K4''​ is the integer hull of ''​P'':​ - <​code>​ - >$P_I=new Polytope<​Rational>​(POINTS=>​$P->​LATTICE_POINTS);​ - ​ - - We can analyse some elementary properties of ''​P_I''​ ... - <​code>​ - > print$P_I->​POINTS;​ - 1 0 0 0 0 0 0 - 1 0 0 0 0 0 1 - 1 0 0 0 0 1 0 - 1 0 0 0 1 0 0 - 1 0 0 1 0 0 0 - 1 0 0 1 1 0 0 - 1 0 1 0 0 0 0 - 1 0 1 0 0 1 0 - 1 1 0 0 0 0 0 - 1 1 0 0 0 0 1 - - > print $P_I->​FACETS;​ - 0 0 0 0 0 0 1 - 0 1 0 0 0 0 0 - 1 0 0 0 -1 -1 -1 - 1 -1 0 0 -1 -1 0 - 1 0 -1 0 -1 0 -1 - 1 -1 -1 0 -1 0 0 - 1 0 0 -1 0 -1 -1 - 1 -1 0 -1 0 -1 0 - 1 0 -1 -1 0 0 -1 - 1 -1 -1 -1 0 0 0 - 0 0 0 0 0 1 0 - 0 0 1 0 0 0 0 - 0 0 0 0 1 0 0 - 0 0 0 1 0 0 0 - - > print$P_I->​N_FACETS;​ - 14 - ​ - - ... and compare them with the according properties of the defining polytope ''​P'':​ - <​code>​ - > print $P->​VERTICES;​ - 1 0 0 0 1 0 0 - 1 0 1 0 0 0 0 - 1 1/2 1/2 0 1/2 0 0 - 1 0 0 0 0 0 0 - 1 1 0 0 0 0 0 - 1 1/2 0 1/2 0 1/2 0 - 1 0 1/2 1/2 0 0 1/2 - 1 0 0 0 1/2 1/2 1/2 - 1 0 0 0 0 1 0 - 1 0 0 1 0 0 0 - 1 0 0 0 0 0 1 - 1 1 0 0 0 0 1 - 1 0 1 0 0 1 0 - 1 0 0 1 1 0 0 - - > print$P->​VOLUME;​ - 1/72 - - > print $P_I->​VOLUME;​ - 1/90 - ​ - - Next we analyse the combinatorics of ''​P_I'':​ - {{ user_guide:​ilp:​gale.png?​300|The Gale diagram of ''​facet0''​}} - <​code>​ - > print$P_I->​AMBIENT_DIM,​ " ", $P_I->​DIM;​ - 6 6 - - > print$P_I->​F_VECTOR;​ - 10 39 78 86 51 14 - - > print $P_I->​FACET_SIZES;​ - 8 8 6 6 6 6 6 6 6 6 8 8 8 8 - - >$facet0=facet($P_I,​0);​ - - > print$facet0->​AMBIENT_DIM,​ " ", $facet0->​DIM;​ - 6 5 - - > print rows_labeled($facet0->​VERTICES_IN_FACETS);​ - 0:0 1 2 3 4 5 6 - 1:1 2 4 6 7 - 2:2 4 5 6 7 - 3:1 3 4 6 7 - 4:3 4 5 6 7 - 5:0 2 3 4 5 7 - 6:0 1 2 3 4 7 - 7:0 1 3 5 6 7 - 8:0 1 2 5 6 7 - - > \$facet0->​GALE;​ - ​ - The Gale diagram of ''​facet0''​ is depicted on the right.
• user_guide/tutorials/matching_polytopes.txt