Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revisionBoth sides next revision | ||
tutorial:matching_polytopes [2014/01/03 15:45] – external edit 127.0.0.1 | user_guide:matching_polytopes [2019/01/25 09:27] – ↷ Page moved from tutorial:matching_polytopes to user_guide:matching_polytopes oroehrig | ||
---|---|---|---|
Line 5: | Line 5: | ||
First we construct a graph, the complete graph on four nodes: | First we construct a graph, the complete graph on four nodes: | ||
< | < | ||
- | $K4=new props:: | + | > $K4=new props:: |
- | + | > | |
- | for ($i=0; $i<4; ++$i) { | + | > for (my $i=0; $i<4; ++$i) { |
- | for ($j=$i+1; $j<4; ++$j) { | + | > for (my $j=$i+1; $j<4; ++$j) { |
- | $K4-> | + | > $K4-> |
- | } | + | > } |
- | } | + | > } |
</ | </ | ||
Line 18: | Line 18: | ||
Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of '' | Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of '' | ||
< | < | ||
- | sub node_edge_incidences { | + | > sub node_edge_incidences { |
- | my $g=shift; | + | > my $g=shift; |
- | my $A=new Matrix< | + | > my $A=new Matrix< |
- | my $k=0; | + | > my $k=0; |
- | for (my $i=0; $i< | + | > for (my $i=0; $i< |
- | foreach (@{$g-> | + | > foreach (@{$g-> |
- | if ($_>$i) { | + | > if ($_>$i) { |
- | $A-> | + | > $A-> |
- | $A-> | + | > $A-> |
- | ++$k; | + | > ++$k; |
- | } | + | > } |
- | } | + | > } |
- | } | + | > } |
- | return $A; | + | > return $A; |
- | } | + | > } |
</ | </ | ||
Now we can construct the node-edge-incidence matrix of our graph '' | Now we can construct the node-edge-incidence matrix of our graph '' | ||
< | < | ||
- | $A=node_edge_incidences($K4); | + | > $A=node_edge_incidences($K4); |
- | + | > print $A; | |
- | print $A; | + | |
1 1 1 0 0 0 | 1 1 1 0 0 0 | ||
1 0 0 1 1 0 | 1 0 0 1 1 0 | ||
Line 47: | Line 46: | ||
With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x< | With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x< | ||
< | < | ||
- | $I=new Matrix< | + | > $I=new Matrix< |
- | + | > $Block1=new Matrix< | |
- | $Block1=new Matrix< | + | |
</ | </ | ||
Line 55: | Line 53: | ||
< | < | ||
- | $Block2=new Matrix< | + | > $Block2=new Matrix< |
</ | </ | ||
Now we can put both parts together and define the polytope: | Now we can put both parts together and define the polytope: | ||
< | < | ||
- | $Ineqs=new Matrix< | + | > $Ineqs=new Matrix< |
- | + | > $P=new Polytope< | |
- | $P=new Polytope< | + | |
</ | </ | ||
The matching polytope of '' | The matching polytope of '' | ||
< | < | ||
- | $P_I=new Polytope< | + | > $P_I=new Polytope< |
</ | </ | ||
We can analyse some elementary properties of '' | We can analyse some elementary properties of '' | ||
< | < | ||
- | print $P_I-> | + | > print $P_I-> |
1 0 0 0 0 0 0 | 1 0 0 0 0 0 0 | ||
1 0 0 0 0 0 1 | 1 0 0 0 0 0 1 | ||
Line 84: | Line 81: | ||
1 1 0 0 0 0 1 | 1 1 0 0 0 0 1 | ||
- | print $P_I-> | + | > print $P_I-> |
0 0 0 0 0 0 1 | 0 0 0 0 0 0 1 | ||
0 1 0 0 0 0 0 | 0 1 0 0 0 0 0 | ||
Line 100: | Line 97: | ||
0 0 0 1 0 0 0 | 0 0 0 1 0 0 0 | ||
- | print $P_I-> | + | > print $P_I-> |
14 | 14 | ||
</ | </ | ||
Line 106: | Line 103: | ||
... and compare them with the according properties of the defining polytope '' | ... and compare them with the according properties of the defining polytope '' | ||
< | < | ||
- | print $P-> | + | > print $P-> |
1 0 0 0 1 0 0 | 1 0 0 0 1 0 0 | ||
1 0 1 0 0 0 0 | 1 0 1 0 0 0 0 | ||
Line 122: | Line 119: | ||
1 0 0 1 1 0 0 | 1 0 0 1 1 0 0 | ||
- | print $P-> | + | > print $P-> |
1/72 | 1/72 | ||
- | print $P_I-> | + | > print $P_I-> |
1/90 | 1/90 | ||
</ | </ | ||
Line 132: | Line 129: | ||
{{ : | {{ : | ||
< | < | ||
- | print $P_I-> | + | > print $P_I-> |
6 6 | 6 6 | ||
- | print $P_I-> | + | > print $P_I-> |
10 39 78 86 51 14 | 10 39 78 86 51 14 | ||
- | print $P_I-> | + | > print $P_I-> |
8 8 6 6 6 6 6 6 6 6 8 8 8 8 | 8 8 6 6 6 6 6 6 6 6 8 8 8 8 | ||
- | $facet0=facet($P_I, | + | > $facet0=facet($P_I, |
- | print $facet0-> | + | > print $facet0-> |
6 5 | 6 5 | ||
- | print rows_labeled($facet0-> | + | > print rows_labeled($facet0-> |
0:0 1 2 3 4 5 6 | 0:0 1 2 3 4 5 6 | ||
1:1 2 4 6 7 | 1:1 2 4 6 7 | ||
Line 157: | Line 154: | ||
8:0 1 2 5 6 7 | 8:0 1 2 5 6 7 | ||
- | $facet0-> | + | > $facet0-> |
</ | </ | ||
The Gale diagram of '' | The Gale diagram of '' |