Faktorisasi Graf Baru Yang Dihasilkan Dari Pemetaan Titik Graf Sikel Pada Bilangan Bulat Positif

Abstract

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 menghasilkan graf baru Cn* yang memiliki 1-faktor dengan ciri-ciri fungsi tertentu. Tujuan penelitian ini adalah untuk mengetahui 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) menggambar graf sikel Cn, (2) menentukan kemungkinan-kemungkinan dari fungsi f(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.