圖屬性

圖的不變量

圖論中,圖屬性(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個頂點的道路圖都具有相同的色多項式。

實例

編輯

屬性

編輯

整數常量

編輯

實數常量

編輯

序列和多項式

編輯

參見

編輯

參考文獻

編輯
  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 .