Odpovídající polynom - Matching polynomial

V matematický pole teorie grafů a kombinatorika, a odpovídající polynom (někdy se tomu říká acyklický polynom) je generující funkce z počtu párování různých velikostí v grafu. Je to jeden z několika polynomy grafů studoval v algebraická teorie grafů.

Definice

Bylo definováno několik různých typů shodných polynomů. Nechat G být graf s n vrcholy a nechat m_k být počet k-osazování hran.

Jeden odpovídající polynom o G je

${ displaystyle m_ {G} (x): = součet _ {k geq 0} m_ {k} x ^ {k}.}$

Jiná definice udává odpovídající polynom jako

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

Třetí definicí je polynom

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

Každý typ má své použití a všechny jsou ekvivalentní jednoduchými transformacemi. Například,

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

a

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

Spojení s jinými polynomy

První typ vyhovujícího polynomu je přímé zobecnění havarovaný polynom.

Druhý typ shodného polynomu má pozoruhodné souvislosti ortogonální polynomy. Například pokud G = K._m,n, kompletní bipartitní graf, pak druhý typ shodného polynomu souvisí s generalizovaným Laguerrův polynom L_n^α(X) podle totožnosti:

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

Li G je kompletní graf K._n, pak M_G(X) je Hermitův polynom:

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

kde H_n(X) je „pravděpodobnostní Hermitův polynom“ (1) v definici Hermitovy polynomy. Tyto skutečnosti byly pozorovány Godsil (1981).

Li G je les, pak jeho odpovídající polynom je roven charakteristický polynom jeho matice sousedství.

Li G je cesta nebo a cyklus, pak M_G(X) je Čebyševův polynom. V tomto případě μ_G(1,X) je Fibonacciho polynom nebo Lucasův polynom resp.

Doplnění

Odpovídající polynom grafu G s n vrcholy souvisí s doplňkem dvojice (ekvivalentních) vzorců. Jedním z nich je jednoduchá kombinatorická identita Zaslavsky (1981). Druhým je integrální identita kvůli Godsil (1981).

Podobný vztah existuje i pro podgraf G z K._m,n a jeho doplněk v K._m,n. Tento vztah, vzhledem k Riordanovi (1958), byl znám v kontextu neútočení umístění věží a polynomů věže.

Aplikace v chemické informatice

The Hosoyův index grafu G, jeho počet shody, se používá v chemoinformatika jako strukturní deskriptor molekulárního grafu. Lze jej vyhodnotit jako m_G(1) (Gutman 1991 ).

Třetí typ vyhovujícího polynomu představil Farrell (1980) jako verze "acyklického polynomu" používaného v systému Windows chemie.

Výpočetní složitost

Na libovolných grafech, nebo dokonce rovinné grafy, výpočet odpovídajícího polynomu je # P-kompletní (Jerrum 1987 ). Lze jej však vypočítat efektivněji, když je známa další struktura grafu. Zejména výpočet odpovídajícího polynomu na n-vertexové grafy šířka stromu k je fixovatelný parametr: existuje algoritmus, jehož doba běhu pro jakoukoli pevnou konstantu k, je polynomiální v n s exponentem, na kterém nezávisí k (Courcelle, Makowsky & Rotics 2001 Odpovídající polynom grafu s n vrcholy a šířka kliky k lze vypočítat včas n^Ó(k) (Makowsky a kol. 2006 ).

Reference

• Courcelle, B.; Makowsky, J. A .; Rotics, U. (2001), "O pevné složitosti parametrů problémů s výčtem grafů definovatelných v monadické logice druhého řádu" (PDF), Diskrétní aplikovaná matematika, 108 (1–2): 23–52, doi:10.1016 / S0166-218X (00) 00221-3.
• Farrell, E. J. (1980), „Odpovídající polynom a jeho vztah k acyklickému polynomu grafu“, Ars Combinatoria, 9: 221–228.
• Godsil, C.D. (1981), „Hermitovy polynomy a vztah duality pro porovnávání polynomů“, Combinatorica, 1 (3): 257–262, doi:10.1007 / BF02579331.
• Gutman, Ivan (1991), „Polynomials in theory theory“, Bonchev, D .; Rouvray, D. H. (eds.), Teorie chemického grafu: Úvod a základyMatematická chemie 1, Taylor & Francis, str. 133–176, ISBN  978-0-85626-454-2.
• Jerrum, Mark (1987), „Systémy dvourozměrných monomerů a dimerů jsou výpočetně neřešitelné“, Žurnál statistické fyziky, 48 (1): 121–134, doi:10.1007 / BF01010403.
• Makowsky, J. A .; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), „Výpočet polynomů grafů na grafech ohraničené šířky kliky“, Proc. 32. mezinárodní workshop o grafově-teoretických koncepcích v informatice (WG '06) (PDF), Přednášky v informatice, 4271, Springer-Verlag, str. 191–204, doi:10.1007/11917496_18.
• Riordan, Johne (1958), Úvod do kombinatorické analýzy, New York: Wiley.
• Zaslavsky, Thomas (1981), „Doplňkové shodné vektory a vlastnost rozšíření jednotné shody“, European Journal of Combinatorics, 2: 91–103, doi:10.1016 / s0195-6698 (81) 80025-x.