数学において、グラフ多項式とは、値が多項式であるグラフ不変量です。この種の不変量は代数的グラフ理論で研究されています。[1] 重要なグラフ多項式には以下のものがあります。
- グラフの隣接行列に基づく特性多項式。
- 彩色多項式は、整数引数における値がグラフをその色数で彩色する数を表す多項式です。
- 二色多項式は、彩色多項式の2変数一般化である。
- フロー多項式は、整数引数における値が、引数を法とする整数フロー量を持つ、どこにもゼロがないフローの数を表す多項式です。
- グラフ内の特定の閉じたウォークに対応する二項項の積として定義される、伊原ゼータ関数(の逆関数) 。
- ピエール・マルタンがオイラーツアーの研究に使用したマルタン多項式
- マッチング多項式は、グラフのマッチングの生成関数として定義されるいくつかの異なる多項式です。
- 信頼性多項式は、独立したエッジ障害が発生した後に接続が維持される確率を表す多項式です。
- Tutte多項式は、2 つの変数の多項式であり、(変数を少し変更した後) 与えられたグラフの誘導サブグラフの接続コンポーネントの数の生成関数として定義でき、サブグラフの頂点の数によってパラメータ化されます。
参照
参考文献
- ^ Shi, Yongtang; Dehmer, Matthias; Li, Xueliang; Gutman, Ivan (2016)、『グラフ多項式、離散数学とその応用』、CRC Press、ISBN 9781498755917
このセットインデックス記事には、同じ名前（または類似の名前）を持つ関連項目のリストが含まれています。
内部リンクから誤ってこのページに移動した場合は、リンクを目的の記事に直接変更することをお勧めします。
内部リンクから誤ってこのページに移動した場合は、リンクを目的の記事に直接変更することをお勧めします。
