圖屬性

在圖論中，圖屬性（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指數

實數常量

• 聚類係數
• 介數中心性
• 分數色數
• 代數連通度
• 等周數
• Estrada指數
• 強度

序列和多項式

• 程序
• 圖譜
• 鄰接矩陣的特徵多項式
• 色多項式
• 塔特多項式

參見

• 邏輯圖，用於指定圖形屬性的幾種形式語言之一
• 拓撲指數，在化學圖論的一個密切相關的概念