Differences

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

--- user_guide:matching_polytopes [2019/01/25 09:27] – ↷ Page moved from tutorial:matching_polytopes to user_guide:matching_polytopes oroehrig
+++ user_guide:tutorials:matching_polytopes [2019/02/04 22:55] (current) – external edit 127.0.0.1
@@ 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 0 0 0
-0 0 1 1 0
-1 0 1 0 1
-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;
-0 0 0 0 0 0
-0 0 0 0 0 1
-0 0 0 0 1 0
-0 0 0 1 0 0
-0 0 1 0 0 0
-0 0 1 1 0 0
-0 1 0 0 0 0
-0 1 0 0 1 0
-1 0 0 0 0 0
-1 0 0 0 0 1
-> print $P_I->FACETS;
-0 0 0 0 0 1
-1 0 0 0 0 0
-0 0 0 -1 -1 -1
--1 0 0 -1 -1 0
-0 -1 0 -1 0 -1
--1 -1 0 -1 0 0
-0 0 -1 0 -1 -1
--1 0 -1 0 -1 0
-0 -1 -1 0 0 -1
--1 -1 -1 0 0 0
-0 0 0 0 1 0
-0 1 0 0 0 0
-0 0 0 1 0 0
-0 0 1 0 0 0
-> print $P_I->N_FACETS;
-</code>
-... and compare them with the according properties of the defining polytope ''P'':
-<code>
-> print $P->VERTICES;
-0 0 0 1 0 0
-0 1 0 0 0 0
-1/2 1/2 0 1/2 0 0
-0 0 0 0 0 0
-1 0 0 0 0 0
-1/2 0 1/2 0 1/2 0
-0 1/2 1/2 0 0 1/2
-0 0 0 1/2 1/2 1/2
-0 0 0 0 1 0
-0 0 1 0 0 0
-0 0 0 0 0 1
-1 0 0 0 0 1
-0 1 0 0 1 0
-0 0 1 1 0 0
-> print $P->VOLUME;
-/72
-> print $P_I->VOLUME;
-/90
-</code>
-Next we analyse the combinatorics of ''P_I'':
-{{ :tutorial:ilp:gale.png?300|The Gale diagram of ''facet0''}}
-<code>
-> print $P_I->AMBIENT_DIM, " ", $P_I->DIM;
-6
-> print $P_I->F_VECTOR;
-39 78 86 51 14
-> print $P_I->FACET_SIZES;
-8 6 6 6 6 6 6 6 6 8 8 8 8
-> $facet0=facet($P_I,0);
-> print $facet0->AMBIENT_DIM, " ", $facet0->DIM;
-5
-> print rows_labeled($facet0->VERTICES_IN_FACETS);
-:0 1 2 3 4 5 6
-:1 2 4 6 7
-:2 4 5 6 7
-:1 3 4 6 7
-:3 4 5 6 7
-:0 2 3 4 5 7
-:0 1 2 3 4 7
-:0 1 3 5 6 7
-:0 1 2 5 6 7
-> $facet0->GALE;
-</code>
-The Gale diagram of ''facet0'' is depicted on the right.