GRUP DARI AUTOMORFISME GRAF BIPARTISI KOMPLIT TRY AZISAH NURMAN Jurusan Matematika, Fakultas Sains dan Teknologi, UINAM
[email protected]
ABSTRAK
Info: Jurnal MSA Vol. 2 No. 1 Edisi: Januari – Juni 2014 Artikel No.: 11 Halaman: 77 - 80 ISSN: 2355-083X Prodi Matematika UINAM
Grup dari automorfisme suatu graf G adalah himpunan semua automorfisme membentuk grup dibawa operasi komposisi, dengan automorfisme dari suatu graf merupakan ishomorfisme dari graf G ke dirinya sendiri. Adapun graf yang akan dicari automorfismenya yaitu graf bipartisi komplit yang merupakan graf dengan titik-titiknya bisa dipartisi ke dalam 2 partisi, dimana tiap titik dari suatu partisi dihubungkan ke setiap titik-titik pada partisi lain. Banyaknya automorfisme graf bipartisi komplit k m,n dapat ditentukan dengan menggunakan rumus m! n! untuk
m n , dan 2 m ! n ! untuk m n . Himpunan dari automorfisme graf bipartisi komplit merupakan grup karena memenuhi keempat sifat dari grup. Karena grup permutasi orde n ( S n ) adalah n! maka bentuk grup dari automorfisme graf bipartisi komplit adalah
S m S n untuk m n , dan
2 S m S n untuk m n .. Kata Kunci: grup, automorfisme, bipartisi komplit
1. PENDAHULUAN Aljabar abstrak dari matematika yang memuat tentang grup yang mencakup sistem bilangan, seperti bilangan bulat, bilangan rasional, bilangan nyata, dan bilangan kompleks terhadap penjumlahan, atau bilangan rasional, bilangan nyata, dan bilangan kompleks yang tak-nol, masing-masing terhadap perkalian. Teori grup memungkinkan sifat-sifat ini dan berbagai sistem lain untuk dipelajari dalam lingkup yang umum, dan hasilnya dapat diterapkan secara luas. Cabang matematika lainnya seperti matematika diskrit yang membahas tentang graf yang saat ini semakin berkembang dan menarik karena keunikan dan banyak sekali penerapannya diantaranya dalam menyelesaikan, mencari sebuah jalan terpendek, postman problem yaitu menentukan jarak terdekat yang dilalui oleh seorang tukang pos. Teori graf merupakan salah satu bidang matematika yang diperkenalkan pertama kali oleh ahli matematika asal Swiss, Leonardo Euler pada tahun 1736. Keunikan teori graf adalah kesederhanaan pokok bahasan yang
76
dipelajarinya, karena dapat disajikan sebagai titik dan sisi. Graf didefinisikan sebagai pasangan himpunan (V , E ) , ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidakkosong dari titik-titik dan E adalah himpunan sisi yang menghubungkan sepasang titik. Dalam penelitian ini graf yang akan dibahas adalah graf bipartisi komplit. Pada artikel, penulis membahasa graf bipartisi komplit, dimana graf tersebut merupakan graf yang titik-titiknya dapat dipartisi ke dalam 2 bagian, dimana tiap titik dari 1 bagian dihubungkan ke bagian yang lain, dan hal itu sangat menarik untuk diteliti grup automorfismenya dengan graf yang dapat dipartisi menjadi 2 bagian. 2. KAJIAN TEORITIS Operasi Biner Misalkan G himpunan tidak kosong, fungsi dari ke G G ke G mengaitkan setiap pasangan berurutan (a, b) G G dengan suatu pasangan di G (yaitu a * b G), maka * dikatakan operasi biner (komposisi biner) pada G . Dengan
Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 demikian, operasi * pada himpunan tidak kosong G adalah operasi biner jika dan hanya jika:
a G, b G a * b G, a, b G jadi operasi
biner merupakan operasi tertutup yang didefinisikan pada himpunan tidak kosong. Definisi 2.1 (i) Asosiatif, jika
Permutasi Notasi Permutasi Misalkan S = a1 , a2 ,...an yaitu himpunan terhingga yang memiliki n anggota berbeda, dan misalkan f : S S suatu permutasi, maka permutasi dapat dinotasikan sebagai berikut,
(a * b) * c a * (b * c), a, b, c G (ii) Komutatif, jika a * b b * a, a, b G (iii) Mempunyai unsur identitas, jika ada e G, sehingga e * a a * e aa G (iv) Setiap anggota mempunyai invers di G, jika a G ada a 1 G sehingga 1
1
a*a a *a e (v) Operasi * pada G dikatakan memenuhi hukum pencoretan kiri, jika a * b a * c bc mengakibatkan untuk setiap
a, b, c G
(vi) Operasi * pada G dikatakan memenuhi hukum pencoretan kanan, jika b * a c * a, b c, untuk mengakibatkan setiap
a, b, c G (vii) Anggota e G dikatakan identitas kiri di G, jika a * e a, a G (viii) jika e identitas kanan di G , maka elemen b G , dikatakan invers kanan dari a G, jika a * b e (ix) Operasi * dikatakan distributif kiri terhadap ° jika a ° (b * c) (a ° b) * (a ° c), a, b, c G Operasi * dikatakan distributif kanan terhadap ° jika. Grup Asal-usul teori grup berawal dari kerja Evariste Galois (1830), yang berkaitan dengan masalah persamaan aljabar yang terpecahkan dengan radikal. Sebelum kerja Galois, grup lebih banyak dipelajari secara kongkrit, dalam bentuk permutasi. Beberapa aspek teori grup abelian dikenal dalam teori bentuk-bentuk kuadrat.
a f 1 f (a1 )
a2
...
f (a 2 ) ...
an f (a n )
Baris yang atas merupakan dengan asal (domain) dan baris yang bawah merupakan kawannya. Komposisi Permutasi Misalkan f dan g permutasi berderajat n yang didefinisikan pada himpunan S yang mempunyai n anggota berbeda. Sesuai dengan definisi 3, f dan g merupakan fungsi satu-satu dan onto dari S ke S. oleh karena itu. Fungsi komposisi (g ° f) atau (f ° g) yang didefinisikan S sebagai berikut. (g ° f ) (x)= g(f(x)) x S dan (f ° g ) (x)= f(g(x)) x S Notasi Cycle Notasi Cycle adalah bentuk notasi dari suatu bentuk permutasi berdasarkan pada pemetaan perputaran Cycle. Grup Permutasi Suatu grup yang elemen-elemennya merupakan permutasi dengan operasi komposisi disebut grup permutasi. Secara khusus, jika sekumpulan permutasi dari suatu himpunan S yang tidak kosong (nonempty) merupakan sebuah grup dengan operasi komposisi fungsi (°), maka S disebut grup permutasi atau disebut grup simetri pada S. Jika orde dari S adalah n, maka grup simetri ini dapat ditulis Sn. Graf Definisi Graf Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang
77
Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G). Ishomorfisme Graf Graf G1 dan G2 adalah isomorfik jika terdapat fungsi satu-satu dan onto pada f dari titik-titik G1 ke titik-titik pada G2 dan fungsi satu-satu pada g dari titik-titik pada G1 sisi-sisi pada G2 , sehingga sebuah sisi incident pada f(v) di G1 dan f(w) di G2 . Pasangan fungsi f dan g disebut isomorfisme dari G1 dan G2 . 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. Misalkan diberikan graf G seperti dibawah ini. 1
2
Tabel Cayley Tabel Cayley adalah merupakan salah satu cara untuk mendefinisikan operasi biner pada himpunan, khususnya himpunan berhingga. Apabila G = {i, a, b, c, …} dengan i, a, b … elemen yang tidak didefinisikan pada objek tertentu dan dilengkapi oleh suatu operasi biner *, yang memenuhi semua sifat grup, maka (G, *) adalah grup abstrak. Grup ini merupakan pola bagi grup lainnya, dan abstrak dari elemenelemen dan operasi tertentu. Eleman identitas dalam grup abstrak tersebut dinyatakan dengan i. Operasi biner pada grup abstrak didefinisikan dengan Tabel Cayley. Apabila G = {i, a, b, c, d}, (G, *) disebut grup abstrak ordo 5. dengan operasi biner * dalam tabel Cayley adalah sebagai berikut: Tabel 2.1: Tabel Cayley (G,*) grup. * i a b c d i
i
a
b
c
d
a
a
b
c
d
i
b
b
c
d
i
a
c
c
d
i
a
b
d
d
i
a
b
c
Pada tabel tersebut, setiap anggota hanya muncul satu kali pada tiap baris dan tiap kolom dan memenuhi sifat grup. Grup dari Automorfisme Graf Sederhana
3 4
Gambar 2.14: Graf G Graf Bipartisi Komplit Sebuah graf G dikatakan bipartisi jika titik V nya dapat dipartisi kedalam dua himpunan bagian M dan N sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik dari M ke sebuah titik dari N. Dengan sebuah graf bipartisi komplit, dapat diartikan bahwa setiap titik dari M dihubungkan ke setiap titik dari N, graf ini dinyatakan dengan K m,n dimana m adalah jumlah titik di M dan n adalah jumlah titik di N.
Himpunan semua automorfisme graf G, dinotasikan dengan Aut(G), membentuk grup di bawah operasi komposisi fungsi yang dinotasikan dengan Aut(G). 3. HASIL DAN PEMBAHASAN Pada graf bipartisi komplit k 2,1 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 2 fungsi. Pada graf bipartisi komplit k 2, 2 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 8 fungsi. Pada graf bipartisi komplit k 2,3 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 12 fungsi. Pada graf
78
Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 bipartisi komplit k 2, 4 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 48 fungsi. Sedangkan pada graf bipartisi komplit k 3,1 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 6 fungsi. Pada graf bipartisi komplit k 3, 2 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 12 fungsi. Pada graf bipartisi komplit k 3,3 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 72 fungsi. Pada graf bipartisi komplit k 3, 4 banyak automorfisme dari graf tersebut ke dirinya sendiri adalah sebanyak 144 fungsi. Berdasarkan tabel 4.9 dapat dijelaskan bahwa graf bipartisi komplit k 2,1 memiliki 2 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1 dan titik 2 yang dinotasikan sebagai (1)(2) dan (1 2), sedangkan titik 3 tidak melakukan rotasi dengan titik manapun sehingga titik 3 hanya dipetakan terhadap dirinya sendiri sehingga dapat dibentuk bahwa banyaknya automorfisme untuk untuk graf bipartisi komplit k 2,1 adalah 21 . Untuk graf bipartisi komplit k 2, 2 memiliki 8 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1 dan titik 2 dan rotasi antara titik 3 dan titik 4 yang juga membentuk 2 notasi, kemudian dirotasi kembali antara titik 1 dan 2 dengan titik 3 dan 4 sehingga menghasilkan 2 notasi baru untuk setiap rotasi antara titik 1 dengan 2 dan titik 3 dengan 4 sehingga dapat dibentuk bahwa banyaknya automorfisme untuk untuk graf bipartisi komplit k 2,1 adalah 2 2 2 . Untuk graf bipartisi komplit k 2,3 memiliki 24 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1 dan titik 2 yang menghasilkan 2 notasi dan rotasi antara titik 3, 4 dan 5 yang menghasilkan 6 notasi, sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k 2,3 adalah 2 6 . Untuk graf bipartisi komplit k 2, 4 memiliki 48 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1 dan 79
titik 2 yang menghasilkan 2 notasi dan rotasi antara titik 3, 4, 5 dan 6 yang menghasilkan 24 notasi, sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k 2, 4 adalah 2 24 . Untuk graf bipartisi komplit k 3,1 memiliki 6 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1,2 dan 3 yang menghasilkan 6 notasi yaitu (1)(2)(3),(1)(2 3),(1 2)(3),(1 3)(2),(1 2 3) dan (1 3 2) sedangkan titik 4 tidak melakukan rotasi dengan titik manapun , sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k 3,1 adalah 6 1. Untuk graf bipartisi komplit k3, 2 memiliki 12 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1,2 dan 3 yang menghasilkan 6 notasi dan rotasi antara titik 4 dan 5 yang menghasilkan 2 notasi, sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k3, 2 adalah 6 2. Untuk graf bipartisi komplit k3,3 memiliki 72 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1,2 dan 3 juga rotasi antara titik 3,4 dan 5 yang juga membentuk 6 notasi, kemudian dirotasi kembali antara titik 1,2,3 dengan titik 3,4 dan 5 sehingga menghasilkan 2 notasi baru untuk setiap rotasi antara titik 1,2 dan 3 juga titik 4,5 dan 6 sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k3,3 adalah 2 6 6. Untuk graf bipartisi komplit k3, 2 memiliki 12 automorfisme dimana automorfisme tersebut diperoleh berdasarkan rotasi antara titik 1,2 dan 3 yang menghasilkan 6 notasi dan rotasi antara titik 4,5,6 dan 7 yang menghasilkan 24 notasi, sehingga dapat dibentuk bahwa banyaknya automorfisme untuk graf bipartisi komplit k3, 4 adalah 6 24. 4. KESIMPULAN DAN SARAN Kesimpulan Adapun bentuk umum dari grup automorfisme graf bipartisi komplit k m,n adalah a. S m S n untuk m n
Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 b. 2 S m S n untuk m=n Saran Hasil yang diperoleh hanyamengkaji salah satu graf partisi n komplit, yang terbatas pada 2 partisi. Oleh karena itu penulis menyarankan agar pembaca mencoba untuk mengkaji graf partisi n komplit dengan partisi yang lebih besar dan dapat membuat program untuk menentukan suatu automorfisme. 5. Daftar Pustaka Abdussakkir,.Teori Graph. Penerbit: UINMalang Press, 2009. Budayasa I Ketut,.Teori Graph dan Aplikasinya. Penerbit: Unesa University Press – 2007. Viii, 252 hal.,lllus, 21. Damayanti, Reni try, Jurnal
[email protected], (vol 2, no 1; 2011), ISSN: 2086–0382. (diakses tanggal 17 Januari 2013)
Darminto, Priyo Bambang. Grup Permutasi, Grup Dihedral.(http://wwwgroup.dcs.st.and.ac.uk/~history/.). (diakses Tanggal 13 november 2012). Jek, Jong Siang, Matematika Diskrit dan Aplikasinya Pada Komputer. Yogyakarta: Andi, 2009 Johnsonbaugh, Richard,.Matematika Diskrit. Jakarta: Prenhallindo,1998 Munir, Rinaldi, Matematika Diskrit. Bandung: Informatika, 2005 Seymour Lipschuts, Marc Lars Lipson. Matematika Diskrit. Jakarta: Salemba Teknika, 2002. Tahmir, Suradi, Teori grup.Makassar: Andira Publisher, 2004. Wibisono, Samuel. Matematika Diskrit. Penerbit: Graha Ilmu, 2008
80
