グラフプロパティ

平面であり連結であるという特性を持ち、位数が 6、大きさが 7、直径が3、内周が3 、頂点連結性が1、次数順序が $<3, 3, 3, 2, 2, 1> であるグラフの例$

グラフ理論において、グラフ特性またはグラフ不変量は、グラフの特定のラベル付けや描画などのグラフ表現ではなく、抽象的な構造のみに依存するグラフの特性である。 ^[1]

定義

グラフの描画とグラフの表現はグラフ理論の有効なトピックですが、グラフの抽象構造にのみ焦点を当てるために、グラフプロパティはグラフのすべての可能な同型性の下で保持されるプロパティとして定義されます。言い換えると、グラフ自体のプロパティであり、グラフの特定の描画や表現のプロパティではありません。非公式には、「グラフ不変量」という用語は定量的に表現されたプロパティに使用され、「プロパティ」は通常、グラフの記述的な特徴付けを指します。たとえば、「グラフには次数 1 の頂点がない」というステートメントは「プロパティ」ですが、「グラフ内の次数 1 の頂点の数」は「不変量」です。

より正式には、グラフプロパティとは、任意の2つの同型グラフが両方ともそのクラスに属するか、両方ともそのクラスに属さないかのいずれかであるというプロパティを持つグラフのクラスです。^[1]同様に、グラフプロパティは、クラスのインジケータ関数、つまりグラフからブール値への関数を使用して形式化できます。この関数は、クラス内のグラフに対しては真、そうでない場合は偽です。この場合も、任意の2つの同型グラフは互いに同じ関数値を持つ必要があります。グラフ不変量またはグラフパラメータも同様に、グラフから整数、実数、数列、多項式などのより広い値クラスへの関数として形式化できます。この関数も、任意の2つの同型グラフに対して同じ値を持ちます。^[2]

プロパティのプロパティ

多くのグラフプロパティは、グラフ上で定義された特定の自然な半順序または事前順序に関して適切に動作します。

グラフ特性Pが遺伝的であるとは、特性Pを持つグラフのすべての誘導部分グラフが特性P も持つ場合である。例えば、完全グラフであることや弦グラフであることは遺伝的特性である。^[1]
グラフ特性が単調であるとは、特性Pを持つグラフのすべてのサブグラフが特性Pも持つ場合です。たとえば、二部グラフであることや三角形のないグラフであることは単調です。すべての単調特性は遺伝的ですが、その逆は必ずしも当てはまりません。たとえば、弦グラフのサブグラフは必ずしも弦ではないため、弦グラフであることは単調ではありません。^[1]
グラフ特性がマイナー閉であるとは、特性Pを持つグラフのすべてのグラフマイナーが特性Pも持つ場合である。例えば、平面グラフはマイナー閉である。すべてのマイナー閉特性は単調であるが、その逆は必ずしも成り立たない。例えば、三角形のないグラフのマイナーは、それ自体が三角形がないとは限らない。^[1]

これらの定義は、特性からグラフの数値不変量に拡張できます。グラフ不変量は、不変量を形式化する関数がグラフ上の対応する半順序から実数への単調関数を形成する場合、遺伝的、単調、またはマイナークローズです。

さらに、グラフ不変量は、グラフの非結合和に対する動作に関して研究されてきました。

グラフ不変量は、2つのグラフGとHのすべてについて、 GとHの非結合和の不変量の値がGとHの値の合計である場合に加法的である。例えば、頂点の数は加法的である。^[1]
グラフ不変量は、2つのグラフGとHのすべてについて、 GとHの非結合和の不変量の値がGとHの値の積である場合に乗法的である。例えば、細谷指数（マッチング数）は乗法的である。^[1]
グラフ不変量が最大化されるとは、2つのグラフGとHのすべてについて、 GとHの非結合和の不変量の値がGとHの値の最大値となる場合である。例えば、彩色数は最大化される。^[1]

さらに、グラフプロパティは、それが記述するグラフの種類によって分類することができます。グラフが無向か有向か、プロパティがマルチグラフに適用されるかどうかなどです。^[1]

不変量の値

グラフ不変量を定義する関数のターゲットセットは、次のいずれかになります。

グラフプロパティのインジケーター関数の真理値 (true または false)。
グラフの頂点数や彩色数などの整数。
グラフの分数彩色数などの実数。
グラフの次数シーケンスなどの整数のシーケンス。
グラフのTutte 多項式などの多項式。

グラフ不変量とグラフ同型性

簡単に計算できるグラフ不変量は、グラフ同型性、またはむしろ非同型性を迅速に認識するのに役立ちます。これは、どのような不変量でも、異なる値を持つ 2 つのグラフは (定義により) 同型にはなり得ないためです。ただし、同じ不変量を持つ 2 つのグラフは、同型である場合もそうでない場合もあります。

グラフ不変量I ( G ) は、不変量I ( G ) とI ( H ) の恒等式がグラフGとHの同型性を意味する場合、完全と呼ばれます。効率的に計算可能なそのような不変量 (グラフ正規化の問題) を見つけることは、困難なグラフ同型性の問題に対する簡単な解決を意味します。ただし、彩色多項式などの多項式値の不変量でさえ、通常は完全ではありません。たとえば、クローグラフと4 頂点のパスグラフは、どちらも同じ彩色多項式を持ちます。

例

プロパティ

整数不変量

順序、頂点の数
サイズ、エッジの数
接続されたコンポーネントの数
回路ランク、辺、頂点、コンポーネントの数の線形結合
直径、頂点間の最短経路の長さのうち最長のもの
胴回り、最短周期の長さ
頂点の連結性、つまりグラフが切断される頂点の最小数
エッジの接続性、削除するとグラフが切断される最小のエッジの数
彩色数、適切な彩色における頂点の最小の色数
彩度指数、適切なエッジカラーリングにおけるエッジの最小色数
選択可能性（または彩色数のリスト）、Gがk選択可能である最小の数k
独立数、独立した頂点集合の最大サイズ
クリーク数、完全部分グラフの最大位数
樹木性
グラフの属
ページ番号
細谷指数
ウィーナー指数
コラン・ド・ヴェルディエールグラフの不変性
ボクシティ

実数不変量

数列と多項式

度数順
グラフスペクトル
隣接行列の特性多項式
彩色多項式、関数として見た - 色の数 $k$ $k$
Tutte多項式、グラフの接続性の多くをエンコードする2変数関数

参照

世襲財産
グラフの論理。グラフの特性を指定するために使用されるいくつかの形式言語の1つ。
位相インデックス、化学グラフ理論と密接に関連する概念

外部リンク

整数不変量の一覧

参考文献

^ abcdefghi Lovász, László (2012)、「4.1 グラフパラメータとグラフプロパティ」、Large Networks and Graph Limits、Colloquium Publications、vol. 60、American Mathematical Society、pp. 41–42、ISBN 978-1-4704-1583-9。
^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「3.10 グラフパラメータ」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、pp. 54–56、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。

[l-1] Lovász, László (2012)、「4.1 グラフパラメータとグラフプロパティ」、Large Networks and Graph Limits、Colloquium Publications、vol. 60、American Mathematical Society、pp. 41–42、ISBN 978-1-4704-1583-9。

[2] Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「3.10 グラフパラメータ」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、pp. 54–56、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。