This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ===== Matching Polytopes ===== 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 perl> > $K4=new props::Graph(4); > for (my $i=0; $i<4; ++$i) { > for (my $j=$i+1; $j<4; ++$j) { > $K4->edge($i,$j); > } > } </code> (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 perl> > 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; > } </code> Now we can construct the node-edge-incidence matrix of our graph ''K4'': <code perl> > $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 </code> With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x<sub>e<html></sub><html></html>≥<html></html></html>0 ... <code perl> > $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); </code> ... and a lower part for the constraints <html><html></html>Σ<html></html><sub></html>e</sub> x<sub>e<html></sub><html></html>≤<html></html></html>1 for each vertex v<html><html></html>∈<html></html></html>V, where the sum is over all edges e containing v: <code perl> > $Block2=new Matrix<Int>(new Vector<Int>([1,1,1,1]) | -$A); </code> Now we can put both parts together and define the polytope: <code perl> > $Ineqs=new Matrix<Rational>($Block1 / $Block2); > $P=new Polytope<Rational>(INEQUALITIES=>$Ineqs); </code> The matching polytope of ''K4'' is the integer hull of ''P'': <code perl> > $P_I=new Polytope<Rational>(POINTS=>$P->LATTICE_POINTS); </code> We can analyse some elementary properties of ''P_I'' ... <code perl> > 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 </code> ... and compare them with the according properties of the defining polytope ''P'': <code perl> > 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 </code> Next we analyse the combinatorics of ''P_I'': {{ :tutorial:ilp:gale.png?300|The Gale diagram of ''facet0''}} <code perl> > 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; </code> The Gale diagram of ''facet0'' is depicted on the right. user_guide/tutorials/release/3.4/matching_polytopes.txt Last modified: 2019/04/13 07:36by 127.0.0.1