圖屬性
在圖論中，圖屬性（graph property）或圖常量（graph invariant，又稱圖不變量）是圖的一種性質，它只取決於其抽象結構，而不取決於圖的表示形式如特定的圖標號或圖繪製形式。[1]
定義 編輯
雖然圖的繪製和圖的表示都是圖論中的有效課題，但為了只關注圖的抽象結構，圖屬性被定義為在圖的所有可能同構下仍存在的屬性。換句話說，它是圖本身的屬性，而不是其特定的繪製或表示形式。非正式用法中，術語「常量」用於定量表示其屬性，而「屬性」用於定性描述圖的特徵。例如，語句「圖沒有度為1的頂點」為「屬性」用法，而「圖中度為1的頂點數量」為「常量」用法。
更正式地說，圖屬性是指具有相同屬性的一類圖，其任何兩個同構圖要麼都屬於該類，要麼都不屬於該類。[1]等價來說，可以使用這類圖的指示函數（將圖轉化為布爾值的函數，屬於該類的圖為真，否則為假）將圖屬性形式化，其中任何兩個同構圖必須具有相同的函數值。類似地，圖常量或圖參數可以形式化為一個函數，還可從圖推廣到更廣泛的值類，如整數、實數、數字序列或多項式，這些值對應的圖其任何兩個同構圖都具有相同的值。[2]
圖屬性的特徵 編輯
對於圖上定義的某些自然偏序關係或預序關係，許多圖屬性與其相關性較高:
- 如果具有P屬性的圖其每一個誘導子圖都具有P屬性，則稱該圖是遺傳的。例如，完美圖和弦圖是遺傳的。[1]
- 如果具有P屬性的圖其每一個子圖都具有P屬性，則稱該圖是單調的。例如，二分圖和無三角形圖是單調的。所有單調的圖都是遺傳的，但遺傳的圖不一定單調。例如，弦圖的子圖不一定是弦圖，所以弦圖並不是單調的。[1]
- 如果具有P屬性的圖其每一個次圖都具有P屬性，則稱該圖是小型閉合的。例如，平面圖是小型閉合的。所有小型閉合的圖都是單調的，但單調的圖不一定是小型閉合的。例如，無三角形圖的次圖不一定是無三角圖，所以無三角形圖不是小型閉合的。[1]
這些定義可以從圖屬性擴展到圖的數值常量：如果圖常量形式化為對應到實數域的單調函數，則圖常量是遺傳的、單調的或小型閉合的。。
此外，還研究了圖常量在圖的不相交併集方面的行為:
常量值 編輯
定義圖常量的函數其目標集可以是:
圖常量與圖同構 編輯
易於計算的圖常量有助於快速識別同構圖，或者說是識別非同構圖。因為對於任何常量，具有不同值的兩個圖(根據定義)不能是同構的。然而，具有相同常量的兩個圖可能是同構的，也可能不是同構的。
如果常量I(G)和I(H)恆等，則意味着圖G和圖H的同構，此時稱圖常量I(G)是完備的。找到一個可有效計算這種常量的方法(圖規範化問題)等價於給出一個簡單解決富有挑戰性的圖同構問題的方法。然而，即使多項式的常量值如色多項式，通常也不完備的。例如，爪形圖和4個頂點的道路圖都具有相同的色多項式。
實例 編輯
屬性 編輯
整數常量 編輯
- 頂點數
- 邊數
- 元件數
- 電路等級（圖的頂點、邊和元件的線性組合）
- 直徑（頂點對之間最長的最短路徑）
- 圍長
- 頂點連通性（切斷圖所需移除的最小頂點數）
- 邊的連接性（切斷圖所需移除的最小邊數）
- 着色數（將所有頂點着色且相鄰頂點不同顏色的最小顏色數）
- 着色指數（將所有邊着色且相鄰邊不同顏色的最小顏色數）
- 獨立集（規模最大的獨立頂點集）
- 團頂點數（最大完備子圖的頂點數）
- 蔭度
- Hosoya指數
- Wiener指數
實數常量 編輯
序列和多項式 編輯
參見 編輯
參考文獻 編輯
- ^ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Lovász, László, 4.1 Graph parameters and graph properties, Large Networks and Graph Limits, Colloquium Publications 60, American Mathematical Society: 41–42, 2012
- ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice, 3.10 Graph Parameters, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer: 54–56, 2012, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4.