主題
Search

規範化標記


G 的規範化標記,也稱為規範形式,是一個圖 G^',它與 G 同構,並且代表 G 的整個同構類 (Piperno 2011)。規範化標記的複雜度類是未知的。

高效的標記方法為同構圖提供了高效的測試,例如 nauty、Traces、bliss 和其他軟體實現所提供的。


參見

同構圖

使用 探索

參考文獻

Junttila, T. and Kaski, P. "Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs." In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (Ed. D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick.) SIAM: pp. 135-149, 2007.McKay, B. "Practical Graph Isomorphism." Congr. Numer. 30, 45-87, 1981. http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.McKay, B. and Piperno, A. "Practical Graph Isomorphism, II." 8 Jan 2013. http://arxiv.org/abs/1301.1493.Piperno, A. "Search Space Contraction in Canonical Labeling of Graphs." 26 Jan 2011. http://arxiv.org/abs/0804.4881.

引用為

Weisstein, Eric W. “規範化標記”。來自 ——Wolfram 網路資源。 https://mathworld.tw/CanonicalLabeling.html

主題分類