因子 (圖論)

在圖論中，因子是某個圖G的生成子圖，並且是與G相同的頂點的子圖。通常因子名稱前面會加一個數，例如k-因子，表示每個頂點的度均為k，換句話說即該因子為k-正則生成子圖。將某個圖G的邊分解為若干個互斥的k-因子之動作稱為k-分解。類似於除法整除的概念，如果圖G可以被k-分解，則G可以稱為k-因子分解圖（類似於G可被k整除的概念），而圖與因子間關係則可以類比為數與因數。特別地，將任意圖1-分解為1-因子是一種完美匹配，因為其結果括了圖G中原來的所有頂點；此外，若將一個k-正則圖進行1-分解則與將該k-正則圖進行k種顏色的等價。2-因子則是包含圖中的所有頂點之環的集合。