圖形屬性

一個示例圖，具有平面和連接的屬性，以及命令6，尺寸7，直徑3，周長3，頂點連接1和度序列<3，3，3，3，2，2，2，1>

在圖理論中，圖形屬性或圖形不變是圖形的屬性，僅取決於抽象結構，而不取決於圖表的圖表（例如特定的標記或圖形圖紙） 。

定義

雖然圖形圖和圖表是圖理論中的有效主題，但僅關注圖的抽象結構，而圖形屬性被定義為在圖形的所有可能同構中保留的屬性。換句話說，它是圖本身的屬性，而不是圖形的特定圖形或表示。非正式地，術語“圖形不變”用於定量表示的屬性，而“屬性”通常是指圖形的描述性特徵。例如，語句“ Graph沒有度量1”的頂點是“屬性”，而“圖中1度的頂點的數量”是“不變”。

更正式的是，圖形屬性是一類帶有屬性的屬性類別，即任何兩個同構圖都屬於該類，或者兩者都不屬於該類。同等地，可以使用類的指示函數對圖形屬性進行形式化，該函數從圖形到布爾值的函數對於類中的圖形和false否則為boole值；同樣，任何兩個同構圖都必須具有與彼此相同的函數值。圖形不變或圖參數可以類似地作為從圖形到更廣泛的值類別的函數（例如整數，實數，數字序列或多項式）的函數，該函數對於任何兩個同構圖都具有相同的值。

屬性的屬性

相對於某些自然部分訂單或圖表上定義的預訂，許多圖形屬性均得到很好的行為：

  • 如果圖形的每個引起的子圖具有屬性P的屬性p ，則圖形屬性p是遺傳性的。例如，作為完美的圖形或弦圖是遺傳性能。
  • 圖形屬性是單調的，如果圖形的每個子圖都帶有屬性p的屬性p 。例如，作為雙方圖或作為三角形圖是單調的。每個單調屬性都是遺傳性的，但不一定反之亦然。例如，和弦圖的子圖不一定是和弦，因此作為和弦圖不是單調。
  • 如果圖形屬性的每個圖形小調都具有屬性p的屬性p ，則圖形屬性是少量關閉的。例如，作為平面圖是少量關閉的。每個少量關閉的特性都是單調的，但不一定是副主義。例如，無三角形圖的未成年人本身並不一定不含三角形。

這些定義可以從屬性擴展到圖形的數值不變性：如果形式化不變的功能形式化不變的函數，則圖形不變性是遺傳性，單調或次要閉合的，從圖形上的相應部分順序形成單調函數。

此外，已經研究了圖形不變的圖形工會的行為：

  • 如果在所有兩個圖G和H中，G和H的不變值是G和H的不相交聯合的值是G和H上的值的總和，則圖形不變性是加性的。例如，頂點的數量是加法的。
  • 如果對於所有兩個圖G和H ，G和H的不變值是G和H的不相交聯合的值是G和H上的值是G和H上的值的乘積，則圖形不變性。例如，霍索亞索引（匹配數）是乘法的。
  • 如果在所有兩個圖G和H中，G和H的不變值是G和H的不相交聯合是G和H上的最大值的最大值，則圖形不變性。例如，色數最大化。

此外，可以根據其描述的圖類型對圖形屬性進行分類：該圖是未指導還是指向圖形，該屬性是否適用於多編碼，等等。

不變的值

定義圖形不變的函數的目標集可能是：

圖形不變和圖同構

易於計算的圖形不變性對於圖形同構的快速識別或非同態性具有重要作用，因為對於任何不變的，兩個具有不同值的圖形（按定義）都不能是同構。但是，兩個具有相同不變性的圖可能是同構的，也可能不是同構。

如果不變的i （ g ）和i （ h ）的身份意味著圖G和H的同構，則稱為圖形I（g）。找到一個有效競爭的這種不變的（圖形化問題）將意味著解決挑戰性的圖形同構問題的一種簡單解決方案。但是，即使是多項式價值不變的，例如色多項式，通常也不完整。例如，4個頂點上的爪圖和路徑圖都具有相同的色度多項式。

例子

特性

整數不變

實際數字不變

序列和多項式

也可以看看