Faktorisasi

Definisi Suatu factor dari graf G adalah subgraf merentang dari G.

Definisi Diketahui bahwa G₁, G₁, . . ., G_n merupakan pasangan subgraf merentang terpisah–sisi (edge–disjoint) dari G sedemikian sehingga E(G_i) = E(G). Maka G dikatakan factorable atau difaktor menjadi subgraf – subgraf (factored into subgraphs) atau factors G₁, G₁, . . ., G_n, dan ditulis G = G₁ G₂ . . . G_n. Ekspresi gabungan tersebut disebut faktorisasi (factorization) dari G menjadi factors G₁, G₁, . . ., G_n.

Definisi Suatu r–regular factor dari graf G dikatakan sebagai r–factor dari G. Maka, graf G mempunyai 1–factor jika dan hanya jika mengandung matching sempurna.

Definisi Graf G dikatakan r–factorable jika terdapat suatu factorization dari graf G menjadi r–factors.

Dekomposisi sisi graf merupakan penggambaran pemisahan himpunan sisi dari suatu graf menjadi sejumlah disjoint subset. Jika setiap sisi G dapat dikelompokkan menjadi sejumlah 1–factor yang disjoint subset maka G dikatakan memiliki 1–factorization.