グラフの色分けを行うCのソースについて教えてください。


http://www.cs.sunysb.edu/~algorith/implement/trick/distrib/trick.c

このプログラムを利用して地図の色分けができないかと考えいますが、グラフ理論が判っていないため、とっかかりが掴めずに困っています。

そこで2点教えてください。
1.以下の入力形式は何を意味するのでしょうか?
4 4
1 2
2 3
3 4
1 4


2.プログラムフローの概略

URLはダミーでも結構です。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:
  • 終了:--
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

回答1件)

id:cyano No.1

回答回数126ベストアンサー獲得回数0

ポイント80pt

http://www.excite.co.jp/world/english/

英語翻訳 - エキサイト 翻訳

英語で説明してありますね。

1行目左はノードの個数

1行目右はノード間を繋ぐエッジの個数

2行目以降は左の番号を持つノードから右の番号を持つノードへのエッジがあるよ、という定義。

故にこの場合は4つのノード間を結ぶ4つのエッジがあり、1-2-3-4-1という順番で輪を描いているグラフを定義しているです。

id:nishioka

なるほど、よくわかりました。

しかし、このプログラムを地図の色分けに適用するには、前処理として面同士のネットワーク関係を抽出する必要がありそうですね。うーんすっきりしたような、難しくなったような...

2005/02/08 20:06:00

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

回答リクエストを送信したユーザーはいません