일치 다항식

그래프 이론과 조합론의 수학 분야에서 일치하는 다항식(Acyclic polyomial)은 그래프에서 다양한 크기의 일치수의 생성 함수다.대수 그래프 이론에서 연구된 여러 그래프 다항식 중 하나이다.

정의

일치하는 몇 가지 다른 유형의 다항식이 정의되었다.G를 정점이 n인 그래프로 하고 m을_k k-edge 일치 항목 수로 한다.

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}.}$

세 번째 정의는 다항식이다.

${\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k^{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}).}$

다른 다항식 연결

일치하는 다항식의 첫 번째 유형은 루크 다항식의 직접 일반화다.

일치하는 두 번째 유형의 다항식은 직교 다항식과의 연결이 현저하다.예를 들어, 전체 초당적 그래프인 G = K인_m,n 경우, 일치하는 두 번째 유형의 다항식은 다음 ID에 의해 일반화된 Laguerre_n^α 다항식 L(x)와 관련된다.

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

G가 전체 그래프 K인_n 경우 M_G(x)은 Hermite 다항식:

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

여기서 H_n(x)는 Hermite 다항식의 정의에서 "확률론자의 Hermite 다항식"(1)이다.이러한 사실은 고딜(1981년)에 의해 관찰되었다.

G가 포리스트인 경우, 일치하는 다항식은 인접 행렬의 특성 다항식과 동일하다.

G가 경로나 사이클이라면 M(x)은_G 체비셰프 다항식이다.이 경우 μ_G(1,x)는 각각 피보나치 다항식 또는 루카스 다항식이다.

보완

정점이 n개인 그래프 G의 일치하는 다항식은 한 쌍의 (동일한) 공식에 의해 그 보완의 그것과 관련이 있다.그 중 하나는 자슬라프스키(1981년)로 인한 단순한 결합 정체성이다.다른 하나는 고딜(1981년)으로 인해 불가결한 정체성이다.

K의_m,n 서브그래프 G와 K의_m,n 그것의 보완과 유사한 관계가 있다.이 관계는 리오르단(1958년)으로 인해 비공격 루크 포지션과 루크 다항식의 맥락에서 알려졌다.

화학 정보학에서의 응용

일치 횟수인 G 그래프의 호소야 지수는 화학정보학에서 분자 그래프의 구조적 설명자로 사용된다.m_G(1)으로 평가할 수 있다(Gutman 1991).

일치 다항식의 세 번째 유형은 파렐(1980년)이 화학에서 사용하는 "순환 다항식"의 한 버전으로 도입했다.

계산 복잡성

임의 그래프 또는 평면 그래프에서 일치하는 다항식 계산은 #P-완전하다(Jerrum 1987).그러나 그래프에 대한 추가 구조가 알려지면 더 효율적으로 계산할 수 있다.특히, treewidth k의 n-vertex 그래프에 일치하는 다항식을 계산하는 것은 고정 매개변수 트랙터블: 어떤 고정 상수 k에 대해 실행 시간이 k에 의존하지 않는 지수(Courcelle, Makowsky & Rotics 2001)를 가진 n의 다항식 알고리즘이 존재한다.n 정점과 clique-width k가 있는 그래프의 일치하는 다항식은 시간 n으로^O(k) 계산할 수 있다(Makowsky et al. 2006).

참조

• Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic" (PDF), Discrete Applied Mathematics, 108 (1–2): 23–52, doi:10.1016/S0166-218X(00)00221-3.
• Farrell, E. J. (1980), "The matching polynomial and its relation to the acyclic polynomial of a graph", Ars Combinatoria, 9: 221–228.
• Godsil, C.D. (1981), "Hermite polynomials and a duality relation for matchings polynomials", Combinatorica, 1 (3): 257–262, doi:10.1007/BF02579331.
• Gutman, Ivan (1991), "Polynomials in graph theory", in Bonchev, D.; Rouvray, D. H. (eds.), Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry, vol. 1, Taylor & Francis, pp. 133–176, ISBN 978-0-85626-454-2.
• Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, doi:10.1007/BF01010403.
• Makowsky, J. A.; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Computing graph polynomials on graphs of bounded clique-width", 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.
• Riordan, John (1958), An Introduction to Combinatorial Analysis, New York: Wiley.
• Zaslavsky, Thomas (1981), "Complementary matching vectors and the uniform matching extension property", European Journal of Combinatorics, 2: 91–103, doi:10.1016/s0195-6698(81)80025-x.