グラフを縮小させたい

[DAI]

学校の課題で、ある重み付きグラフ(頂点と辺がある方です)の縮小グラフの作り方を考えています。
重みというのは、辺の長さみたいなものです。

具体的に言うと、まず、元のグラフの情報として、
#define N 6
#define M 9999
G[N+1][N+1]={{0,0,0,0,0,0,0},
{0,0,4,M,3,M,2},
{0,4,0,3,M,2,M},
{0,M,3,0,2,M,4},
{0,3,M,2,0,4,M},
{0,M,2,M,4,0,3},
{0,2,M,4,M,3,0}};
を与えます。これはN=6頂点のグラフの隣接行列という情報です。

例えばG[2][1]が4というのは頂点②と頂点①の間に重み4の辺があるよ、という意味です。
G[3][1]がMというのは③と①の間は無限距離=辺が無い、という意味です。
同じ頂点同士に辺は置けないので、0としています。
なので、必然的にG[A]とG[A]は同じ要素になります。

このとき、このグラフの頂点たちをグループ分けして、そのグループをひとつの頂点として考えて、
新たにその頂点同士のグラフを作る、ということ考えています。

例えば、Group1(G1)を頂点①②、G2を頂点③④、G3を頂点⑤⑥というふうに3グループに分割します。
グループ分けした後、どのようにそのグループ同士を辺で繋ぐかというと、グループ間の中にある辺の中
で重みが一番小さいものを1本採択します。辺が1本も無ければ、グループ間の辺ももちろん作りません。

G1とG2を例にすると、まず元のグラフのG[1][2]とG[1][3]とG[2][3]とG[2][4]の要素を取り出して、
その中で一番小さい要素を、G1とG2の間にある辺の情報とします。
これを同様にG2とG3、G3とG1に対しても行います。
そして、新たなG1G2G3に対する以下の隣接行列G'を得ます。

G'[3+1][3+1]={{0,0,0,0},
{0,0,3,2},
{0,3,0,4},
{0,2,4,0}};


ここまでが作りたいプログラムの概要です。

このような規模の小さいグラフで、分割の情報も単純であれば、私でもプログラムすることはできるのですが、
できたらどんな頂点数でもどんな分割の仕方でも対応できる汎用性のあるプログラムにしたいのです。
一番悩んでいるのは、どのように頂点の分割を入力情報として与えたら良いのかというところです。

ややこしい話ですみませんが、よろしくお願いします。
ちなみに環境はVista/VisualC++です。

[non]

No25941のVARIOさんの課題の次の課題なのでしょうか？
同じ、大学の課題なのでしょうか？

さて、ぱっと読んだ感じでは、特に難しくないとは思ったのですが、読み違いもあるかも。
学校の課題なら、もっと条件をはっきりして欲しいなという気がしました。

１　グループの最大数は？
　例えば、何か定数で与えられているのか。
２　グループの中の頂点数は？
　すべてのグループ同じかまたは異なるのか。また、どのような形（変数）で与えられるのか？
３　新たな配列Gは動的に用意するのか？

[DAI]

すみません、同一人物です＾＾；
説明が足りなくてすみませんでした。

まず、前提として頂点のグループ分けの情報は、予め自分で入力します。
上の例で言うと、元のグラフの隣接行列Gと、この頂点をグループにしたいという
G1={①②}、G2={③④}、G3={⑤⑥}の情報は自分で用意します。これに準じて
新しいグラフG'を作りたいのです。

１、グループの最大数は元のグラフの頂点数です。
なので元のグラフが6頂点ならグループの数は1から6の間の値を取ります。
２、上の例では全て同じにしましたが、グループの中の頂点数は特に制限はありません。
同じ場合もありますし、異なる場合もあります。
３、動的に用意できるのであればそれでもちろん良いのですが、最初にグループ分けの情報と共に
グループの数も定まるので、グループの数を元に配列を静的に用意する形でも構いません。

nonさんいつもありがとうございます。よろしくお願いします。

[non]

前の課題を自力で解けたのなら、グループ情報をプログラムでどのように宣言したかを
C言語で示してください。
>G1={①②}、G2={③④}、G3={⑤⑥}の情報は自分で用意します。

名前を変えるのは規約違反です。

[DAI]

前の課題は、解けたというより理論の方を勘違いしていたので、解決としてしまいました。
お手数おかけしますが、グループ情報もどのように宣言したら良いのかも含めて御助言願いたいです。
よろしくお願いします。

[non]

どのようにデータを持つか。の、一例です。

#include <stdio.h>
#define N 6 
#define M 9999
#define Gp 3

G[N+1][N+1]={	{0,0,0,0,0,0,0}, 
		{0,0,4,M,3,M,2}, 
		{0,4,0,3,M,2,M}, 
		{0,M,3,0,2,M,4}, 
		{0,3,M,2,0,4,M}, 
		{0,M,2,M,4,0,3}, 
		{0,2,M,4,M,3,0}};
GRP[Gp][N]= {	{1,2,0,0,0,0},
		{3,4,0,0,0,0},
		{5,6,0,0,0,0}};
newG[Gp+1][Gp+1]={0};

void dispNet(void)
{
	int i,j;
	for(i=0;i<Gp+1;i++){
		for(j=0;j<Gp+1;j++)
			printf("%d ",newG[j]);
		printf("\n");
	}
}
int foundNet(int grp1,int grp2)
{
	int min=M+1;
	int i,j;
	for(i=0;GRP[grp1]!=0;i++){
		for(j=0;GRP[grp2][j]!=0;j++){
			if(G[GRP[grp1]][GRP[grp2][j]]!=0)
				if(G[GRP[grp1]][GRP[grp2][j]]<min)
					min=G[GRP[grp1]][GRP[grp2][j]];
		}
	}
	if(min==M+1)
		return 0;
	return min;
}
int main(void)
{
	int i,j;
	for(i=0;i<Gp-1;i++)
		for(j=i+1;j<Gp;j++)
			newG[i+1][j+1]=newG[j+1][i+1]=foundNet(i,j);
	dispNet();
	return 0;
}

[DAI]

返事が遅くなり申し訳ありません。
nonさん、ありがとうございました。
おかげさまで何とかなりそうです。
本当に、ありがとうございます。