マッチング多項式

グラフ理論と組合せ論の数学の分野において、マッチング多項式（非巡回多項式と呼ばれることもある）は、グラフ内のさまざまなサイズのマッチングの数を生成する関数である。これは代数グラフ理論で研究されるグラフ多項式の 1 つである。

いくつかの異なるタイプのマッチング多項式が定義されています。Gをn頂点を持つグラフとし、m _{k を}k辺のマッチングの数とします。

Gの対応する多項式は

${\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}$

別の定義では、対応する多項式は次のようになる。

${\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}$

3番目の定義は多項式である

${\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k}.}$

それぞれの型には用途があり、単純な変換によってすべて同等になります。たとえば、

${\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}$

そして

${\displaystyle \mu_{G}(x,y)=y^{n}m_{G}(x/y^{2}).}$

最初のタイプのマッチング多項式は、ルーク多項式の直接的な一般化です。

2 番目のタイプのマッチング多項式は、直交多項式と注目すべき関係があります。たとえば、完全な 2 部グラフG  =  K _{m , n}の場合、 2 番目のタイプのマッチング多項式は、一般化ラゲール多項式L _n ^α ( x ) と次の恒等式で関連しています。

${\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(mn)}(x^{2}).\,}$

Gが完全グラフ Knの場合、M _G ( x )はエルミート多項式である _。

${\displaystyle M_{K_{n}}(x)=H_{n}(x),\,}$

ここでH _n ( x )はエルミート多項式の定義における「確率論者のエルミート多項式」(1)である。これらの事実はGodsil(1981)によって観察された。

Gがフォレストの場合、そのマッチング多項式は隣接行列の特性多項式に等しくなります。

Gがパスまたはサイクルの場合、M _G ( x ) はチェビシェフ多項式です。この場合、μ _G (1, x ) はそれぞれフィボナッチ多項式またはルーカス多項式です。

n頂点を持つグラフGのマッチング多項式は、その補グラフのマッチング多項式と 1 組の (同等の) 式で関連付けられます。そのうちの 1 つは、Zaslavsky (1981) による単純な組み合わせ恒等式です。もう 1 つは、Godsil (1981) による積分恒等式です。

K _{m , n}のサブグラフGとK _{m , n}におけるその補グラフにも同様の関係があります。この関係は、Riordan (1958) によって、非攻撃ルーク配置とルーク多項式のコンテキストで知られていました。

グラフGのHosoya 指数、すなわちそのマッチング数は、分子グラフの構造記述子として化学情報科学で使用されます。これはm _G (1) として評価されることがあります (Gutman 1991)。

3 番目のタイプのマッチング多項式は、化学で使用される「非巡回多項式」のバージョンとして Farrell (1980) によって導入されました。

任意のグラフ、または平面グラフでも、マッチング多項式の計算は#P 完全です(Jerrum 1987)。ただし、グラフに関する追加の構造がわかっている場合は、より効率的に計算できます。特に、ツリー幅kのn頂点グラフでのマッチング多項式の計算は、固定パラメータで実行可能です。つまり、任意の固定定数kに対して、実行時間がkに依存しない指数を持つnの多項式であるアルゴリズムが存在します (Courcelle、Makowsky、Rotics 2001) 。n頂点でクリーク幅kのグラフのマッチング多項式は、時間n ^{O( k )}で計算される場合があります(Makowsky 他 2006)。

• Courcelle, B. ; Makowsky, JA; Rotics, U. (2001)、「モナディック 2 階論理で定義可能なグラフ列挙問題の固定パラメータ複雑性について」(PDF)、離散応用数学、108 (1–2): 23–52、doi :10.1016/S0166-218X(00)00221-3。
• Farrell, EJ (1980)、「マッチング多項式とグラフの非巡回多項式との関係」、Ars Combinatoria、9 : 221–228。
• Godsil, CD (1981)、「エルミート多項式とマッチング多項式の双対関係」、Combinatorica、1 (3): 257–262、doi :10.1007/BF02579331。
• グットマン、イヴァン (1991)、「グラフ理論における多項式」、ボンチェフ、D.、ルーヴレー、DH (編)、『化学グラフ理論: 入門と基礎』、数理化学、第 1 巻、テイラー & フランシス、pp. 133–176、ISBN 978-0-85626-454-2。
• ジェラム、マーク (1987)、「2 次元モノマー-ダイマー システムは計算上扱いにくい」、Journal of Statistical Physics、48 (1): 121–134、Bibcode :1987JSP....48..121J、doi :10.1007/BF01010403。
• Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006)、「制限されたクリーク幅のグラフ上のグラフ多項式の計算」、Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06) (PDF)、Lecture Notes in Computer Science、vol. 4271、Springer-Verlag、pp. 191–204、doi :10.1007/11917496_18、ISBN 978-3-540-48381-6。
• リオダン、ジョン（1958）、組合せ分析入門、ニューヨーク：ワイリー。
• ザスラフスキー、トーマス（1981）、「相補マッチングベクトルと均一マッチング拡張特性」、ヨーロッパ組合せ論ジャーナル、2：91-103、doi：10.1016 / s0195-6698（81）80025-x。