FAKTORISASI GRAF BARU YANG DIHASILKAN DARI PEMETAAN TITIK GRAF SIKEL PADA BILANGAN BULAT POSITIF
Nova Nevisa Auliatul Faizah 1 , H. Wahyu H. Irawan 2
1 Mahasiswa Jurusan Matematika, Fakultas Sains dan Teknologi, UIN Maulana Malik Ibrahim Malang
2 Dosen Jurusan Matematika, Fakultas Sains dan Teknologi, UIN Maulana Malik Ibrahim Malang E-mail: novanevisa@yahoo.com , henky_lily@yahoo.com

## 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 𝐶 𝑛 dipetakan pada bilangan bulat positif  yang  dibatasi  oleh  derajatnya  maka  akan  menghasilkan  graf  baru 𝐶 𝑛 ∗ yang  memiliki  1-faktor dengan  ciri-ciri  fungsi  tertentu.  Tujuan  penelitian  ini  adalah  untuk  mengetahui  ciri-ciri  fungsi  yang menghasilkan graf baru 𝐶 𝑛 ∗ yang dihasilkan dari graf 𝐶 𝑛 akan memiliki 1-faktor.
Adapun Langkah-langkah untuk memperoleh hasil dari penelitian ini adalah: (1) menggambar graf sikel 𝐶 𝑛 , (2) menentukan kemungkinan-kemungkinan dari fungsi 𝑓(𝐶 𝑛 ) → {1,2} , (3) menentukan 𝐷(𝑥) , (4) menentukan 𝑠(𝑥) dan 𝑆(𝑥) , (5) Menentukan graf baru 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) , (6) Faktorisasi graf baru 𝐶 𝑛 ∗ dengan menunjukkan himpunan pasangannya.
Hasil  dari  penelitian  ini  adalah  ciri-ciri  fungsi  yang  menghasilkan  graf  baru 𝐶 𝑛 ∗ yang  memiliki  1- faktor dengan membedakan untuk banyak titik ganjil dan banyak titik genap sebagaimana berikut: 1. Fungsi dengan banyak 𝑛 atau satu titik dipetakan ke 2 untuk 𝑛 ganjil 2. Fungsi dengan banyak 𝑛 titik dipetakan ke 2 atau 1 untuk 𝑛 genap
Bagi penelitian selanjutnya diharapkan dapat mengembangkan penelitian ini untuk graf lainnya.
Kata Kunci: Faktorisasi, 1-faktor, f-faktor, Graf Sikel (𝐶 𝑛 )

## ABSTRACT
Factor is a spanning subgraph of a graph. Spanning subgraph consist of a set of couples of vertices that  disconnected  each  other  and  always  organized  as  regular  graph  one,  called  as  a  graph  that  has  1- factor. When a set of points of Cycle Graph (𝐶 𝑛 ) mapped on a positive integerbordered by its degree, it will produce a new graph of 𝐶 𝑛 ∗ that has 1-factor with the particular function’s characteristics. The aim of this study  is  to  determine  the  function’s  characteristics  that  produc  a  new  graph  of 𝐶 𝑛 ∗ obtained  from 𝐶 𝑛 of having 1-factor.
Therefore, the steps to provide the result of the research are: (1) drawing the Cycle Graph 𝐶 𝑛 , (2) Determining  the  possibility  function  of 𝑓(𝐶 𝑛 ) → {1, 2} ,  (3)  Determining 𝐷(𝑥) ,  (4)  Determining 𝑠(𝑥) dan 𝑆(𝑥) ,  (5)  Determining  a  new  graph 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) ,  (6)  Factorizing  the  new  graph 𝐶 𝑛 ∗ with  showing  a  set matching.
The results of this research are the function’s characteristics that producing  a new graph of 𝐶 𝑛 ∗ of having 1-factor with differentiate for many odd points and even points as follow: 1. A function of 𝑛 or one vertex has mapped to 2 for 𝑛 odd 2. A function of 𝑛 vertices is mapped to 2 or 1 for 𝑛 even.
For the further research is expected to another graph.
Keyword: Factoritation, 1-factor, f-factor, Graph Cycle (𝐶 𝑛 )

## PENDAHULUAN
Teori  graf  merupakan  salah  satu  cabang ilmu  Matematika  yang  sebenarnya  sudah  ada sejak  dua  ratus  tahun  yang  lalu.  Graf  digunakan untuk mempresentasikan objek-objek diskrit dan
hubungan antara objek-objek tersebut. Representasi  visual  dari  graf  adalah  dengan menyatakan  objek  sebagai  noktah,  bulatan,  atau titik, sedangkan hubungan antara objek dinyatakan  dengan  garis  (Munir,  2012).  Secara sistematis, menurut (Chartrand & Lesniak, 1986)
graf  didefinisikan  sebagai  himpunan  titik 𝑉(𝐺) yang  tak  kosong  dan  himpunan  sisi 𝐸(𝐺) yang mungkin  kosong  yang  mana  keduanya  saling berhubungan.
Dalam  perkembangannya,  jurnal  pertama yang ditulis tentang teori graf muncul pada tahun 1736  oleh  matematikawan  terkenal  dari  Swiss bernama Euler (Budayasa, 2007). Perkembangan teori  ini  tidak  hanya  secara  teoritis,  tetapi  juga secara  aplikatif.  Dalam  perkembangan  teoritis, konsep-konsep yang ada dapat dibuktikan secara deduksi  dan  induksi.  Sedangkan  perkembangan secara  aplikatif  merupakan  terapan  dari  hasil teoritis  sebagai  penyelesaian  dari  suatu  masalah nyata.
Salah  satu  topik  yang  menarik  adalah membahas tentang faktorisasi . Menurut (Chartrand  &  Lesniak,  1986),  faktor  adalah subgraf merentang dari suatu graf dan faktorisasi adalah  penjumlahan  sisi-sisi  yang  disjoint  dari faktor-faktor  suatu  graf.  Selanjutnya r-reguler faktor  dapat  dinyatakan  sebagai r-faktor. Karena faktorisasi dari suatu graf akan selalu menghasilkan  faktor-faktor  graf  yang  beraturan satu,  maka graf  tersebut  dapat  dinyatakan memiliki
1-faktor .
Sedangkan pasangan sempurna  adalah  himpunan  pasangan  titik  yang membentuk sisi pada suatu graf yang tidak saling terhubung  langsung.  Melihat  definisi  pasangan sempurna  ini  dapat  mewakili  definisi  dari  faktor maka  dapat  dinyatakan  bahwa  suatu  graf  yang mengandung  pasangan  sempurna  akan  memiliki 1-faktor.
Sejauh  ini  masalah  yang  sudah  dikaji tentang faktorisasi adalah faktorisasi graf komplit oleh Vera Mandailina tahun 2009 dan faktorisasi graf  beraturan- r dengan  order  genap  oleh  Asna Bariroh  tahun  2010,  kedua  masalah  ini  hanya membahas  tentang  faktorisasi  pada  graf  yang hanya  menghasilkan    berapa  banyak  faktor  pada suatu  graf.  Jika  permasalahan  faktorisasi  ini dikaitkan dengan sebuah pemetaan dari himpunan  titik  suatu  graf  pada  bilangan  bulat positif  yang  dibatasi  oleh  derajatnya  maka  akan berakibat terbentuknya graf baru yang mana graf baru tersebut tidak selalu memiliki 1-faktor. Oleh karena itu peneliti tertarik untuk mengembangkannya lebih lanjut.

