Permasalahan 1-Faktorisasi Sempurna pada Graf Sirkulan Bipartit Berderajat 4

YANUZ NURCHALIK, Dr. Yeni Susanti, M. Si.

2017 | Skripsi | S1 MATEMATIKA

Di dalam tugas akhir ini dibahas mengenai permasalahan 1-faktorisasi sempurna pada graf sirkulan berderajat 4. Pembahasan diawali dengan penjelasan tentang 1-faktorisasi pada graf secara umum. Berikutnya, dibahas tentang 1-faktorisasi sempurna pada graf sirkulan bipartit serta ditunjukkan pula beberapa graf sirkulan bipartit berderajat 4 yang memenuhi kondisi 1-faktorisasi sempurna. Pada bagian akhir dari pembahasan, dijelaskan tentang sekeluarga graf sirkulan non-bipartit berderajat 4 yang tidak memenuhi kondisi 1-faktorisasi sempurna.

In this final project, we discuss about the perfect 1-factorization (abbreviated P1F) problems for circulant graphs of 4-degree. First, we concern 1-factirozation of arbitrary graphs. And then, we discuss on the P1F of circulant bipartite graphs and show several constructions of them having 4-degree. In the final part, we present that a family of circulant non-bipartite graphs of 4-degree does not admit the P1F.

Kata Kunci : teori graf, 1-faktor, 1-faktorisasi, 1-faktorisasi sempurna, graf sirkulan, graf bipartit