2017-09-02

Monge property

平面グラフとは、エッジを交叉させずに平面に描けるグラフのこと
平面グラフの距離行列はMonge propertyという性質を満足する
平面グラフの頂点u,vから、別の頂点x,yへの最短距離を考えるとき d(u,x)+d(v,y)とd(u,y)+d(v,x)とのどちらが小さいかを問題にしたい
今、d(u,x)+d(v,y) <= d(u,y)+d(v,x)となっていたときに、u,vとx,yに、順序を定めて u<=v & x<=yとすることにする
今、u,vは２ノード、x,yも２ノードだったが、これを、平面グラフのノードの部分集合と別の部分集合とにして、n個のノード、m個のノードの部分集合でかんがえたときにも、n個、m個内の順序関係が定まる
この性質がMonge property
この性質が成り立っているとき、巡回セールスマン問題はこの性質の成立を前提としないそれよりも簡単だという
また、Monge propertyの対称正方行列版をSupnick matrixと呼ぶ
planar graphの距離行列にこれがあるらしいのだが、部分集合の取り方の定義のところがまだ良くわかっていない…。任意の部分集合２つを取ってよいわけではないようだ(それを確かめたのが後述のコード)...。planar graphが持つ、あるサイクルとその内部に着目する。サイクルを２エッジで分離して、片方の頂点集合をＡ、もう片方の頂点集合をＢとする。このとき、Ａの要素とＢの要素との間の最短距離関係が長方形行列として得られる。この長方形行列がMonge propertyを持つ。
参考１
参考２
参考３
参考４

library(igraph)

el <- matrix(c(1,2,2,3,1,4,1,7,2,7,2,8,3,8,7,9,7,8,8,9,3,6,9,4,9,5,9,6,8,6,4,5,5,6),byrow=TRUE,ncol=2)
g <- graph.edgelist(el,directed=FALSE)
plot(g)

n.iter <- 100
ret <- rep(0,n.iter)
ret2 <- ret
for(ii in 1:n.iter){
	L <- c(1,2,2,1,3,1,5,1,3,5,3,4,2,4,2,8,2)
	#L <- runif(17)
	d <- distances(g,weights=L)
	d. <- d[c(1,2,3),c(4,5,6)]

	tmp <- c()
	tmp2 <- tmp
	for(i in 1:2){
		for(j in (i+1):3){
			for(k in 1:2){
				for(l in (k+1):3){
					d.. <- d.[c(i,j),c(k,l)]
					tmp <- c(tmp,d..[1,1] + d..[2,2] - (d..[1,2]+d..[2,1]))
					# 行列の要素xをexp(x)にしてその行列式をとると必ず1以下
					tmp2 <- c(tmp2,det(exp(d..)))
				}
			}
		}
	}

	ret[ii] <- (prod(tmp<=0))
	ret2[ii] <- prod(tmp2<=1)
}

plot(ret)
plot(ret2)

AB.0 <- matrix(sample(1:1000,6),ncol=2)
ord <- rbind(c(1,2,3),c(1,3,2),c(2,1,3),c(2,3,1),c(3,1,2),c(3,2,1))
n <- length(ord[,1])

for(k in 1:n){
	for(kk in 1:n){
		AB <- cbind(AB.0[ord[k,],1],AB.0[ord[kk,],2])
		abcd <- matrix(0,0,4)
		val <- c()
		for(i in 1:2){
			for(ii in (i+1):3){
				for(j in 1:2){
					for(jj in (j+1):3){
						tmp <- d.[c(AB[i,1],AB[ii,1]),c(AB[j,2],AB[jj,2])]
						abcd <- rbind(abcd,c(i,ii,j,jj))
						#abcd <- rbind(abcd,c(AB[i,1],AB[ii,1],AB[j,2],AB[jj,2]))
						val <- c(val,tmp[1,1] + tmp[2,2] - (tmp[1,2]+tmp[2,1]))
					}
				}
			}
		}
		print(prod(sign(val)==1))
		if(prod(sign(val)==1)){
			print(val)
		}
	}
}


#cbind(abcd,val)

library(gtools)
n <- 4
vs <- sample(1:1000,n)
pm <- permutations(n,n)

pm2 <- permutations(n,2)
pm2 <- t(apply(pm2,1,sort))


for(i in 1:length(pm[,1])){
	tmp <- d.[vs[pm[i,]],vs[pm[i,]]]
	ret <- c()
	for(j in 1:length(pm2[,1])){
		for(jj in 1:length(pm2[,1])){
			tmp2 <- tmp[pm2[j,],pm2[jj,]]
			tmp3 <- tmp2[1,1] + tmp2[2,2] - (tmp2[1,2]+tmp2[2,1])
			ret <- c(ret,tmp3)
		}
	}
	print(prod(sign(ret)==1))
		if(prod(sign(ret)==1)){
			print(ret)
		}
}