## METODE PENELITIAN
Penelitian ini bertujuan untuk mengembangkan permasalahan tentang faktorisasi,  sehingga  metode  penelitian  ini merupakan  metode    kepustakaan,  pendekatan yang  digunakan  ialah  pendekatan  kualitatif  yang pada  umumnya  tidak  terjun  ke  lapangan  dalam pencarian  dan  pengumpulan  sumber  datanya. Sedangkan  pola  pembahasannya  dari  induktif  ke deduktif,  hal  ini  berarti  pembahasannya  dimulai dari  hal-hal  khusus    menuju  pada  hal-hal  umum
( generalisasi ).  Secara  garis  besar  langkah penelitian ini sebagai berikut:
1) Menggambar  graf  sikel (𝐶 𝑛 ) dengan 𝑛 bilangan ganjil.
2) Menentukan  fungsi 𝑓: 𝑉(𝐶 𝑛 ) → 𝑍 + dengan ketentuan 𝑓(𝑥) ≤ 𝑑(𝑥) ∀𝑥 ∈ 𝑉(𝐶 𝑛 ) ,  karena derajat  pada  graf  sikel (𝐶 𝑛 ) selalu  dua  maka himpunan 𝑍 + = {1,2} sehingga  fungsinya dapat  ditulis 𝑓: 𝑉(𝐶 𝑛 ) → {1,2} .  Kemudian menuliskan  semua  kemungkinan  pemetaan yang terjadi.
3) Menentukan 𝐷(𝑥) = {𝑥 𝛼 |𝛼 ∈ 𝐸(𝐶 𝑛 ), 𝛼 adalah sisi  yang  terkait  langsung  dengan 𝑥; ∀𝑥 ∈ 𝑉(𝐶 𝑛 )} . 4) Menentukan 𝑠(𝑥) = 𝑑(𝑥) − 𝑓(𝑥) ∀𝑥 ∈ 𝑉(𝐶 𝑛 ) yang  didefinisikan  sebagai  bilangan  yang dihasilkan  dari  selisih  antara  derajat  titik  di graf  sikel (𝐶 𝑛 ) dan  bilangan  bulat  positif  dari fungsi 𝑓: 𝑉(𝐶 𝑛 ) → 𝑍 + ,  kemudian  menentukan 𝑆(𝑥) = {𝑥(𝑖)|1 ≤ 𝑖 ≤ 𝑠(𝑥)} yang berupa himpunan titik dari 𝑠(𝑥) .
5) Menentukan  graf  baru 𝐶 𝑛 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) ,  yang masing-masing  dari 𝑉 ⋆ dan 𝐸 ⋆ didefinisikan sebagai berikut:
a. 𝑉 ⋆ = 𝑉 ⋆ 1 ⋃𝑉 ⋆ 2 ; 𝑉 ⋆ 1 = ⋃ 𝐷(𝑥) 𝑥∈𝑉 (𝐶𝑛) ; 𝑉 ⋆ 2 = ⋃ 𝑆(𝑥) 𝑥∈𝑉 (𝐶𝑛)
b. 𝐸 ⋆ = 𝐸 ⋆ 1 ⋃𝐸 ⋆ 2 ; 𝐸 ⋆ 1 = {𝑥 𝛼 𝑦 𝛼 |𝛼 = 𝑥𝑦 ∈ 𝐸(𝐶 𝑛 ) ; 𝐸 ⋆ 2 = {𝑢𝑣|𝑢 ∈ 𝐷(𝑥) 𝑑𝑎𝑛 𝑣 ∈
𝑆(𝑥), 𝑥 ∈ 𝑉 (𝐶 𝑛 )} .
6) Faktorisasi graf baru 𝐶 𝑛 ⋆ .
7) Membuat  suatu  konjektur  berdasarkan  ciri- ciri yang didapatkan.
8) Merumuskan konjektur sebagai suatu teorema,  kemudian  dibuktikan  kebenarannya sehingga  dapat  dinyatakan  benar  secara umum.
9) Menuliskan laporan penelitian.

## TEORI DASAR
1. Definisi Graf Sikel Sikel dengan  3  atau  lebih  titik  adalah  suatu graf  sederhana  yang  titiknya  tersusun mengikuti putaran seperti suatu jalan dengan dua  titik  yang  terhubung  langsung  jika keduanya  berturutan  dan  tidak  terhubung langsung dengan lainnya. Sebuah sikel dengan satu  titik  disebut  loop,  dan  sikel  dengan  dua titik  yang  dihubungkan  oleh  dua  sisi  disebut sisi rangkap (Bondy & Murty, 2008).
Contoh 2.2: Graf sikel 𝐶 𝑛 dengan 𝑛 = 3,4,5,6
Gambar 1  Graf 𝐶 3 , 𝐶 4 , 𝐶 5 , 𝐶 6

## 2. Definisi Subgraf Merentang
Subgraf H dari graf G yang memiliki himpunan titik  yang  sama  pada G atau  jika  subgraf H dengan 𝑉(𝐻) = 𝑉(𝐺) ,  maka H disebut spanning  subgraf (Subgraf  merentang)  dari G (Chartrand & Lesniak, 1986).
Dari  definisi  sub  graf  merentang, peneliti memberikan contoh sebagai berikut:

## G                               G 1
Gambar 2 Subgraf Merentang Graf G 1 dari Graf G
3. Definisi Matching
Matching (Pasangan)  pada  graf G adalah himpunan  pasangan  titik  yang  membentuk sisi  pada  graf G yang  tidak  saling  terhubung langsung (Chartrand & Lesniak, 1986).
4. Definisi Perfect Matching
M disebut sebagai perfect matching (pasangan  sempurna)  pada  graf G ,  jika M merupakan  suatu  pasangan  pada  graf G ,  dan semua  sisi  di M menutup  semua  titik  di G (Bondy & Murty, 2008).
5. Definisi Perfect Matching M disebut sebagai perfect matching (pasangan  sempurna)  pada  graf G ,  jika M merupakan  suatu  pasangan  pada  graf G ,  dan semua  sisi  di M menutup  semua  titik  di G (Bondy & Murty, 2008) . Contoh  diberikan  graf G dan  graf H sebagai berikut:
𝐺 𝐻 Gambar 3 Graf 𝐺 dan graf 𝐻
Dari  Gambar  3  Graf 𝐺 dengan 𝑀 = {𝑒 1 , 𝑒 4 } merupakan pasangan tidak sempurna  dan graf 𝐻 dengan 𝑀 = {𝑒 1 , 𝑒 3 , 𝑒 5 } adalah pasangan sempurna.
6. Definisi Faktor Faktor  dari  graf G adalah  suatu  subgraf merentang dari graf G (Chartrand & Lesniak, 1986).
Jika 𝐺 1 , 𝐺 2 , … , 𝐺 𝑛 adalah  faktor  yang  disjoint sisi pada graf G sedemikian hingga ⋃ 𝑖=1 𝑛 𝐸(𝐺 𝑖 ) = 𝐸(𝐺) dimana 𝐺 =   𝐺 1 ⊕   𝐺 2 ⊕ …  ⊕   𝐺 𝑛 disebut  sebagai  penjumlahan  sisi dari faktor-faktor 𝐺 1 , 𝐺 2 , … , 𝐺 𝑛 .

