k-means type clustering

Hi

I have a more difficult problem and I'm not even sure where to start. I have an NxM matrix where m is the number of data sets I have.I want to group them in a "k-means"esque manner such that the differences between all partners are minimized, but only such that contiguous data sets are paired. The elligible information is housed in the structure "Neighbors" where the row number x=the data set, meaning [x,1] contains the eligible grouping partners.

How do i go about creating a program such that all collection of pairs will be quantified and the one with the least amount of differences will be returned, but which also takes into account the elligible pairs?

[Image Analyst]

What are the axes if you did a scatterplot of these data? For any single given data set - one column - how many clusters are in it? One? Two? And the next column over, would its data lie in the same clusters as the first column? Or do they have the own, completely independent and separate cluster(s)?

A diagram or plot would help.