퍼펙트 매칭
Perfect matching그래프 이론에서 그래프의 완벽한 일치는 그래프의 모든 꼭지점을 커버하는 일치가 된다.보다 공식적으로 그래프 G = (V, E)를 보면, G의 완벽한 일치는 E의 부분 집합 M으로, V의 모든 꼭지점이 M의 정확히 하나의 가장자리에 인접해 있다.
완벽한 일치는 1-요인이라고도 한다. 이 용어에 대한 설명은 그래프 요인화를 참조하십시오.일부 문헌에서는 완전 매칭이라는 용어가 사용된다.
모든 완벽한 매칭은 최대 카디널리티 매칭이지만, 그 반대는 사실이 아니다.예를 들어 다음 그래프를 고려해 보십시오.[1]
그래프 (b)에는 6개의 정점이 모두 일치하므로 (크기 3)의 완벽한 일치가 있고, 그래프 (a)와 (c)에는 (크기 2)의 최대 카디널리티 일치가 있는데, 이는 일부 정점이 일치하지 않기 때문이다.
완벽한 매칭도 최소 사이즈 엣지 커버다.완벽한 일치가 있는 경우 일치하는 번호와 에지 커버 번호가 모두 V / 2가 된다.
완벽한 일치는 그래프의 정점 수가 짝수일 때만 발생할 수 있다.거의 완벽한 일치는 정확히 하나의 꼭지점이 일치하지 않는 것이다.이것은 그래프에 정점 수가 홀수일 때에만 발생할 수 있으며, 이러한 일치는 최대치여야 한다.위의 그림에서 부분(c)은 거의 완벽한 일치를 보여준다.그래프의 모든 꼭지점에 대해 해당 꼭지점만 생략하는 거의 완벽한 일치가 있는 경우 그래프를 요인 임계치라고도 한다.
특성화
홀의 결혼 정리는 완벽한 조화를 이루는 초당적 그래프의 특징을 제공한다.
Tutte 정리는 임의의 그래프에 특성화를 제공한다.
완벽한 매칭은 1-정규 서브그래프, 즉 1-요인이다.일반적으로 spanning k-regular subgraph는 k-factor이다.
하사니 몬파레드와 말리크가 완벽한 일치를 갖기 위한 그래프의 스펙트럼 특성화는 다음과 같다.Let be a graph on even vertices and be distinct nonzero purely imaginary numbers.만일 실제로 교대 행렬 ,\pm \lambda _{\frac{n}{2}}}.[2]그러나(시 그래프 G{G\displaystyle}과 eigenvalues λ 1,±λ 2,…,±λ n2{\displaystyle \pm \lambda_{1},\pm \lambda _{2},\ldots도±을 가진{A\displaystyle}그럼 G{G\displaystyle}완벽한 일치하는 가지고 있다.융점) 실제 대칭 또는 스큐 대칭 행렬의 n {\displaystyle n n의 정점과 가장자리가 의 0이 아닌 오프대칭 항목으로 주어진다
연산
그래프가 완벽한 일치를 허용하는지 여부를 결정하는 것은 최대 카디널리티 일치를 찾기 위한 알고리즘을 사용하여 다항식 시간에 수행될 수 있다.
그러나 초당적 그래프에서도 완벽한 일치의 수를 세는 것은 #P-완전이다.임의 0–1 매트릭스(또 다른 #P-완전한 문제)의 영구적 계산은 주어진 매트릭스를 생체역량 매트릭스로 하는 양당성 그래프에서 완벽한 매칭 수를 계산하는 것과 같기 때문이다.
Kastelyn의 주목할 만한 정리는 평면 그래프의 완벽한 일치의 수는 FKT 알고리즘을 통해 다항 시간 내에 정확하게 계산할 수 있다고 말한다.
완전한 그래프 Kn (n 짝수)의 완벽한 일치 횟수는 이중 요인(( - [3]
완벽한 매칭 폴리토프
그래프의 완벽한 일치 폴리토프는 R의 E 폴리토프인데, 각 모서리가 완벽한 매칭의 발생 벡터인 것이다.
참고 항목
참조
- ^ 앨런 기번스, 알고리즘 그래프 이론, 캠브리지 대학 출판부, 1985년 5장.
- ^ Keivan Hassani Monfared와 Sudipta Mallik, Organization 3.6, Graphics 3.6, 선형 대수 및 응용 프로그램 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
- ^ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