## 7. Definisi Faktorisasi
Faktorisasi  dari  graf G adalah  penjumlahan sisi  dari  faktor-faktor  graf  (Chartrand  & Lesniak, 1986).
Suatu r-reguler faktor  dari  graf G dapat dinyatakan  sebagai r-faktor dari G .  Oleh karena  itu,  suatu  graf  memiliki  1-faktor jika dan  hanya  jika  mengandung  suatu perfect matching. contoh faktorisasi dari graf G sebagai berikut: G                   G 1 G 2 G 3
Gambar 2.9 Garf G dan Faktor-faktornya
Berdasarkan buku Extremal Graph Theory peneliti menyimpulkan bahwa untuk membangun  graf  baru 𝐺 ∗ dari  graf 𝐺 yang memiliki 1-faktor adalah dengan langkah-langkah sebagai berikut:
1) Menentukan  fungsi 𝑓: 𝑉(𝐺) → 𝑍 + dengan ketentuan 𝑓(𝑥) ≤ 𝑑(𝑥) ∀𝑥 ∈ 𝑉(𝐺) .
2) Menentukan 𝐷(𝑥) = {𝑥 𝛼 |𝛼 ∈ 𝐸(𝐺), 𝛼 adalah sisi  yang  terkait  langsung  dengan 𝑥; ∀𝑥 ∈ 𝑉(𝐺)} .
3) Menentukan 𝑠(𝑥) = 𝑑(𝑥) − 𝑓(𝑥) ∀𝑥 ∈ 𝑉(𝐺)) , kemudian  menentukan 𝑆(𝑥) = {𝑥(𝑖)|1 ≤ 𝑖 ≤ 𝑠(𝑥)} .
4) Menentukan  graf  baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) dengan 𝑉 ⋆ dan 𝐸 ⋆ didefinisikan sebagai berikut: a. 𝑉 ⋆ = {𝑉 ⋆ 1 ⋃𝑉 ⋆ 2 |𝑉 ⋆ 1 = ⋃ 𝐷(𝑥) 𝑥∈𝑉(𝐺) 𝑑𝑎𝑛 𝑉 ⋆ 2 =
⋃ 𝑆(𝑥)} 𝑥∈𝑉(𝐺) b. 𝐸 ⋆ = {𝐸 ⋆ 1 ⋃𝐸 ⋆ 2 |𝐸 ⋆ 1 = {𝑥 𝛼 𝑦 𝛼 |𝛼 = 𝑥𝑦 ∈ 𝐸(𝐺)}
𝑑𝑎𝑛 𝐸 ⋆ 2 = {𝑢𝑣|𝑢  ∈ 𝐷(𝑥), 𝑣 ∈ 𝑆(𝑥), 𝑥 ∈ 𝑉 (𝐺)}} . 5. Faktorisasi  graf  baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) dengan menunjukkan  adanya  himpunan  pasangan sempurna.
Dari  graf  baru 𝐺 ∗ yang  dibangun  tersebut maka terbentuklah lemma sebagai berikut:
Lemma 1
𝐺 memiliki  f-faktor  jika  dan  hanya  jika 𝐺 ∗ memiliki 1-faktor (Bollobas, 1978).
Bukti: Misalkan 𝐺 memiliki  f-faktor  dengan himpunan  sisi 𝐹 ⊂ 𝐸 .  Maka 𝜓(𝐹) memuat  sisi yang  bebas  dan  dalam  setiap  himpunan 𝐷(𝑥) pasti  titik 𝑠(𝑥) tidak  tertutup  oleh 𝜓(𝐹) .  Untuk setiap 𝑥 kita  menambahkan 𝑠(𝑥) yang  bebas dengan  sisi 𝐷(𝑥) − 𝑆(𝑥) yang  menutup  titik-titik yang  lain  dari 𝐷(𝑥) .  Dengan  cara  ini  kita memperoleh 𝐺 ∗ memiliki 1-faktor. Sebaliknya  jika 𝐺 ∗ mempunyai  1-faktor dengan  himpunan  sisi 𝐹 ∗ ⊂ 𝐸 ∗ kemudian 𝜓 −1 (𝐹 ∗ ∩ 𝐸 ∗ ) adalah  himpunan  sisi  dari  f-faktor di 𝐺 .
Contoh Diberikan graf komplit 𝐾 4
Gambar 4 Garf 𝐾 4
1. Menentukan  fungsi 𝑓: 𝑉(𝐾 4 ) → 𝑍 + dengan ketentuan 𝑓(𝑥) ≤ 𝑑(𝑥) ∀𝑥 ∈ 𝑉(𝐾 4 ) .
Gambar 5 Salah Satu Kemungkinan Fungsi 𝑓: 𝑉(𝐾 4 ) → 𝑍 + 2. Menentukan 𝐷(𝑥) = {𝑥 𝛼 |𝛼 ∈ 𝐸(𝐾 4 ), 𝛼 adalah sisi  yang  terkait  langsung  dengan 𝑥; ∀𝑥 ∈ 𝑉(𝐾 4 )} . 𝐷(𝑎) = {𝑎 𝛼 |𝛼 ∈ 𝐸(𝐾 4 ) dengan 𝛼 = 1 , 𝛼 = 4 dan 𝛼 = 5} maka diperoleh 𝐷(𝑎) = {𝑎 1 , 𝑎 4 , 𝑎 5 } 𝐷(𝑏) = {𝑏 𝛼 |𝛼 ∈ 𝐸(𝐾 4 ) dengan 𝛼 = 1 , 𝛼 = 2 dan 𝛼 = 6} maka diperoleh 𝐷(𝑏) = {𝑏 1 , 𝑏 2 , 𝑏 6 } 𝐷(𝑐) = {𝑐 𝛼 |𝛼 ∈ 𝐸(𝐾 4 ) dengan 𝛼 = 2, 𝛼 = 3 dan 𝛼 = 5} maka diperoleh 𝐷(𝑐) = {𝑐 2 , 𝑐 3 , 𝑐 5 } 𝐷(𝑑) = {𝑑 𝛼 |𝛼 ∈ 𝐸(𝐾 4 ) dengan 𝛼 = 3, 𝛼 = 4 dan 𝛼 = 6} maka diperoleh 𝐷(𝑑) = {𝑑 3 , 𝑑 4 , 𝑑 6 } 3. Menentukan 𝑠(𝑥) = 𝑑(𝑥) − 𝑓(𝑥) ∀𝑥 ∈ 𝑉(𝐾 4 )) , kemudian  menentukan 𝑆(𝑥) = {𝑥(𝑖)|1 ≤ 𝑖 ≤ 𝑠(𝑥)} .
𝑠(𝑎) = 𝑑(𝑎) − 𝑓(𝑎) = 3 − 2 = 1 maka diperoleh 𝑆(𝑎) = {𝑎(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑎(1)} 𝑠(𝑏) = 𝑑(𝑏) − 𝑓(𝑏) = 3 − 2 = 1
maka
diperoleh
𝑆(𝑏) = {𝑏(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑏(1) } 𝑠(𝑐) = 𝑑(𝑐) − 𝑓(𝑐) = 3 − 2 = 1
maka diperoleh 𝑆(𝑐) = {𝑐(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑐(1)}
𝑠(𝑑) = 𝑑(𝑑) − 𝑓(𝑑) = 3 − 2 = 1 maka diperoleh 𝑆(𝑑) = {𝑑(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑑(1)} 4. Menentukan graf baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) a. 𝑉 ⋆ = 𝑉 ⋆ 1 ⋃ 𝑉 ⋆ 2 𝑉 ⋆ 1 = ⋃ 𝐷(𝑥) 𝑥∈𝑉{𝐾 4 ) = {𝐷(𝑎) ∪ 𝐷(𝑏) ∪ 𝐷(𝑐) ∪ 𝐷(𝑑)}
= {𝑎 1 , 𝑎 4 , 𝑎 5 , 𝑏 1 , 𝑏 2 , 𝑏 6 , 𝑐 2 , 𝑐 3 , 𝑐 5 , 𝑑 3 , 𝑑 4 , 𝑑 6 } 𝑉 ⋆ 2 = ⋃ 𝑆(𝑥) 𝑥∈𝑉(𝐾 4 ) = {𝑆(𝑎) ∪ 𝑆(𝑏) ∪ 𝑆(𝑐)} = {𝑎(1), 𝑏(1), 𝑐(1), 𝑑(1)} Sehingga untuk 𝑉 ⋆ = 𝑉 ⋆ 1 ⋃ 𝑉 ⋆ 2 diperoleh 𝑉 ⋆ = {𝑎 1 , 𝑎 4 , 𝑎 5 , 𝑏 1 , 𝑏 2 , 𝑏 6 , 𝑐 2 , 𝑐 3 , 𝑐 5 , 𝑑 3 , 𝑑 4 , 𝑑 6 , 𝑎(1), 𝑏(1), 𝑐(1), 𝑑(1)}
b. 𝐸 ⋆ = 𝐸 ⋆ 1 ⋃ 𝐸 ⋆ 2 𝐸 ⋆ 1 = {𝑥 𝛼 𝑦 𝛼 |𝛼 = 𝑥𝑦 ∈ 𝐸(𝐾 4 )} 𝛼 = 1 maka diperoleh 𝑎 1 𝑏 1 𝛼 = 2 maka diperoleh 𝑏 2 𝑐 2 𝛼 = 3 maka diperoleh 𝑐 3 𝑑 3 𝛼 = 4 maka diperoleh 𝑑 4 𝑎 4 𝛼 = 5 maka diperoleh 𝑎 5 𝑐 5 𝛼 = 6 maka diperoleh 𝑏 6 𝑑 6
Jadi, 𝐸 ⋆ 1 = {𝑎 1 𝑏 1 , 𝑏 2 𝑐 2 , 𝑐 3 𝑑 3 , 𝑑 4 𝑎 4 , 𝑎 5 𝑐 5 , 𝑏 6 𝑑 6 } 𝐸 ⋆ 2 = {𝑢𝑣| 𝑢 ∈ 𝐷(𝑥), 𝑣 ∈ 𝑆(𝑥), 𝑥 ∈ 𝑉(𝐾 4 )} = {𝑎 1 𝑎(1), 𝑎 4 𝑎(1), 𝑎 5 𝑎(1), 𝑏 1 𝑏(1), 𝑏 2 𝑏(1), 𝑏 6 𝑏(1), 𝑐 2 𝑐(1), 𝑐 3 𝑐(1), 𝑐 5 𝑐(1), 𝑑 3 𝑑(1), 𝑑 4 𝑑(1), 𝑑 6 𝑑(1)} Sehingga untuk 𝐸 ⋆ = 𝐸 ⋆ 1 ⋃ 𝐸 ⋆ 2 diperoleh
𝐸 ⋆ = {𝑎 1 𝑏 1 , 𝑏 2 𝑐 2 , 𝑐 3 𝑑 3 , 𝑑 4 𝑎 4 , 𝑎 5 𝑐 5 , 𝑏 6 𝑑 6 , 𝑎 1 𝑎(1), 𝑎 4 𝑎(1), 𝑎 5 𝑎(1), 𝑏 1 𝑏(1), 𝑏 2 𝑏(1),
𝑏 6 𝑏(1), 𝑐 2 𝑐(1), 𝑐 3 𝑐(1), 𝑐 5 𝑐(1), 𝑑 3 𝑑(1),
𝑑 4 𝑑(1), 𝑑 6 𝑑(1)} Jadi, graf baru 𝐾 4 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) adalah
Gambar 6 Graf baru 𝐾 4 ⋆
5. Faktorisasi  graf  baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) dengan menunjukkan  adanya  himpunan  pasangan sempurna,  yaitu 𝑀 = {𝑎 1 𝑏 1 , 𝑎 5 𝑐 5 , 𝑐 3 𝑑 3 , 𝑏 6 𝑑 6 , 𝑏 2 𝑏(1), 𝑐 2 𝑐(1), 𝑑 4 𝑑(1)} . Karena graf baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) memuat  pasangan  sempurna  maka graf baru 𝐺 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) memiliki 1-faktor.

