主題
Search

區分數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

圖 G 的（頂點）的標記 phi，使用集合 {1,2,...,r} 中的正整數，被稱為是 r-可區分的，如果 圖自同構 G 不保留所有的頂點標籤。形式上，phi 是 r-可區分的，如果對於每個非平凡的 sigma in Aut(G)，都存在 x in V(G) 使得 phi(x)!=phi(xsigma)，其中 V(G) 是 G 的頂點集，Aut(G) 是 G 的 自同構群。圖 G 的區分數 D(G) 然後是最小的 r，使得 G 有一個 r-可區分的標記 (Albertson and Collins 1996)。

具有相同自同構群的不同圖可能具有不同的區分數。

D(G)=1 當且僅當 G 是 恆等圖 時成立。圖 G 及其 圖補 G^_ 具有相同的區分數。

具有 |Aut(G)|<=k! 的圖 G 的區分數 D(G)<=k (Tymoczko 2005; 歸功於 Albertson, Collins, 和 Kleitman)。

特殊情況總結在下表中。

GD(G)
完全二部圖 K_(n,n)n+1
完全圖 K_nn
圈圖 C_n{3 for n=3,4,5; 2 for n>=6
廣義 Petersen 圖 GP(n,k){3 for (n,k)=(4,1),(5,2); 2 otherwise
超立方體圖 Q_n{1 for n=0; 2 for n=1; 3 for n=2,3; 2 for n>=4
路徑圖 P_n{1 for n=1; 2 for n>=2
星圖 S_n{n for n=1,2; n-1 otherwise
n-三角圖 L(K_n){1 for n=1,2; 3 for n=3,4,5; 2 for n>=6
輪圖 W_n{4 for n=4; 3 for n=5,6; 2 for n>=7

另請參閱

色數, 色多項式

使用 探索

參考文獻

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18.Konhauser, J. D. E.; Velleman, D.; and Wagon, S. 腳踏車是怎麼走的？以及其他有趣的數學謎題。 Washington, DC: Math. Assoc. Amer., 1996.Rubin, F. Problem 729. In J. Recr. Math. 11, 128, 1979. (Solution in Vol. 12, 1980).Tymoczko, J. "Distinguishing Numbers for Graphs and Groups." 17 Mar 2005. http://arxiv.org/abs/math/0406542

請引用本文為

Weisstein, Eric W. "區分數。" 來自 --一個 資源。 https://mathworld.tw/DistinguishingNumber.html

學科分類