資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學什麼是規範標籤？
處理圖同構問題的標準方法是將每個圖對映到一個特定的字串表示形式，稱為其程式碼或規範標籤。規範標籤具有這樣的屬性：如果兩個圖是同構的，那麼它們的程式碼應該相等。
此屬性使我們能夠透過分析圖的規範標籤來測試圖同構性。構建圖規範標籤的第一步是為該圖發現一個鄰接矩陣描述。它顯示了給定圖的此類矩陣的一個例項。
一個圖可以有多個鄰接矩陣描述，因為有多種方法可以對鄰接矩陣中的頂點進行排序。第一行和第一列與具有 3 條邊的頂點 a 相關，第二行和第二列與具有 2 條邊的另一個頂點 a 相關，依此類推。要推匯出圖的所有鄰接矩陣描述，需要處理矩陣的所有可能的行排列。
示例 − 考慮以下矩陣
M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
可以使用以下置換矩陣將第一行（和列）與 M 的第三行進行轉換 −
P13 = 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
其中 P13 透過交換單位矩陣的第一行和第三行獲得。它可以交換第一行和第三行（和列），置換矩陣與 M 相乘 −
M′ = P13T X M X P13= 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16
第二步是為每個鄰接矩陣確定字串描述。因為鄰接矩陣是對稱的，所以根據矩陣的上三角部分生成字串描述是有效的。
程式碼是透過以列方式連線上三角矩陣的條目獲得的。最後一步是關聯圖的所有字串描述，並選擇具有最低（或最高）字典順序值的那個。
之前的方法看起來代價高昂，因為它需要我們確定圖的所有可能的鄰接矩陣，並評估它們的每個字串描述以發現規範標籤。此外，對於每個包含 k 個頂點的圖，都應該處理 kl 個排列。
已經開發出各種方法來降低此任務的複雜性，包括快取先前計算的規範標籤，並透過合併更多資料（包括頂點標籤和頂點的度數）來減少確定規範標籤所需的排列數。
更新於：2022年2月11日
396 次檢視
廣告