## PEMBAHASAN
1. Faktorisasi Graf  Baru 𝑪 𝟑 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟑 ) → {𝟏, 𝟐} Pertama menggambar graf sikel 𝐶 3 dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, dan 𝑐𝑎 = 3
Gambar 7 Graf Sikel 𝐶 3 Selanjutnya  menentukan  semua  kemungkinan fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2} adalah sebagai berikut:
Gambar 8 Semua Kemungkinan Fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2} Kemudian  untuk  langkah  selanjutnya  akan dikerjakan  pada  salah  satu  kemungkinan  dari Gambar  8  sebagai  sampel  kemungkinan  yang dijadikan acuan untuk mengerjakan kemungkinan-kemungkinan  fungsi  yang  lain. Salah satu kemungkinan tersebut adalah:
Gambar 9 Salah Satu Kemungkinan Fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2}
Selanjutnya menentukan 𝐷(𝑥) = {𝑥 𝛼 |𝛼 = 𝐸(𝐶 3 ), 𝛼 terkait langsung dengan 𝑥 ∈ 𝑉(𝐶 3 )} 𝐷(𝑎) = {𝑎 𝛼 |𝛼 ∈ 𝐸(𝐶 3 ) dengan 𝛼 = 1 dan 𝛼 = 3} maka diperoleh 𝐷(𝑎) = {𝑎 1 , 𝑎 3 } 𝐷(𝑏) = {𝑏 𝛼 |𝛼 ∈ 𝐸(𝐶 3 ) dengan 𝛼 = 1 dan 𝛼 = 2} maka diperoleh 𝐷(𝑏) = {𝑏 1 , 𝑏 2 } 𝐷(𝑐) = {𝑐 𝛼 |𝛼 ∈ 𝐸(𝐶 3 ) dengan 𝛼 = 2 dan 𝛼 = 3} maka diperoleh 𝐷(𝑐) = {𝑐 2 , 𝑐 3 }
Selanjutnya
menentukan
𝑠(𝑥) = 𝑑(𝑥) − 𝑓(𝑥) ∀𝑥 ∈ 𝑉(𝐶 3 ) ,  kemudian  menentukan 𝑆(𝑥) = {𝑥(𝑖)|1 ≤ 𝑖 ≤ 𝑠(𝑥)} 𝑠(𝑎) = 𝑑(𝑎) − 𝑓(𝑎) = 2 − 1 = 1 maka diperoleh 𝑆(𝑎) = {𝑎(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑎(1)} 𝑠(𝑏) = 𝑑(𝑏) − 𝑓(𝑏) = 2 − 2 = 0 maka diperoleh 𝑆(𝑏) = {𝑏(𝑖)|1 ≤ 𝑖 ≤ 0} = { } 𝑠(𝑐) = 𝑑(𝑐) − 𝑓(𝑐) = 2 − 1 = 1 maka diperoleh 𝑆(𝑐) = {𝑐(𝑖)|1 ≤ 𝑖 ≤ 1} = {𝑐(1)} Selanjutnya menentukan graf baru 𝐶 3 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) a. 𝑉 ⋆ = 𝑉 ⋆ 1 ⋃ 𝑉 ⋆ 2 𝑉 ⋆ 1 = ⋃ 𝐷(𝑥) 𝑥∈𝑉{𝐶3) = {𝐷(𝑎) ∪ 𝐷(𝑏) ∪
𝐷(𝑐)} = {𝑎 1 , 𝑎 3 , 𝑏 1 , 𝑏 2 , 𝑐 2 , 𝑐 3 } 𝑉 ⋆ 2 = ⋃ 𝑆(𝑥) 𝑥∈𝑉(𝐶3) = {𝑆(𝑎) ∪ 𝑆(𝑏) ∪ 𝑆(𝑐)} = {𝑎(1), 𝑐(1)} Sehingga untuk 𝑉 ⋆ = 𝑉 ⋆ 1 ⋃ 𝑉 ⋆ 2 diperoleh 𝑉 ⋆ = {𝑎 1 , 𝑎 3 , 𝑏 1 , 𝑏 2 , 𝑐 2 , 𝑐 3 , 𝑎(1), 𝑐(1)} b. 𝐸 ⋆ = 𝐸 ⋆ 1 ⋃ 𝐸 ⋆ 2 𝐸 ⋆ 1 = {𝑥 𝛼 𝑦 𝛼 |𝛼 = 𝑥𝑦 ∈ 𝐸(𝐶 3 )} 𝛼 = 1 maka diperoleh 𝑎 1 𝑏 1 𝛼 = 2 maka diperoleh 𝑏 2 𝑐 2 𝛼 = 3 maka diperoleh 𝑐 3 𝑎 3
Jadi, 𝐸 ⋆ 1 = {𝑎 1 𝑏 1 , 𝑏 2 𝑐 2 , 𝑐 3 𝑎 3 } 𝐸 ⋆ 2 = {𝑢𝑣| 𝑢 ∈ 𝐷(𝑥), 𝑣 ∈ 𝑆(𝑥), 𝑥 ∈ 𝑉(𝐶 3 )} = {𝑎 1 𝑎(1), 𝑎 3 𝑎(1), 𝑐 2 𝑐(1), 𝑐 3 𝑐(1)} Sehingga untuk 𝐸 ⋆ = 𝐸 ⋆ 1 ⋃ 𝐸 ⋆ 2 diperoleh
𝐸 ⋆ = {𝑎 1 𝑏 1 , 𝑏 2 𝑐 2 , 𝑐 3 𝑎 3 , 𝑎 1 𝑎(1), 𝑎 3 𝑎(1), 𝑐 2 𝑐(1), 𝑐 3 𝑐(1)} Jadi, graf baru 𝐶 3 ⋆ = (𝑉 ⋆ , 𝐸 ⋆ ) dari kemungkinan  fungsi 𝑓(𝑎) = 1, 𝑓(𝑏) = 2, dan 𝑓(𝑐) = 1 adalah:
Gambar 10 Graf Baru 𝐶 3 ⋆ dari Sampel Kemungkinan Fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2}
Selanjutnya  faktorisasi  graf  baru 𝐶 3 ⋆ .  Dari Gambar 10 didapatkan pasangan 𝑀 = {𝑏 2 𝑐 2 , 𝑐(1)𝑐 3 , 𝑎 3 𝑎(1), 𝑎 1 𝑏 1 } sebagai  himpunan
pasangan  titik  yang  membentuk  sisi  yang  tidak saling terhubung langsung. Karena titik-titik pada Gambar  10  bisa  berpasang-pasangan  dan merupakan  pasangan  sempurna,  maka  berakibat graf baru 𝐶 3 ⋆ dari fungsi 𝑓(𝑎) = 1, 𝑓(𝑏) = 2, dan 𝑓(𝑐) = 1 memiliki 1-faktor .
Selanjutnya  untuk  pembahasan  kemungkinan- kemungkinan  dari  fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2} yang lain  dapat  dapat  dilakukan  dengan  cara  yang sama  dan  disimpulkan  bahwa  kemungkinan- kemungkinan  fungsi  yang  menghasilkan  graf baru 𝐶 3 ⋆ yang  memiliki  1-faktor  adalah  sebagai berikut:
Gambar 11 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2} yang Memiliki 1-Faktor
Maka  dapat  dibuat  dugaan  mengenai  ciri-ciri fungsi  yang  mengakibatkan  graf  baru 𝐶 3 ⋆ yang dihasilkan  dari  fungsi 𝑓: 𝑉(𝐶 3 ) → {1, 2} akan memiliki 1-faktor dengan melihat banyaknya titik yang dipetakan yaitu fungsi dengan banyak 𝑛 titik atau hanya satu titik dipetakan ke 2.
Untuk  graf 𝑪 𝒏 selanjutnya  akan  dilakukan dengan  cara  yang  sama  dan  hanya  akan ditunjukkan fungsi yang memiliki 1-faktor.
2. Faktorisasi Graf  Baru 𝑪 𝟒 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟒 ) → {𝟏, 𝟐} Gambar  graf  sikel (𝐶 4 ) dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, 𝑐𝑑 = 3, 𝑑𝑒 = 4
Gambar 12 Graf Sikel 𝐶 4
Kemungkinan-kemungkinan
fungsi yang menghasilkan  graf  baru 𝐶 4 ⋆ yang  memiliki  1- faktor adalah sebagai berikut:
Gambar 13 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 4 ) → {1, 2} yang Memiliki 1-faktor
3. Faktorisasi Graf  Baru 𝑪 𝟓 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟓 ) → {𝟏, 𝟐} Gambar  graf  sikel 𝐶 5 dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, 𝑐𝑑 = 3, 𝑑𝑒 = 4, 𝑒𝑎 = 5
Gambar 14 Graf Sikel 𝐶 5
Kemungkinan-kemungkinan
fungsi yang menghasilkan  graf  baru 𝐶 5 ⋆ yang  memiliki  1- faktor adalah sebagai berikut:
Gambar 15 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 5 ) → {1, 2} yang Memiliki 1-faktor
4. Faktorisasi Graf  Baru 𝑪 𝟔 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟔 ) → {𝟏, 𝟐} Gambar  graf  sikel (𝐶 6 ) dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, 𝑐𝑑 = 3, 𝑑𝑒 = 4, 𝑒𝑓 = 5, 𝑓𝑎 = 6
Gambar 3.10 Graf Sikel 𝐶 6
Kemungkinan-kemungkinan
fungsi
yang
menghasilkan  graf  baru 𝐶 6 ⋆ yang  memiliki  1- faktor adalah sebagai berikut:
Gambar 15 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 6 ) → {1, 2} yang Memiliki 1-faktor
5. Faktorisasi Graf  Baru 𝑪 𝟕 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟕 ) → {𝟏, 𝟐} Gambar  graf  sikel (𝐶 7 ) dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, 𝑐𝑑 = 3, 𝑑𝑒 = 4, 𝑒𝑓 = 5, 𝑓𝑔 = 6, 𝑔𝑎 = 7
Gambar 16 Graf Sikel 𝐶 7
Kemungkinan-kemungkinan
fungsi yang menghasilkan  graf  baru 𝐶 7 ⋆ yang  memiliki  1- faktor adalah sebagai berikut:
Gambar 17 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 7 ) → {1, 2} yang Memiliki 1-faktor
6. Faktorisasi Graf  Baru 𝑪 𝟖 ⋆ yang  Dihasilkan dari Fungsi 𝒇: 𝑽(𝑪 𝟖 ) → {𝟏, 𝟐} Pertama MengGambar graf sikel (𝐶 8 ) dengan 𝑎𝑏 = 1, 𝑏𝑐 = 2, 𝑐𝑑 = 3, 𝑑𝑒 = 4, 𝑒𝑓 = 5, 𝑓𝑔 = 6, 𝑔ℎ = 7, ℎ𝑎 = 8
Gambar 18 Graf Sikel 𝐶 8 Kemungkinan-kemungkinan fungsi yang menghasilkan  graf  baru 𝐶 8 ⋆ yang  memiliki  1- faktor adalah sebagai berikut:
Gambar 19 Kemungkinan Fungsi 𝑓: 𝑉(𝐶 8 ) → {1, 2} yang Memiliki 1-faktor
7. Dugaan  Ciri-ciri  Fungsi 𝒇: 𝑽(𝑪 𝒏 ) → {𝟏, 𝟐} yang  Mengakibatkan  Graf  Baru 𝑪 𝒏 ⋆ Memiliki 1-Faktor
Ciri-ciri  fungsi  yang  mengakibatkan  graf baru 𝐶 𝑛 ⋆ yang  dihasilkan  dari  fungsi 𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} akan memiliki 1-faktor adalah:
Untuk 𝑛 ganjil a. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 2 b. Fungsi  dengan  sebanyak  hanya  satu  titik dipetakan ke 2.
Untuk 𝑛 genap
a. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 2 b. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 1.

