圖屬性

在圖論中，圖屬性（graph property）或圖常量（graph invariant，又稱圖不變量）是圖的一種性質，它只取決於其抽象結構，而不取決於圖的表示形式如特定的圖標號或圖繪製形式。^[1]

一個示例圖。該圖為平面圖與連通圖，有頂點數為6，邊數為7，最短路徑為3，圍長為3，度序列為<3, 3, 3, 2, 2, 1>。

定義

雖然圖的繪製和圖的表示都是圖論中的有效課題，但為了只關注圖的抽象結構，圖屬性被定義為在圖的所有可能同構下仍存在的屬性。換句話說，它是圖本身的屬性，而不是其特定的繪製或表示形式。非正式用法中，術語「常量」用於定量表示其屬性，而「屬性」用於定性描述圖的特徵。例如，語句「圖沒有度為1的頂點」為「屬性」用法，而「圖中度為1的頂點數量」為「常量」用法。

更正式地說，圖屬性是指具有相同屬性的一類圖，其任何兩個同構圖要麼都屬於該類，要麼都不屬於該類。^[1]等價來說，可以使用這類圖的指示函數（將圖轉化為布爾值的函數，屬於該類的圖為真，否則為假）將圖屬性形式化，其中任何兩個同構圖必須具有相同的函數值。類似地，圖常量或圖參數可以形式化為一個函數，還可從圖推廣到更廣泛的值類，如整數、實數、數字序列或多項式，這些值對應的圖其任何兩個同構圖都具有相同的值。^[2]

圖屬性的特徵

對於圖上定義的某些自然偏序關係或預序關係，許多圖屬性與其相關性較高:

如果具有P屬性的圖其每一個誘導子圖都具有P屬性，則稱該圖是遺傳的。例如，完美圖和弦圖是遺傳的。^[1]
如果具有P屬性的圖其每一個子圖都具有P屬性，則稱該圖是單調的。例如，二分圖和無三角形圖是單調的。所有單調的圖都是遺傳的，但遺傳的圖不一定單調。例如，弦圖的子圖不一定是弦圖，所以弦圖並不是單調的。^[1]
如果具有P屬性的圖其每一個次圖都具有P屬性，則稱該圖是小型閉合的。例如，平面圖是小型閉合的。所有小型閉合的圖都是單調的，但單調的圖不一定是小型閉合的。例如，無三角形圖的次圖不一定是無三角圖，所以無三角形圖不是小型閉合的。^[1]

這些定義可以從圖屬性擴展到圖的數值常量：如果圖常量形式化為對應到實數域的單調函數，則圖常量是遺傳的、單調的或小型閉合的。。

此外，還研究了圖常量在圖的不相交併集方面的行為:

對於圖G和圖H，如果G和H的不相交併集里的常量值是G和H各自常量值之和，則對應的圖常量是可加的。例如，其頂點數是可加的。^[1]
對於圖G和圖H，如果G和H的不相交併集里的常量值是G和H各自常量值之積，則對應的圖常量是可乘的。例如，Hosoya指數(匹配數)是可乘的。^[1]
對於圖G和圖H，如果G和H的不相交併集里的常量值是G和H各自常量值的最大值，則對應的圖常量就是兩者中的最大值。^[1]

此外，圖屬性可以根據它們所描述的圖類型進行分類：圖是無向的還是有向的，圖的屬性是否適用於多重圖等。^[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 .

[l-1] 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

[2] 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 .

[1]

[2]