因子 (圖論)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/03/Desargues_graph_3color_edge.svg/200px-Desargues_graph_3color_edge.svg.png)
在圖論中,因子是某個圖G的生成子圖,並且是與G相同的頂點的子圖。通常因子名稱前面會加一個數,例如k-因子,表示每個頂點的度均為k,換句話說即該因子為k-正則生成子圖。將某個圖G的邊分解為若干個互斥的k-因子之動作稱為k-分解。類似於除法整除的概念,如果圖G可以被k-分解,則G可以稱為k-因子分解圖[1](類似於G可被k整除的概念),而圖與因子間關係則可以類比為數與因數。特別地,將任意圖1-分解為1-因子是一種完美匹配,因為其結果括了圖G中原來的所有頂點;此外,若將一個k-正則圖進行1-分解則與將該k-正則圖進行k種顏色的邊着色等價。2-因子則是包含圖中的所有頂點之環的集合。
參考文獻
- Bondy, John Adrian; Murty, U. S. R., Graph Theory with Applications, North-Holland, 1976 [2019-05-05], ISBN 0-444-19451-7, (原始內容存檔於2012-06-16), Section 5.1: "Matchings".
- Chetwynd, A. G.; Hilton, A. J. W., Regular graphs of high degree are 1-factorizable, Proceedings of the London Mathematical Society, 1985, 50 (2): 193–206, doi:10.1112/plms/s3-50.2.193.
- Diestel, Reinhard, Graph Theory 3rd, Springer, 2005, ISBN 3-540-26182-6, Chapter 2: "Matching, covering and packing". Electronic edition(頁面存檔備份,存於互聯網檔案館).
- Harary, Frank, Graph Theory, Addison-Wesley, 1969, ISBN 0-201-02787-9, Chapter 9: "Factorization".
- Hazewinkel, Michiel (編), One-factorization, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- Niessen, Thomas, How to find overfull subgraphs in graphs with large maximum degree, Discrete Applied Mathematics, 1994, 51 (1–2): 117–125, doi:10.1016/0166-218X(94)90101-5.
- Perkovic, L.; Reed, B., Edge coloring regular graphs of high degree, Discrete Mathematics, 1997,, 165–166: 567–578, doi:10.1016/S0012-365X(96)00202-6.
- Petersen, Julius, Die Theorie der regulären graphs, Acta Mathematica, 1891, 15: 193–220, doi:10.1007/BF02392606.
- West, Douglas B. 1-Factorization Conjecture (1985?). Open Problems – Graph Theory and Combinatorics. [2010-01-09]. (原始內容存檔於2009-08-13).
- 埃里克·韋斯坦因. Graph Factor. MathWorld.
- 埃里克·韋斯坦因. k-Factor. MathWorld.
- 埃里克·韋斯坦因. k-Factorable Graph. MathWorld.
- ^ 因子分解圖 factorable graph. 國家教育研究院. [2019-05-05]. (原始內容存檔於2021-09-28).