Faktorisasi Graf baru yang dihasilkan dari pemetaan titik graf sikel pada bilangan bulat positif

ABSTRAK

Faktor merupakan subgraf merentang dari suatu graf. Subgraf merentang terdiri dari himpunan pasangan titik yang tidak saling terhubung dan selalu berbentuk graf beraturan satu, ini dapat disebut sebagai graf yang memiliki 1-faktor. Ketika himpunan titik dari graf sikel (Cn) dipetakan pada bilangan bulat positif yang dibatasi oleh derajatnya maka akan menghasilakan graf baru Cn yang memiliki 1-faktor dengan ciri-ciri fungsi yang menghasilkan graf baru Cn* yang dihasilkan dari graf Cn akan memiliki 1-faktor.

Adapun langkah-langkah untuk memperoleh hasil dari penelitian ini adalah : (1) menggambarkan graf sikel Cn, (2) menentukan kemungkinan-kemungkinan dari fungsi ..(Cn)→ {1,2}, {3} menentukan D(x), (4) menentukan s(x) dan S(x), (5) menentukan graf baru Cn* = (V*, E*), (6) faktorisasi graf baru Cn* dengan menunjukkan himpunan pasangannya.

Hasil dari penelitian ini adalah ciri-ciri fungsi yang menghasilkan graf baru Cn* yang memiliki 1-faktor dengan membedakan untuk banyak titik ganjil dan banyak titik genap sebagaimana berikut, 1. Fungsi dengan banyak n atau satu titik dipetakan ke 2 untuk n ganjil. 2. Fungsi dengan banyak n titik dipetakan ke 2 atau 1 untuk n genap.

Bagi penelitian selanjutnya diharapkan dapat mengembangkan penelitian ini untuk graf lainnya.