有向グラフ

質問

有効グラフに関しての問題なんですがわからないところがあるのでお願いします。

閉路を含まない有向グラフ（Ｇ）について以下の問いに答えなさい。
（１）Ｇの点番号が「トポロジカル・オーダ」に従うとはどのようなことか説明しなさい。
（２）点番号の付けられていないＧに、トポロジカル・オーダに従う点番号を付ける手順（手続き）を書きなさい。
（３）トポロジカル・オーダの順に点を並べてできる隣接行列はどのような特徴をもつか

（２）がよくわかりません。また（１）、（３）はなんとなくわかるんですがなんか同じ意味になってしまってうまく答えられません。
だれか解説お願いします。

回答No.1

Tacosan · ベストアンサー

(1) は実質的に「トポロジカルオーダーの定義」を言うことになります.
飛んで (3) は (1) から得られるんだけど, 点の順序をトポロジカルオーダーでならべるたときに, 隣接行列がどのような形になるかを答えるということですね. だから (1) と (3) では違う表現になる (というか, (1) では隣接行列に言及しないはず) のが普通です.
で (2) だけど, これは「トポロジカルオーダーが存在するならそれを求める」アルゴリズムでいいんですね? (3) の結果を使えば想像つくかも. ヒントは「トポロジカルオーダーで最初の点はどのような条件を満たさなければならないか」を考えること.

お礼

ありがとうございました！！自分なりにですが回答を作れました。。
わかりやすかったです！！