Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
user_guide:tutorials:matching_polytopes [2019/01/25 09:38] – ↷ Page moved from user_guide:matching_polytopes to user_guide:tutorials: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> |
- | In this tutorial we will use '' | ||
- | |||
- | First we construct a graph, the complete graph on four nodes: | ||
- | < | ||
- | > $K4=new props:: | ||
- | > | ||
- | > for (my $i=0; $i<4; ++$i) { | ||
- | > for (my $j=$i+1; $j<4; ++$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 '' | ||
- | < | ||
- | > sub node_edge_incidences { | ||
- | > my $g=shift; | ||
- | > my $A=new Matrix< | ||
- | > my $k=0; | ||
- | > for (my $i=0; $i< | ||
- | > | ||
- | > if ($_>$i) { | ||
- | > | ||
- | > | ||
- | > | ||
- | > } | ||
- | > } | ||
- | > } | ||
- | > return $A; | ||
- | > } | ||
- | </ | ||
- | Now we can construct the node-edge-incidence matrix of our graph '' | ||
- | < | ||
- | > $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< | ||
- | < | ||
- | > $I=new Matrix< | ||
- | > $Block1=new Matrix< | ||
- | </ | ||
- | |||
- | ... and a lower part for the constraints < | ||
- | |||
- | < | ||
- | > $Block2=new Matrix< | ||
- | </ | ||
- | |||
- | Now we can put both parts together and define the polytope: | ||
- | < | ||
- | > $Ineqs=new Matrix< | ||
- | > $P=new Polytope< | ||
- | </ | ||
- | |||
- | The matching polytope of '' | ||
- | < | ||
- | > $P_I=new Polytope< | ||
- | </ | ||
- | |||
- | We can analyse some elementary properties of '' | ||
- | < | ||
- | > print $P_I-> | ||
- | 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-> | ||
- | 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-> | ||
- | 14 | ||
- | </ | ||
- | |||
- | ... and compare them with the according properties of the defining polytope '' | ||
- | < | ||
- | > print $P-> | ||
- | 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-> | ||
- | 1/72 | ||
- | |||
- | > print $P_I-> | ||
- | 1/90 | ||
- | </ | ||
- | |||
- | Next we analyse the combinatorics of '' | ||
- | {{ user_guide: | ||
- | < | ||
- | > print $P_I-> | ||
- | 6 6 | ||
- | |||
- | > print $P_I-> | ||
- | 10 39 78 86 51 14 | ||
- | |||
- | > print $P_I-> | ||
- | 8 8 6 6 6 6 6 6 6 6 8 8 8 8 | ||
- | |||
- | > $facet0=facet($P_I, | ||
- | |||
- | > print $facet0-> | ||
- | 6 5 | ||
- | |||
- | > print rows_labeled($facet0-> | ||
- | 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-> | ||
- | </ | ||
- | The Gale diagram of '' |