## Teorema 1:
Fungsi  yang  mengakibatkan  graf  baru 𝐶 𝑛 ⋆ yang dihasilkan dari kemungkinan- kemungkinan fungsi 𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} dapat  memiliki  1-faktor  untuk 𝑛 ganjil (𝑛 ≥ 3) adalah  fungsi  dengan  sebanyak 𝑛 titik atau hanya satu titik dipetakan ke 2.
Bukti: Misal 𝐶 𝑛 adalah  graf  sikel  dengan 𝑛 ganjil (𝑛 ≥ 3) dengan 𝑉(𝐶 𝑛 ) = {𝑣 1 , 𝑣 2 , 𝑣 3 , … , 𝑣 𝑛 } dan 𝐸(𝐶 𝑛 ) = {𝑒 1 , 𝑒 2 , 𝑒 3 , … , 𝑒 𝑛 } dengan 𝑒 𝑖 = 𝑣 𝑖 𝑣 𝑖+1 untuk 𝑖 = 1,2, … , 𝑛 − 1 dan 𝑒 𝑛 = 𝑣 𝑛 𝑣 1 .  Misalkan 𝐶 𝑛 ∗ adalah  graf  baru  yang  dihasilkan  dari kemungkinan
𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} .
Akan ditunjukkan  bahwa 𝐶 𝑛 ∗ memiliki  1-faktor  jika fungsinya  memetakan  sebanyak 𝑛 titik  atau hanya satu titik dipetakan ke 2. Misal gambar graf 𝐶 𝑛 adalah:
Gambar 20 Graf Sikel 𝐶 𝑛 untuk 𝑛 Ganjil
Selanjutnya menentukan fungsi
berdasarkan ciri-ciri yang telah ditentukan, yaitu: a. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 2 Misalkan 𝑓 fungsi dari 𝑉(𝐶 𝑛 ) ke {1, 2} dengan 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛 . Maka diperoleh:
𝐷(𝑥) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 …, 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 }
𝑆(𝑥) = { } 𝑉 ⋆ = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 …,
𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } 𝐸 ⋆ = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 3𝑒2 , … , 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 }
Jadi  graf  baru 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) dengan  fungsi 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛 adalah:
Gambar 21 Graf Baru 𝐶 𝑛 ∗ untuk 𝑛 Ganjil dari Fungsi 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛 Selanjutnya  dari  Gambar  21  dilakukan faktorisasi  dengan  menunjukkan  adanya pasangan yaitu
dengan
melihat pengembangan  titik  yang  terjadi  dari  setiap titik  di  graf  sikel 𝐶 𝑛 berdasarkan  masing- masing pemetaannya sebagaimana berikut:
Untuk 𝑣 1 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 1 ) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 } dan 𝑆(𝑣 1 ) = { } .  Jadi  titik 𝑣 1 berkembang menjadi {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 }
Untuk 𝑣 2 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 2 ) = {𝑣 2𝑒1 , 𝑣 2𝑒2 } dan 𝑆(𝑣 2 ) = { }. Jadi  titik 𝑣 2 berkembang menjadi {𝑣 2𝑒1 , 𝑣 2𝑒2 } ⋮ Untuk 𝑣 𝑛 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 𝑛 ) = { 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } dan 𝑆(𝑣 𝑛 ) = { } .  Jadi titik 𝑣 𝑛 berkembang menjadi {𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } .
Dari  pengembangan  titik  ini  dapat dilihat  bahwa  untuk  setiap  titik  yang dipetakan  ke  2  selalu  berkembang  menjadi 2 titik,  karena  sebanyak 𝑛 titik  yang  dipetakan ke  2  maka  banyak  pengembangannya  adalah 2𝑛 titik,  dan  karena 𝑛 = 2𝑘 + 1 maka 2𝑛 = 2(2𝑘 + 1) bernilai  genap.  Kemudian  dari simulasi  Gambar  3.17  terlihat  bahwa  sisi-sisi yang terbentuk pada graf baru 𝐶 𝑛 ∗ berupa sisi- sisi  yang  berselang-seling  dengan 𝑀 = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 3𝑒2 , … , 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 } ,  maka  dapat dipastikan  graf  baru 𝐶 𝑛 ∗ dengan  fungsi sebanyak 𝑛 titik dipetakakan ke 2 akan selalu memiliki 1-faktor.
b. Fungsi  dengan  sebanyak  hanya  satu  titik dipetakan ke 2
Misalkan 𝑓 fungsi dari 𝑉(𝐶 𝑛 ) ke {1, 2} dengan 𝑓(𝑣 𝑖 ) = 1 dan 𝑓(𝑣 1 ) = 2 untuk 𝑖 = 2, 3, … , 𝑛 . Maka diperoleh:
𝐷(𝑥) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 …, 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 }
𝑆(𝑥) = {𝑣 2 (1), 𝑣 3 (1), … , 𝑣 𝑛 (1)}
𝑉 ⋆ = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 … , 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 , 𝑣 2 (1), 𝑣 3 (1), … , 𝑣 𝑛 (1)}
𝐸 ⋆ = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 3𝑒2 , … , 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 , 𝑣 2𝑒1 𝑣 2 (1), 𝑣 2𝑒2 𝑣 2 (1), 𝑣 3𝑒2 𝑣 3 (1), 𝑣 3𝑒3 𝑣 3 (1), …,
𝑣 𝑛𝑒𝑛−1 𝑣 𝑛 (1), 𝑣 𝑛𝑒𝑛 𝑣 𝑛 (1)}
Jadi  graf  baru 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) dengan  fungsi 𝑓(𝑣 𝑖 ) = 1 dan 𝑓(𝑣 1 ) = 2 untuk 𝑖 = 2, 3, … , 𝑛 adalah:
Gambar 22 Graf Baru 𝐶 𝑛 ∗ untuk 𝑛 Ganjil dari Fungsi 𝑓(𝑣 𝑖 ) = 1 dan 𝑓(𝑣 1 ) = 2 untuk 𝑖 = 2, 3, … , 𝑛 Selanjutnya  dari  Gambar  22  dilakukan faktorisasi  dengan  menunjukkan  adanya pasangan yaitu dengan melihat pengembangan  titik  yang  terjadi  dari  setiap titik  di  graf  sikel 𝐶 𝑛 berdasarkan  masing- masing pemetaannya sebagaimana berikut:
Untuk 𝑣 1 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 1 ) = {𝑣 1𝑒1 , 𝑣 1𝑒𝑛 } dan 𝑆(𝑣 1 ) = { } .  Jadi  titik 𝑣 1 berkembang menjadi {𝑣 1𝑒1 , 𝑣 1𝑒𝑛 } Untuk 𝑣 2 dipetakan  ke 1 ,  maka  diperoleh 𝐷(𝑣 2 ) = {𝑣 2𝑒1 , 𝑣 2𝑒2 } dan 𝑆(𝑣 2 ) = { 𝑣 2 (1)}. Jadi
titik 𝑣 2 berkembang menjadi {𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 2 (1)}
⋮ Untuk 𝑣 𝑛 dipetakan  ke 1 ,  maka  diperoleh 𝐷(𝑣 𝑛 ) = {𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } dan 𝑆(𝑣 𝑛 ) = {𝑣 𝑛 (1) } . Jadi titik 𝑣 𝑛 berkembang menjadi {𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 , 𝑣 𝑛 (1)} .
Dari  pengembangan  titik  ini  dapat  dilihat bahwa  untuk  setiap  titik  yang  dipetakan  ke  2 selalu  berkembang  menjadi 2 titik,  karena sebanyak satu titik yang dipetakan ke 2 maka banyak  pengembangannya  adalah 2 titik, sedangkan  untuk  setiap  titik  yang  dipetakan ke  1  selalu  berkembang  menjadi 3 titik, karena sebanyak 𝑛 − 1 titik yang dipetakan ke 1  maka  banyak  pengembangannya  adalah 3(𝑛 − 1 ) .
Jadi,
secara keseluruhan perkembangan  titiknya  adalah  sebesar 2 + 3(𝑛 − 1 ) titik.  Karena 𝑛 = 2𝑘 + 1 maka 2 + 3(𝑛 − 1 ) = 6𝑘 + 2 bernilai genap. Kemudian dari simulasi Gambar 3.18 terlihat bahwa sisi- sisi  yang  terbentuk  pada  graf  baru 𝐶 𝑛 ∗ akan selalu  berbentuk  lintasan,  sehingga  dapat ditunjukkan  himpunan  pasangannya  adalah 𝑀 = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 2 (1), 𝑣 3𝑒2 𝑣 3 (1) … ,
𝑣 𝑛𝑒𝑛−1 𝑣 𝑛 (1), 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 } , maka dapat dipastikan  graf  baru 𝐶 𝑛 ∗ dengan  fungsi sebanyak  hanya  satu  titik  dipetakakan  ke  2 akan selalu memiliki 1-faktor.

