그래프 인자화
Graph factorization
그래프 이론에서 그래프 G의 인자는 스패닝 서브그래프, 즉 G와 동일한 정점을 갖는 서브그래프다. 그래프의 k-요인은 스패닝 k-정규 서브그래프이며, k-요인화는 그래프의 가장자리를 분리 k-요인으로 분할한다.그래프 G는 k-요인화를 인정할 경우 k-요인화가 가능하다고 한다.특히 1-요인은 완벽한 매칭이며, k-정규 그래프의 1-요인화는 k-컬러로 엣지 컬러링이다.2-요인은 그래프의 모든 정점에 걸쳐 있는 사이클 모음입니다.
1-화
그래프가 1-요인(즉, 1-요인화)이면 정규 그래프여야 한다.그러나 모든 일반 그래프가 1-요인성인 것은 아니다.k-규칙 그래프는 색도 지수 k를 갖는 경우 1-요인할 수 있다. 이러한 그래프의 예는 다음과 같다.
- 정기적인 초당적 그래프.[1]홀의 결혼 정리는 k-정기 양분 그래프가 완벽한 매칭을 담고 있음을 보여주는 데 사용될 수 있다.그런 다음 완벽한 일치를 제거하여 (k - 1)정기적인 초당적 그래프를 얻을 수 있고, 동일한 추론을 반복적으로 적용할 수 있다.
- 노드 수가 짝수인 전체 그래프(아래 참조)[2]
그러나 색도 지수 k + 1을 갖는 k-규칙 그래프도 있으며, 이러한 그래프는 1-요인성이 아니다. 이러한 그래프의 예는 다음과 같다.
- 노드 수가 홀수인 일반 그래프.
- 피터슨 그래프.
전체 그래프
완전한 그래프의 1-요소는 라운드 로빈 토너먼트에서 쌍을 이루는 것에 해당한다.완전한 그래프의 1-요인화는 완전한 하이퍼그래프의 1-요인에 관한 바라나이 정리의 특별한 경우다.
정점 수에 대한 완전한 그래프의 1-요인화를 구성하는 한 가지 방법에는 정점 중 하나를 제외한 모든 정점을 원 위에 놓고 나머지 정점을 원의 중심에 두는 것이 포함된다.이 정점의 배열로, 그래프의 1-요소를 구성하는 한 가지 방법은 중심에서 e에 수직인 선에 놓여 있는 모든 가능한 가장자리와 함께 하나의 다각형 정점까지 에지 e를 선택하는 것이다.이러한 방식으로 구성할 수 있는 1-요인은 그래프의 1-요인을 형성한다.
K2, K4, K6, K, K8, ...의 구별되는 1-요인화 수는 1, 1, 6, 6240, 1225566720, 252282619805368320, 987586558163838383040, ...OEIS: A000438.
1-추측
G를 2n 노드가 있는 k-정규 그래프로 하자.k가 충분히 크면, G는 1-유효성이어야 한다고 알려져 있다.
- k = 2n - 1이면 G는 전체 그래프 K이므로2n 1-요인(위 참조)
- k = 2n - 2인 경우 K에서2n 완벽한 일치를 제거하여 G를 구성할 수 있다.다시 말하지만, G는 1-유효성이 있다.
- Chetwynd & Hilton(1985)은 k가 12n/7이면 G가 1-factorable이라는 것을 보여준다.
1-요인화 추측이란[3] k ≈ n이면 충분하다고 말하는 오랜 추측이다.정확한 표현으로 추측하면 다음과 같다.
- n이 홀수이고 k ≥ n이면 G는 1-요인이다.n이 짝수이고 k ≥ n - 1이면 G는 1-요인이다.
과도한 추측은 1-요인화 추측을 내포하고 있다.
완벽한 1-요인화
1-요인화의 완벽한 한 쌍은 조합이 해밀턴의 주기를 유도하는 1-요인 한 쌍이다.
그래프의 완벽한 1-요인화(P1F)는 모든 1-요인 쌍이 완벽한 쌍이라는 특성을 갖는 1-요인화다.완벽한 1-요인화는 완벽한안 된다 혼동해서는 일치(일-요인이라고도 함)와.
1964년, 안톤 코치히는 n 2 2의 완전한 그래프 K가2n 완벽한 1-요인화를 가지고 있다고 추측했다.지금까지 다음과 같은 그래프는 완벽한 1-요인을 갖는 것으로 알려져 있다.[4]
- p가 이상한 소수인 완전 그래프 K의2p 무한 계열(앤더슨과 나카무라에 의해 독립적으로),
- p가 이상한 소수인 완전 그래프 K의p + 1 무한 계열
- 그리고2n 2n additional {16, 28, 36, 40, 50, 126, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792를 포함하는 산발적인 추가 결과.몇몇 새로운 결과들이 여기에서 수집된다.
완전한 그래프 K가n + 1 완벽한 1-요인화를 가지고 있다면 완전한 양분 그래프 K도n,n 완벽한 1-요인화를 가지고 있다.[5]
2차화
그래프가 2-요인성인 경우 일부 정수 k의 경우 2k-정규형이어야 한다.Julius Petersen은 1891년에 필요한 조건도 충분하다는 것을 보여주었다: 어떤 2k-정규 그래프도 2-사실화 가능하다.[6]
연결된 그래프가 2k-정규적이고 짝수 수의 가장자리를 갖는 경우 두 요인을 각각 오일러 투어의 가장자리의 교차 부분 집합으로 선택하여 k-요인할 수도 있다.[7]이것은 연결된 그래프에만 적용된다. 연결되지 않은 계수는 홀수 사이클 또는 K2k+1 복사본의 분리 결합을 포함한다.
Oberwolfach 문제는 완전한 그래프를 이소모르픽 하위그래프로 2-요인화하는 것과 관련이 있다.어떤 서브그래프가 가능한지 묻는다.이것은 서브그래프가 연결되었을 때 알려져 있지만(이 경우는 해밀턴 사이클이고 이 특수한 경우는 해밀턴 분해의 문제) 일반적인 경우는 미해결 상태로 남아 있다.
메모들
- ^ 하라리(1969), 정리 9.2, 페이지 85.Diestel(2005), Corollary 2.1.3, 페이지 37.
- ^ 하라리(1969), 정리 9.1, 페이지 85.
- ^ 체트윈드&힐튼(1985년).니센(1994년).페르코비치 & 리드(1997년).서쪽.
- ^ Wallis, W. D. (1997), "16. Perfect Factorizations", One-factorizations, Mathematics and Its Applications, vol. 390 (1 ed.), Springer US, p. 125, doi:10.1007/978-1-4757-2564-3_16, ISBN 978-0-7923-4323-3
- ^ Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (May 2002), "A Family of Perfect Factorisations of Complete Bipartite Graphs", Journal of Combinatorial Theory, A, 98 (2): 328–342, doi:10.1006/jcta.2001.3240, ISSN 0097-3165
- ^ 피터슨(1891), §9, 페이지 200.하라리(1969), 정리 9.9, 페이지 90.증거는 Diestel(2005), Corollary 2.1.5, 페이지 39를 참조한다.
- ^ 피터슨(1891), §6, 페이지 198.
참조
- Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, archived from the original on 2010-04-13, retrieved 2019-12-18, 섹션 5.1: "일치".
- Chetwynd, A. G.; Hilton, A. J. W. (1985), "Regular graphs of high degree are 1-factorizable", Proceedings of the London Mathematical Society, 50 (2): 193–206, doi:10.1112/plms/s3-50.2.193.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, 2장 : "매칭, 덮개, 포장"전자판.
- Harary, Frank (1969), Graph Theory, Addison-Wesley, ISBN 0-201-02787-9, 9장: "사실화"
- "One-factorization", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Niessen, Thomas (1994), "How to find overfull subgraphs in graphs with large maximum degree", Discrete Applied Mathematics, 51 (1–2): 117–125, doi:10.1016/0166-218X(94)90101-5.
- Perkovic, L.; Reed, B. (1997), "Edge coloring regular graphs of high degree", Discrete Mathematics, 165–166: 567–578, doi:10.1016/S0012-365X(96)00202-6.
- Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica, 15: 193–220, doi:10.1007/BF02392606.
- West, Douglas B. "1-Factorization Conjecture (1985?)". Open Problems – Graph Theory and Combinatorics. Retrieved 2010-01-09.
- Weisstein, Eric W. "Graph Factor". MathWorld.
- Weisstein, Eric W. "k-Factor". MathWorld.
- Weisstein, Eric W. "k-Factorable Graph". MathWorld.
추가 읽기
- Plummer, Michael D. (2007), "Graph factors and factorization: 1985–2003: A survey", Discrete Mathematics, 307 (7–8): 791–821, doi:10.1016/j.disc.2005.11.059.
