Sifat-Sifat Graf Permutasi

Penelitian ini merupakan penjelasan kembali tentang graf permutasi serta
sifat-sifatnya. Diberikan permutasi ( ) ( ) ( ) , graf permutasi
( ) adalah graf dengan himpunan simpul * + dan
himpunan sisi *( ) ( ) ( ) +. Penelitian ini dilakukan
dengan metode kajian pustaka, yaitu dengan mempelajari referensi yang terkait
dengan topik yang dikaji. Pada skripsi ini dijabarkan syarat-syarat yang harus
dipenuhi agar suatu graf berlabel merupakan graf permutasi, serta permutasi yang
sesuai dengan graf yang diberikan dan sifat-sifat dari graf permutasi. Dari hasil
analisis, graf permutasi selalu diawali dengan graf kosong dan diakhiri dengan
graf lengkap kecuali untuk graf permutasi dengan yang mana hanya
terbentuk satu graf yang merupakan graf kosong. Selanjutnya untuk ,
graf yang terbentuk selalu berjumlah genap dan untuk setiap graf terdapat
pasangan graf yang merupakan komplemen satu sama lain. Untuk ,
terdapat graf-graf yang saling isomorfik.