## Teorema 2:
Fungsi  yang  mengakibatkan  graf  baru 𝐶 𝑛 ⋆ yang dihasilkan dari kemungkinan-
kemungkinan fungsi 𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} dapat  memiliki  1-faktor  untuk 𝑛 genap (𝑛 ≥ 4) adalah  fungsi  dengan  sebanyak 𝑛 titik dipetakan ke 2 atau ke 1.
Bukti Misal 𝐶 𝑛 adalah graf sikel  dengan 𝑛 genap (𝑛 ≥ 4) dengan 𝑉(𝐶 𝑛 ) = {𝑣 1 , 𝑣 2 , 𝑣 3 , … , 𝑣 𝑛 } dan 𝐸(𝐶 𝑛 ) = {𝑒 1 , 𝑒 2 , 𝑒 3 , … , 𝑒 𝑛 } dengan 𝑒 𝑖 = 𝑣 𝑖 𝑣 𝑖+1 untuk 𝑖 = 1,2, … , 𝑛 − 1 dan 𝑒 𝑛 = 𝑣 𝑛 𝑣 1 .  Misalkan 𝐶 𝑛 ∗ adalah  graf  baru  yang  dihasilkan  dari kemungkinan
𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} .
Akan ditunjukkan  bahwa 𝐶 𝑛 ∗ memiliki  1-faktor  jika fungsinya memetakan sebanyak 𝑛 titik dipetakan ke 2 atau ke 1. Misal gambar graf 𝐶 𝑛 adalah:
Gambar 23 Graf Sikel 𝐶 𝑛 untuk 𝑛 Genap Selanjutnya menentukan
fungsi berdasarkan ciri-ciri yang telah ditentukan, yaitu: a. Fungsi  dengan  sebanyak 𝑛 titik  dipetakan ke 2 Misalkan 𝑓 fungsi dari 𝑉(𝐶 𝑛 ) ke {1, 2} dengan 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛 . Maka diperoleh: 𝐷(𝑥) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 …, 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } 𝑆(𝑥) = { } 𝑉 ⋆ = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 … , 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 }
𝐸 ⋆ = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 3𝑒2 , … , 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 }
Jadi  graf  baru 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) dengan  fungsi 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛 adalah:
Gambar 24 Graf Baru 𝐶 𝑛 ∗ untuk 𝑛 Genap dari Fungsi 𝑓(𝑣 𝑖 ) = 2 untuk 𝑖 = 1, 2, … , 𝑛
Selanjutnya  dari  Gambar  24  dilakukan faktorisasi  dengan  menunjukkan  adanya pasangan yaitu
dengan
melihat pengembangan  titik  yang  terjadi  dari  setiap titik  di  graf  sikel 𝐶 𝑛 berdasarkan  masing- masing pemetaannya sebagaimana berikut:
Untuk 𝑣 1 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 1 ) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 } dan 𝑆(𝑣 1 ) = { } .  Jadi  titik 𝑣 1 berkembang menjadi {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 }
Untuk 𝑣 2 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 2 ) = {𝑣 2𝑒1 , 𝑣 2𝑒2 } dan 𝑆(𝑣 2 ) = { }. Jadi  titik 𝑣 2 berkembang menjadi {𝑣 2𝑒1 , 𝑣 2𝑒2 } ⋮
Untuk 𝑣 𝑛 dipetakan  ke 2 ,  maka  diperoleh 𝐷(𝑣 𝑛 ) = { 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } dan 𝑆(𝑣 𝑛 ) = { } .  Jadi titik 𝑣 𝑛 berkembang menjadi {𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } .
Dari  pengembangan  titik  ini  dapat dilihat  bahwa  untuk  setiap  titik  yang dipetakan  ke  2  selalu  berkembang  menjadi 2 titik,  karena  sebanyak 𝑛 titik  yang  dipetakan ke  2  maka  banyak  pengembangannya  adalah 2𝑛 titik,  dan  karena 𝑛 = 2𝑘 + 2 maka 2𝑛 = 2(2𝑘 + 2) bernilai  genap.  Kemudian  dari simulasi  Gambar  3.20  terlihat  bahwa  sisi-sisi yang terbentuk pada graf baru 𝐶 𝑛 ∗ berupa sisi- sisi  yang  berselang-seling  dengan 𝑀 = {𝑣 1𝑒1 𝑣 2𝑒1 ,   𝑣 2𝑒2 𝑣 3𝑒2 , …,   𝑣 𝑛+1𝑒𝑛+1 𝑣 𝑛+2𝑒𝑛+1 ,
𝑣 𝑛+2𝑒𝑛+2 𝑣 1𝑒𝑛+2 } ,  maka  dapat  dipastikan  graf baru 𝐶 𝑛 ∗ dengan  fungsi  sebanyak 𝑛 titik dipetakakan  ke  2  akan  selalu  memiliki  1- faktor.
b. Fungsi dengan banyak 𝑛 titik dipetakan ke
1 Misalkan 𝑓 fungsi dari 𝑉(𝐶 𝑛 ) ke {1, 2} dengan 𝑓(𝑣 𝑖 ) = 1 untuk 𝑖 = 1, 2, … , 𝑛 . Maka diperoleh: 𝐷(𝑥) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 …, 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 }
𝑆(𝑥) = { 𝑣 1 (1), 𝑣 2 (1), 𝑣 3 (1), … , 𝑣 𝑛 (1)} 𝑉 ⋆ = {𝑣 1𝑒𝑛 , 𝑣 1𝑒1 , 𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 3𝑒2 , 𝑣 3𝑒3 … , 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 , 𝑣 1 (1), 𝑣 2 (1), 𝑣 3 (1), … , 𝑣 𝑛 (1)} 𝐸 ⋆ = {𝑣 1𝑒1 𝑣 2𝑒1 , 𝑣 2𝑒2 𝑣 3𝑒2 , … , 𝑣 𝑛𝑒𝑛 𝑣 1𝑒𝑛 , 𝑣 1𝑒𝑛 𝑣 1 (1), 𝑣 1𝑒1 𝑣
1 (1), 𝑣 2𝑒1 𝑣 2 (1), 𝑣 2𝑒2 𝑣 2 (1), 𝑣 3𝑒2 𝑣 3 (1), 𝑣 3𝑒3 𝑣 3 (1), … , 𝑣 𝑛𝑒𝑛−1 𝑣 𝑛 (1), 𝑣 𝑛𝑒𝑛 𝑣 𝑛 (1)}
Jadi  graf  baru 𝐶 𝑛 ∗ = (𝑉 ∗ , 𝐸 ∗ ) dengan  fungsi 𝑓(𝑣 𝑖 ) = 1 untuk 𝑖 = 1, 2, … , 𝑛 adalah:
Gambar 25 Graf Baru 𝐶 𝑛 ∗ untuk 𝑛 Genap dari Fungsi 𝑓(𝑣 𝑖 ) = 1 untuk 𝑖 = 1, 2, … , 𝑛
Selanjutnya  dari  Gambar  25  dilakukan faktorisasi  dengan  menunjukkan  adanya pasangan yaitu dengan melihat pengembangan  titik  yang  terjadi  dari  setiap titik  di  graf  sikel 𝐶 𝑛 berdasarkan  masing- masing pemetaannya sebagaimana berikut:
Untuk 𝑣 1 dipetakan  ke 1 ,  maka  diperoleh 𝐷(𝑣 1 ) = {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 } dan 𝑆(𝑣 1 ) = { 𝑣 1 (1)} . Jadi titik 𝑣 1 berkembang
menjadi {𝑣 1𝑒𝑛 , 𝑣 1𝑒 1 , 𝑣 1 (1)}
Untuk 𝑣 2 dipetakan  ke 1 ,  maka  diperoleh 𝐷(𝑣 2 ) = {𝑣 2𝑒1 , 𝑣 2𝑒2 } dan 𝑆(𝑣 2 ) = {𝑣 2 (1) }. Jadi
titik
𝑣 2 berkembang menjadi
{𝑣 2𝑒1 , 𝑣 2𝑒2 , 𝑣 2 (1) } ⋮ Untuk 𝑣 𝑛 dipetakan  ke 1 ,  maka  diperoleh 𝐷(𝑣 𝑛 ) = { 𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 } dan 𝑆(𝑣 𝑛 ) = {𝑣 𝑛 (1) } . Jadi titik 𝑣 𝑛
berkembang menjadi {𝑣 𝑛𝑒𝑛−1 , 𝑣 𝑛𝑒𝑛 , 𝑣 𝑛 (1)} .
Dari  pengembangan  titik  ini  dapat dilihat  bahwa  untuk  setiap  titik  yang dipetakan  ke  1  selalu  berkembang  menjadi 3 titik,  karena  sebanyak 𝑛 titik  yang  dipetakan ke  1  maka  banyak  pengembangannya  adalah 3𝑛 titik,  dan  karena 𝑛 = 2𝑘 + 2 maka 3𝑛 = 3(2𝑘 + 2) bernilai  genap.  Kemudian  dari simulasi  Gambar  3.21  terlihat  bahwa  sisi-sisi yang  terbentuk  pada  graf  baru 𝐶 𝑛 ∗ berupa lintasan, sehingga dapat ditunjukkan himpunan
pasangannya
adalah
𝑀 =
{𝑣 3𝑒3 𝑣 3 (1),    𝑣 3𝑒3 𝑣 2𝑒2 ,    𝑣 2𝑒1 𝑣 2 (1),  𝑣 1𝑒1 𝑣 1 (1),
𝑣 1𝑒𝑛 𝑣 𝑛𝑒𝑛 , 𝑣 𝑛𝑒𝑛−1 𝑣 𝑛 (1)} ,  maka  dapat  dipastikan graf baru 𝐶 𝑛+2 ∗ dengan fungsi sebanyak 𝑛 titik dipetakakan  ke  2  akan  selalu  memiliki  1- faktor.

