user_guide:tutorials:matching_polytopes

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
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)
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);​ 
->   } 
-> } 
-</​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>​ 
-> 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>​ 
-> $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</​sub><​html>&​ge;</​html>​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); 
-</​code>​ 
- 
-... and a lower part for the constraints <​html>&​Sigma;</​html><​sub>​e</​sub>​ x<​sub>​e</​sub><​html>&​le;</​html>​1 for each vertex v<​html>&​isin;</​html>​V,​ where the sum is over all edges e containing v: 
- 
-<​code>​ 
-> $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>​ 
-> $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>​ 
-> $P_I=new Polytope<​Rational>​(POINTS=>​$P->​LATTICE_POINTS);​ 
-</​code>​ 
- 
-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 
-</​code>​ 
- 
-... 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 
-</​code>​ 
- 
-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;​ 
-</​code>​ 
-The Gale diagram of ''​facet0''​ is depicted on the right. 
  • user_guide/tutorials/matching_polytopes.txt
  • Last modified: 2019/02/04 22:55
  • (external edit)