有向非巡回グラフを読んでいますが、ラベルを付け直してもトポロジカル順序の概念を理解できません。一般的なトポロジカル順序
についての私の理解は、DAG内のすべての頂点が終了するまで、入力エッジのない頂点からパス上の次の頂点へと移動するような頂点の順序を見つけることです。
しかし、ラベルの付け直しがどのように役立つのかわかりません。頂点のラベルを変更する意味は何ですか？実際にこのようにグラフを壊しませんか？
誰かがその適用例を使ってわかりやすく説明してもらえますか？
質問する
513 次
1 に答える
2
参照なしでは確実にわかりませんが、このコンテキストでのラベルの付け直しは、通常、頂点の順序を変更することを意味します。これは、グラフのトポロジ（エッジと頂点）を変更することを意味するのではなく、並べ替え順序を変更することを意味します。
また、グラフの置換行列またはベクトルを生成することと考えることもできます。これにより、元のグラフと同型のグラフが作成されますが、頂点1,2,3 ...、nはソートされた順序に対応します。
于 2012-05-19T20:55:31.730 に答える