## PENUTUP
1. Kesimpulan
Berdasarkan  pembahasan,  maka  dapat diperoleh  kesimpulan  bahwa  ciri-ciri  fungsi yang  mengakibatkan  graf  baru 𝐶 𝑛 ⋆ yang dihasilkan  dari  kemungkinan-kemungkinan fungsi 𝑓: 𝑉(𝐶 𝑛 ) → {1, 2} dapat  memiliki  1- faktor adalah: Untuk 𝑛 ganjil a. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 2 b. Fungsi  dengan  sebanyak  hanya  satu  titik dipetakan ke 2 Untuk 𝑛 genap a. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 2 b. Fungsi dengan sebanyak 𝑛 titik dipetakan ke 1

## 2. Saran
Bagi  penelitian  selanjutnya  disarankan untuk melanjutkan penelitian pada graf lain.

## DAFTAR PUSTAKA
[1] Bollobas,  B.  (1978). EXTREMAL  GRAPH THEORY. San Francisco: ACADEMIC PRESS.
[2] Bondy,  J.,  &  Murty,  U.  (2008). Graph  Theory. USA: Springer.
[3] Budayasa. (2007). Teory Graph dan Aplikasinya. Surabaya: Unesa University Press.
[4] Chartrand, G., & Lesniak, L. (1986). Graph and Digraphs. Washington: Chapman & Hall/CRC.
[5] Munir, R. (2012). Matematika Diskrit.
Bandung: Informatika Bandung.