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はダミーでも結構です。
http://www.excite.co.jp/world/english/
英語翻訳 - エキサイト 翻訳
英語で説明してありますね。
1行目左はノードの個数
1行目右はノード間を繋ぐエッジの個数
2行目以降は左の番号を持つノードから右の番号を持つノードへのエッジがあるよ、という定義。
故にこの場合は4つのノード間を結ぶ4つのエッジがあり、1-2-3-4-1という順番で輪を描いているグラフを定義しているです。
なるほど、よくわかりました。
しかし、このプログラムを地図の色分けに適用するには、前処理として面同士のネットワーク関係を抽出する必要がありそうですね。うーんすっきりしたような、難しくなったような...