Salah satu topik yang menarik untuk dikaji pada teori graf adalah tentang automorfisme graf. Automorfisme pada suatu graf G adalah isomorfisme dari graf G ke G sendiri. Dengan kata lain automorfisme graf G merupakan suatu permutasi dari himpunan titik-titik V(G) atau sisi-sisi dari graf G, E(G) yang menghasilkan graf yang isomorfik dengan dirinya sendiri. Jika adalah suatu automorfisme dari G ke G dan v V(G) maka . Untuk mencari automorfisme pada suatu graf, biasanya dilakukan dengan menentukan semua kemungkinan fungsi yang satu-satu, onto, dan isomorfisme dari himpunan titik pada graf tersebut. Tujuan penelitian ini adalah untuk mengetahui dan menguraikan automorfisme graf bintang dan graf lintasan serta penjabarannya.
Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research), dengan langkah-langkah penelitian sebagai berikut: (1) Merumuskan masalah; (2) Menggambarkan graf bintang ( sampai ) dan graf lintasan (P2 sampai P6); (3) Memberikan label pada setiap titik dari masing-masing graf yang telah digambarkan; (4) Menentukan semua kemungkinan fungsi permutasi yang satu-satu dan onto dari setiap graf pada dirinya sendiri; (5) Memilah fungsi permutasi yang automorfisme dan tidak automorfisme dari semua kemungkinan fungsi; (6) Menentukan karakteristik dari fungsi permutasi automorfisme; (7) Membangun teorema tentang banyak fungsi permutasi yang automorfisme dan bentuk fungsi permutasinya, serta pembuktiannya; (8) Menunjukkan bahwa himpunan automorfisme dari graf bintang dan graf lintasan dengan komposisi fungsi adalah membentuk grup
Berdasarkan hasil pembahasan, dapat diperoleh (1) Graf bintang- ( ) memiliki +1 titik, banyaknya automorfisme dari graf tersebut adalah . Permutasinya α adalah automorfisme yang harus mengawetkan derajat titik-titiknya, oleh karena itu permutasinya harus berbentuk dan untuk setiap . Jika α = ( … ) fungsi bijektif maka α merupakan automorfisme; (2) Dari graf lintasan maka banyaknya automorfisme hanya ada 2 fungsi permutasi yang berbentuk: (1) untuk n genap: ( ), untuk n ganjil: ( )( ) dan (2) = .
Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research), dengan langkah-langkah penelitian sebagai berikut: (1) Merumuskan masalah; (2) Menggambarkan graf bintang ( sampai ) dan graf lintasan (P2 sampai P6); (3) Memberikan label pada setiap titik dari masing-masing graf yang telah digambarkan; (4) Menentukan semua kemungkinan fungsi permutasi yang satu-satu dan onto dari setiap graf pada dirinya sendiri; (5) Memilah fungsi permutasi yang automorfisme dan tidak automorfisme dari semua kemungkinan fungsi; (6) Menentukan karakteristik dari fungsi permutasi automorfisme; (7) Membangun teorema tentang banyak fungsi permutasi yang automorfisme dan bentuk fungsi permutasinya, serta pembuktiannya; (8) Menunjukkan bahwa himpunan automorfisme dari graf bintang dan graf lintasan dengan komposisi fungsi adalah membentuk grup
Berdasarkan hasil pembahasan, dapat diperoleh (1) Graf bintang- ( ) memiliki +1 titik, banyaknya automorfisme dari graf tersebut adalah . Permutasinya α adalah automorfisme yang harus mengawetkan derajat titik-titiknya, oleh karena itu permutasinya harus berbentuk dan untuk setiap . Jika α = ( … ) fungsi bijektif maka α merupakan automorfisme; (2) Dari graf lintasan maka banyaknya automorfisme hanya ada 2 fungsi permutasi yang berbentuk: (1) untuk n genap: ( ), untuk n ganjil: ( )( ) dan (2) = .
No comments:
Post a Comment