TopologicalSort

TopologicalSort[g]

有向非巡回グラフ g について，g の頂点のリストを位相的に並べて与える．

TopologicalSort[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細

  • TopologicalSortは，位相順位あるいは位相順序としても知られている．
  • 各辺 uv について u が v に先行するならその頂点リストは位相的に並べられている．

例題

すべて開くすべて閉じる

例  (1)

頂点の位相的順序を求める：

スコープ  (6)

TopologicalSortは有向グラフに使うことができる：

重み付きグラフ：

多重グラフ：

TopologicalSortは非巡回グラフのみに使うことができる：

規則を使ってグラフを指定する：

大きいグラフに使う：

アプリケーション  (1)

巡回グラフの場合は頂点の代りに強連結成分をソートする：

成分間の辺を求めることで g を圧縮する：

強連結成分の位相的な順序を使って g の頂点を順序付ける：

新たな隣接行列はブロック上三角行列である：

Wolfram Research (2010), TopologicalSort, Wolfram言語関数， https://reference.wolfram.com/language/ref/TopologicalSort.html （2015年に更新）.

テキスト

Wolfram Research (2010), TopologicalSort, Wolfram言語関数， https://reference.wolfram.com/language/ref/TopologicalSort.html （2015年に更新）.

CMS

Wolfram Language. 2010. "TopologicalSort." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/TopologicalSort.html.

APA

Wolfram Language. (2010). TopologicalSort. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/TopologicalSort.html

BibTeX

@misc{reference.wolfram_2024_topologicalsort, author="Wolfram Research", title="{TopologicalSort}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/TopologicalSort.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_topologicalsort, organization={Wolfram Research}, title={TopologicalSort}, year={2015}, url={https://reference.wolfram.com/language/ref/TopologicalSort.html}, note=[Accessed: 18-November-2024 ]}