色塗り問題について、新たな質問です。よろしくお願いします。

質問

これまでに質問に答えていただいた皆様、また、拙い質問の投稿の不備をご指摘していただいた皆様ありがとうございました。今回、更に課題が出てどうすればいいのか困っています。
それは、ノード間の通信量を計る、というものなのですが、前回のもふくめて問題を書きます。
http://oshiete1.goo.ne.jp/kotaeru.php3?q=1962022にあるmoritan2さんに頂いた回答の「n個目までのノードの色がa[]に入っている時、そこまでリンクのあるノードに同じものがないかをチェックする関数、違反がなければ true、あれば false、n < 2 の時は常に true」というものも併せて教えていただけると幸いです。
「色塗り問題」
＜条件＞
ノード数　６　V={X1、X2、X3、X4、X5、X6}
色数　3
接続｛(X1,X2)、(X2,X3)、(X3,X4)、(X4,X5)、(X5,X6)、(X6,X1)、(X2,X5)}
制約　接続がつながっているノード同士は同じ色になってはいけない。
更に、隣のノードと通信をして、制約に違反していなければそのまま配色、違反していればその旨を元のノードに伝え、色の変更を要求する、という機能を追加しなければならなくなりました。
この、通信量を測れるようにするには、どのようなコードを書けばよいのでしょうか？教えてください。よろしくお願いします。

回答No.2

moritan2

#include <stdio.h>

#define MAX_NODE 6

typedef struct {
int n1;
int n2;
} LINK;

int color[MAX_NODE]; // ノードの色が入る配列
int n_comm; // 通信回数

LINK link[] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 5}, {1, 4}};
int n_link = 7;

bool check_link(int n)
{
int i;

for(i = 0; i < n_link; i++) {
int n1, n2;

n1 = link[i].n1;
n2 = link[i].n2;
if(n2 == n - 1) {
n_comm++;
if(color[n1] == color[n2]) {
return false;
}
}
}
return true;
}

bool aaa(int n)
{
int i;

if(check_link(n) == false) {
return false;
}
if(n >= MAX_NODE) {
return true;
}

for(i = 0; i < 3; i++) {
color[n] = i;
if(aaa(n + 1) == true) {
return true;
}
}
return false;
}

int main()
{
int ans;
int i;

ans = aaa(0);
if(ans == true) {
printf("n_comm=%d\n", n_comm);
for(i = 0; i < MAX_NODE; i++) {
printf("%d, ", color[i]);
}
printf("\n");
}
return 0;
}

補足

祖母が倒れ、入院しており、お返事が遅れてしまいすみませんでした。このプログラムをビルドしてみましたが、警告で、

「61行目、’==’：演算中の’int’型と’const bool’型の混用は安全ではありません。」

とでましたが、これはそのまま実行していいのでしょうか？何か修正点があれが教えてください。宜しくお願いします。

回答No.1

moritan2

リンクの判定はリンクの情報がどのように与えられるのか仕様を明らかにしてもらわないと答えようがないと思うのですが、、、

その次の問題に関しても、どうも要求仕様がはっきりしません。元のノードというのが意味がはっきりしません。

また、３色でできないときはどうするのか？　平面の地図でもすこし複雑になると３色では足りず４色が必要なんですけど。４色なら平面の地図なら必ず塗り分け可能らしいですけど。この証明が、昔からある有名な難問で４色問題といいます。近年になってコンピュータを使った証明がされたらしいですけど。

補足

moritan2さん、度々回答いただきありがとうございます。

僕が解きたい問題の基本形が下の図のようモノなんです。
○－○－○
｜　｜　｜　　
○－○－○　
＜ノードの割り当ては上段左からX1、X2、X3、下段右からX4、X5、X6となっていて、線でつながっているノード同士は同じ色になってはいけない＞
という設定なんです。
通信は、例えば、X1が、自分が「赤」(三色問題として、色は赤、青、緑とします。)ということをX2にしらせ、X2は自分がなれる色(この場合、青と緑が可能)になります。
しかし、X2が、自身に割り当てられる色がなかった場合、X1にその旨を通知し、X1への色の変更を要求します。そしてまた、X2へ自分の色を通知するというわけです。

基本形は、ノード数６、リンク数７、色数３でしたが、特にノード数とリンク数を自分で設定できるようにして、その際の通信量をはかりたいというわけです。

これで、補足要求の答えになりましたでしょうか？
もし足りない部分があったらまたお願いします。