metric(n)

description

                 
 

	The metric cone describes the set of weightings of the edges
	of a complete graph that satisfy the triangle inequality. 
	The metric polytope adds the additional constraint that 
	the weights of any triangle sum to at most 2.

dim

n(n-1)/2

n_facets

2n(n-1)

references

85, 105, 95, 96, 101, 99

keywords

facet-degenerate, ridge-diameter

facets

$t=0;
for ($i=1; $i< $n; $i++){
    for($j=$i+1; $j<=$n; $j++){
	$edge[$i][$j]=$t;
	$edge[$j][$i]=$t;
	$t++
    }
}


	

for ($i=1; $i< $n-1; $i++){
    for($j=$i+1; $j<$n; $j++){
	for ($k=$j+1; $k<=$n; $k++){
		@bits=( (0) x ($n*($n-1)/2) );
		$bits[$edge[$i][$j]]=1;
		$bits[$edge[$i][$k]]=1;
		$bits[$edge[$j][$k]]=-1;
		row(0,@bits);
		$bits[$edge[$i][$k]]=-1;
		$bits[$edge[$j][$k]]=1;
		row(0,@bits);
		$bits[$edge[$i][$j]]=-1;
		$bits[$edge[$i][$k]]=1;
		row(0,@bits);
		$bits[$edge[$i][$k]]=-1;
		$bits[$edge[$j][$k]]=-1;	
		row(2,@bits);	
	}    
    }
}
	




returnmatrix();