DAG圖和拓撲排序混淆基本面

我正在閱讀定向非循環圖我不明白拓撲秩序的想法通過relabeling。
我對拓撲秩序的理解一般是我們找到頂點的順序，以便我們從沒有輸入邊的那個移動到路徑上的下一個，等等，直到我們完成了頂點的所有頂點DAG。
但我不明白重貼標籤有何幫助。我的意思是重新標記頂點的意義是什麼？我們不是真的以這種方式破壞圖表嗎？
任何人都可以請簡單解釋一下它的應用程序的例子嗎？DAG圖和拓撲排序混淆基本面

來源

2012-05-19 Cratylus

我無法確定沒有參考，但在這種情況下重新貼標籤通常意味着改變頂點的順序。這並不意味着改變圖形的拓撲（邊緣和頂點），而是意味着改變排序順序。

您也可以將其視爲爲圖生成置換矩陣或向量。這創建了一個圖表isomorphic到原來的，但是其中頂點1,2,3 ...，n對應於排序順序

來源

2012-05-19 20:55:31 dfb

這是我感到困惑的部分。這裏的「排序順序」是什麼意思？ – Cratylus

這只是排序的數組或圖形 - 元素按照某些標準排列的順序。在一個數組中，如果它是一個字符串，數字等，那麼這可以是曲線圖。在一個圖中，拓撲排序被定義爲具有輸出邊的頂點高於其目標的排序。請注意，多個置換矩陣可能會滿足該條件 – dfb

DAG圖和拓撲排序混淆基本面

回答

相關問題