6. Reni Damayanti AUTOMORFISME GRAF BINTANG DAN GRAF LINTASAN Reni Tri Damayanti Mahasiswa Pascasarjana Jurusan Matematika Universitas Brawijaya Email: si_cerdazzz@rocketmail.com ABSTRAK 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 ������ ������ ntuk mencari automorfisme pada suatu graf, biasanya dilakukan dengan menentukan semua kemungkinan fungsi yang satu-satu, onto, dan isomorfisme dari himpunan titik pada graf tersebut. Sehingga berdasarkan hal itu dapat diketahui dan diuraikan automorfisme graf bintang dan graf lintasan serta penjabarannya. 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: (a) untuk n genap: �� ����� ������� ������� … ������� �!, untuk n ganjil: �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % dan (b) �� =��� ��� ��� …��� . Kata Kunci: graf bintang � �,� , graf lintasan ��, isomorfisme graf, automorfisme graf, dan grup simetri PENDAHULUAN Graf didefinisikan sebagai himpunan titik (vertek) yang tidak kosong dan himpunan garis atau sisi (edge) yang mungkin kosong. Himpunan titik dari suatu graf G dinyatakan dengan V(G) dan himpunan sisi dinyatakan dengan E(G). Salah satu topik yang menarik untuk dikaji pada teori graf adalah tentang automorfisme graf. Automorfisme dari suatu graf G merupakan suatu permutasi dari himpunan titik-titik V(G) atau himpunan sisi-sisi dari graf G (E(G)). Dengan kata lain, automorfisme dari suatu graf G adalah isomorfisme dari graf G ke dirinya sendiri, yaitu fungsi yang memetakan ke dirinya sendiri. Pada bab ini akan dibahas mengenai automorfisme suatu graf pada graf bintang dan graf lintasan. Pada graf bintang, teorema yang dibangun adalah (1) banyaknya fungsi permutasi yang automorfisme, (2) bentuk fungsi permutasi yang automorfisme yaitu titik v1� &� �,�� yang selalu dipetakan ke dirinya sendiri sedangkan titik lainnya dapat dipetakan ke sebarang titik kecuali v1. Sedangkan pada graf lintasan, teorema yang dibangun adalah banyaknya fungsi permutasi yang automorfisme dari graf �� yaitu hanya 2 fungsi yang dibedakan berdasarkan banyak titik genap dan ganjil. Kemudian mengetahui bahwa grup automorfisme dari graf bintang �,� isomorfik dengan grup simetri '� dan grup automorfisme dari graf lintasan �� isomorfik dengan grup siklik orde-2 �(� . GRAF LINTASAN DAN GRAF BINTANG Definisi 1. Graf lintasan adalah graf yang terdiri dari sebuah lintasan tunggal. Graf lintasan dengan � verteks dilambangkan oleh ��. Perhatikan bahwa �� memiliki �-tepi, dan dapat diperoleh dari graf siklus )� dengan menghapus sebuah sisi. Contoh 1: 2P 3P 4P1P Gambar 1. Graf Lintasan Dari gambar 1. di atas, graf P1 hanya mempunyai satu titik, maka P1 tidak mempunyai sisi. Pada graf P2 mempunyai dua titik dan satu sisi. Pada graf P3 mempunyai tiga titik dan dua sisi. Sedangkan, pada graf P4 mempunyai empat titik dan tiga sisi. Jadi, penulis dapat menentukan beberapa ciri khusus dari graf lintasan ��adalah setiap titik ujung dan titik pangkal selalu berderajat 1 dan titik selain titik ujung dan titik pangkal selalu berderajat 2. Reni Damayanti 36 Volume 2 No. 1 November 2011 Definisi 2. Suatu graf G lengkap partisi-� adalah graf partisi-� dengan himpunan-himpunan partisi &�,&�,…,&� yang memiliki sifat tambahan yaitu jika * � &+ dan � � &,, - . / maka *� � ��0 . Jika |&+| �+, kemudian graf ini dinotasikan dengan �2�,2�,…,2� . (Order pada bilangan 2�,2�,… ,2� tidak penting.) Ingat bahwa graf lengkap partisi-� adalah lengkap jika dan hanya jika 2+ 1 untuk semua -, dalam hal ini adalah �. Jika 2+ 4 untuk semua -, kemudian graf lengkap partisi-� adalah tetap dan dinotasikan dengan ��� . Maka, ��� 5 �. Suatu graf bipartisi lengkap dengan himpunan partisi &� dan &�, dimana |&�| 6 dan |&�| �, kemudian dinotasikan dengan �6,� . Graf �1,� disebut graf bintang. Contoh 2: Gambar 2 Graf Bipartisi Definisi 3. Dua buah graf G1 dan G2 dikatakan iso- morfik jika terdapat pemetaan satu-satu ϕ antara V(G1) pada V(G2) sedemikian hingjga misal *� � ��0� jika dan hanya jika (ϕ(u)ϕ(v)) � E(G2). Jika G1 isomorfis terhadap G2 dapat dikatakan bahwa G1 dan G2 saling isomorfik dan dapat ditulis G1 ≅ G2. Contoh 3: Gambar 3. G1 isomorfik dengan G2 tetapi tidak Isomorfik dengan G3 Pemetaan ϕ: V(G1) → V(G2) didefinisikan oleh: Gambar 4. Pemetaan Satu-satu ���� *�, ���� *�, ���� *�, ���7 *7 Akan dibuktikan bahwa (v1,v2), (v1,v3), (v1,v4), (v2,v3), (v2,v4), (v3,v4)� E(G1) jika dan hanya jika (ϕ(v1),ϕ(v2)), (ϕ(v1),ϕ(v3)), (ϕ(v1),ϕ(v4)), (ϕ(v2),ϕ(v3)), (ϕ(v2),ϕ(v4)), (ϕ(v3),ϕ(v4)) � E(G2). ���,�� � ��0� dan ����� ,���� � �*�,*� � ��0� ���,�� � ��0� dan ����� ,���� � �*�,*� � ��0� ���,�7 � ��0� dan ����� ,���7 � �*�,*7 � ��0� ���,�� � ��0� dan ����� ,���� � �*�,*� � ��0� ���,�7 � ��0� dan ����� ,���7 � �*�,*7 � ��0� ���,�7 � ��0� dan ����� ,���7 � �*�,*7 � ��0� Berdasarkan uraian diatas terbukti bahwa G1 ≅ G2. Definisi 4 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). Jika ϕ adalah suatu automorfisme dari G dan v�V(G) maka ������� ������ . Contoh 4: Misal diberikan graf G seperti di bawah ini: Gambar 5. Graf G Diberikan pemetaan �:&�0 9 &�0 , maka automorfisme yang mungkin dari graf G di atas adalah: G1 v5 v1 v3 v4 v2 v6 v7 v5 v1 v3 v4 v2 v6 v7 G2 G3 v3 v4 v2 v1 G2 u3 u4 u2 u1 G1 ϕ V(G1) V(G2) v3 v4 v2 v1 v3 v4 v2 v1 2 1 3 4 Automorfisme Graf Bintang dan Graf Lintasan Jurnal CAUCHY – ISSN: 2086-0382 37 ��1 1 ��2 2 ��3 3 ��1 2 ��2 3 ��3 1 ��1 3 ��2 1 ��3 2 ��1 1 ��2 3 ��3 2 ��1 1 ��2 3 ��3 2 ��1 1 ��2 3 ��3 2 HASIL DAN PEMBAHASAN Berikut ini ditentukan banyaknya automorfisme dari masing-masing graf ke dirinya sendiri berdasarkan bentuk-bentuk permutasi yang mengacu pada pemetaan titiknya yang memenuhi fungsi tersebut, dengan pola sebagai berikut: Graf Bintang Pada graf bintang banyaknya automorfisme yang mengacu pada pemetaan titiknya sebagai berikut: Dari penjelasan tentang automorfisme pada graf bintang berdasarkan bentuk-bentuk permutasi yang mengacu pada pemetaan titiknya yang memenuhi fungsi tersebut, maka dapat dibuat tabel banyaknya automorfisme dari kemungkinan banyak fungsi tersebut melalui tempat kedudukan titik-titiknya dengan bentuk fungsi �1 �……… <=>=? � : Tabel 2 Banyaknya Automorfisme Melalui Bentuk Permutasi Titiknya dari �,� Graf Bintang ( �,�) Σ fungsi berbentuk �……… <=>=?� �,� 1 1 1! �,� 2 2 · 1 2! �,7 6 3 · 2 · 1 3! �,A 24 4 · 3 · 2 · 1 4! �,C 120 5 · 4 · 3 · 2 · 1 5! … … … �,� ��� E 1 �� E2 …2· 1 �! Tabel 1. Banyaknya Automorfisme dari G(K�,G) → G(K�,G) Graf Bintang Automorfisme Banyaknya Automorfisme �,� α = (1)(2)(3) 1 2 α = (1)(. .) 1 �,� α = (1)(2)(3)(4) 1 6 α = (1)( . . . ) 2 α = (1)( . )( . . ) 3 �,7 α = (1)(2)(3)(4)(5) 1 24 α = (1)( . . . . ) 6 α = (1) (.) (. . .) 8 α = (1)( . )( . )( . . ) 6 α = (1)( . . )( . . ) 3 �,A α = (1)(2)(3)(4)(5)(6) 1 120 α = (1)( . . . . . ) 24 α = (1)( . )( . . . . ) 30 α = (1)( . )( . )( . . . ) 20 α = (1)( . )( . )( . )( . . ) 10 α = (1)( . )( . . )( . . ) 15 α = (1)( . . )( . . . ) 20 �,C α = (1)( . . . . . .) 120 120 Atau dapat ditulis φ= (1) (2) (3) Atau dapat ditulis φ= (1 2 3) Atau dapat ditulis φ= (1 3 2) Atau dapat ditulis φ= (1) (2 3) Atau dapat ditulis φ= (2) (1 3) Atau dapat ditulis φ= (3) (1 2) Reni Damayanti 38 Volume 2 No. 1 November 2011 Dari uraian automorfisme graf bintang di atas maka berdasarkan banyak titik dapat dibuat teorema tentang banyak automorfisme dari graf �,� untuk � bilangan asli yang fungsinya berbentuk (1) �……… <=>=? � , yaitu sebagai berikut: Teorema 1 Graf bintang-� ( �,�) memiliki �+1 titik. Banyaknya automorfisme dari graf tersebut adalah �!. Diketahui: misalkan � adalah automorfisme dari �,� ke dirinya sendiri. Akan dibuktikan: ���� �� dan ���� �� dengan I . 1 dan 4 . 1. Bukti Graf �,� memiliki � M 1 titik. Misalkan titik-titiknya adalah &� �,�� ���,��,��,… ,�� � . Misalkan � adalah automorfisme dari �,� ke dirinya sendiri. Karena α(��) = ��, yang berarti mengawetkan derajat �� itu sendiri, sehingga banyaknya titik yang dapat dipermutasikan adalah sebanyak � titik, maka permutasinya dapat dirumuskan sebanyak �!. Selanjutnya, akan ditunjukkan bahwa ���� �� dan ���� ��. Karena derajat titik �� 1 sehingga ���� �� juga mengawetkan derajat titiknya. Andaikan ���� �� dengan I . 1 dan �� �N �I . 4 . 6 . Gambar 6. bintang-� ( �,�) ���,�� � �� �,� �����,�� ����� ,���� ���,�N O �� �,� Jadi, ���� �� maka � bukan automorfisme. Sehingga, pengandaian I . 1 salah. Jadi, seharusnya pengandaian menjadi I 1 atau ���� ��. Dari teorema 1 di atas, maka dapat diturunkan teorema sebagai berikut: Teorema 2 Grup automorfisme dari graf bintang �,�isomorfik dengan grup simetri '� atau �'�,P 5 �Q� �,��,P�. Bukti Akan ditunjukkan ada korespondensi satu- satu dari anggota �'�,P pada �Q� �,��,P�. Buat pemetaan R dari '� ke Q� �,�� dengan aturan sebagai berikut (contoh dapat dilihat pada lampiran): Jika� � '�dengan � ��� �� �� … �S ,1 T U T � Maka ↓ ↓ ↓ ↓ R�� ��V$ � �V� � �VW � … �VX �� Karena � dan R�� korespondensinya sama, maka bentuk permutasinya sama. Dapat ditunjukkan bahwa R bersifat bijektif dan homomorfisme. Jika Y,Z � '� dan R�Y ,R�Z � Q� �,�� Maka Y 9 R�Y Z 9 R�Z Jadi, R�YZ R�Y R�Z Dengan demikian R adalah isomorfisme. Jadi, �'�,P 5 �Q� �,��,P� terbukti. Graf Lintasan Pada graf lintasan banyaknya automorfisme yang mengacu pada pemetaan titiknya sebagai berikut: Tabel 3 Banyaknya Automorfisme dari G(Pn) → G(Pn) Graf Lintasan Automorfisme Banyaknya Automorfisme P2 β = (1)(2) 1 2 β =(1 2) 1 P3 β =(1)(2)(3) 1 2 β =(1 3)(2) 1 P4 β =(1)(2)(3)(4) 1 2 β =(1 4)(2 3) 1 P5 β =(1)(2)(3)(4)(5) 1 2 β =(1 5)(2 4)(3) 1 P6 β =(1)(2)(3)(4)(5)(6) 1 2 β = (1 6)(2 5)(34) 1 Dari tabel 3 di atas, maka dapat dibuat bentuk umum dari banyaknya fungsi permutasi yang automorfisme sebagai berikut: 1 �� Automorfisme Graf Bintang dan Graf Lintasan Jurnal CAUCHY – ISSN: 2086-0382 39 Tabel 4. Bentuk Umum Automorfisme dari G(Pn) → G(Pn) Berdasarkan Banyak Titik Genap dan Ganjil �Genap �� ��� ��� ��� …��� sebanyak 1 �� ����� ������� ������� … "������ �% �Ganjil �� ��� ��� ��� …��� sebanyak 1 �� ����� ������� ������� … "�� �� ���� �� �%"�� �� % Dari uraian automorfisme graf lintasan di atas maka berdasarkan banyak titik dapat dibuat teorema tentang banyak automorfisme dari graf Pn, yaitu sebagai berikut: Teorema 3 Dari graf lintasan �� maka banyaknya automorfisme hanya ada 2 fungsi yang berbentuk: a. Untuk n genap, permutasinya berbentuk: �� ����� ������� ������� … ������� �! dan �� = ��� ��� ��� …��� b. Untuk n ganjil, permutasinya berbentuk: �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % dan �� = ��� ��� ��� …��� Bukti a. Untuk n genap, permutasinya berbentuk: �� ����� ������� ������� … "������ �% Sehingga, ���� �� → mengawetkan derajat titik 1 ���� ���� → mengawetkan derajat titik 2 ���� ���� → mengawetkan derajat titik 2 ↓ ↓ �����! ����� �! → mengawetkan derajat titik 2 ↓ ↓ ������ 2 → mengawetkan derajat titik 2 ���� 1 → mengawetkan derajat titik 1 Karena graf lintasan (��) ini jumlah titiknya genap, maka ���� ,��� � � ���� Sehingga, ����� ,��� � ����� ,���� � ���,���� � ���� ���� ,��� � � ���� Sehingga, ����� ,��� � ����� ,���� � �����,���� � ���� [����!,���� �!\ � ���� Sehingga, �[����,��� �!\ [�����!,����� �!\ ���� �,���! ����,��� �! � ���� Begitu pula untuk ������ ,��� � � ���� Sehingga, ������� ,��� � ������� ,���� � ���,�� � ���� Jadi,�� ����� ������� ������� … ������� �! terbukti automorfisme. Selanjutya, untuk fungsi identitas tidak perlu ditunjukkan karena sudah jelas automorfisme. b. Untuk n ganjil, permutasinya berbentuk: �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % Sehingga, ���� �� → mengawetkan derajat titik 1 ���� ���� → mengawetkan derajat titik 2 ���� ���� → mengawetkan derajat titik 2 ↓ ↓ �"��#$� ����#$� �% �"��#$� % → mengawetkan derajat titik 2 ↓ ↓ ������ 2→ mengawetkan derajat titik 2 ���� 1 → mengawetkan derajat titik 1 Maka, ���� ,��� � � ���� Sehingga, ����� ,��� � ����� ,���� � ���,���� � ���� ���� ,��� � � ���� Sehingga,����� ,��� � ����� ,���� � �����,���� � ���� ["��#$� ��,��#$� �%\ � ���� Sehingga, �["�� �� ��,�� �� �%\ Reni Damayanti 40 Volume 2 No. 1 November 2011 ]�[�� �� ��,�"�� �� �%\^ "��#$� ��,��#$� �% � ���� Begitu pula untuk ������ ,��� � � ���� Sehingga, ������� ,��� � ������� ,���� � ���,�� � ���� Jadi, �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % adalah automorfisme. Jadi, berdasarkan pada bagian a dan b maka teorema terbukti benar. Setelah mengetahui banyaknya automorfisme graf lintasan (��) hanya ada 2 fungsi yaitu yang berbentuk: �� ��� ��� ��� …��� dan �� ����� ������� ������� … ������� �! untuk � genap �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % untuk � ganjil, Dari teorema 3 di atas, maka dapat diturunkan teorema sebagai berikut: Teorema 4 Grup automorfisme dari graf lintasan ��isomorfik dengan grup siklik orde-2 �(� atau �(�,P 5 ���,P . Bukti Misalkan �(�,P 5 ���,P . Akan ditunjukkan ada korespondensi satu- satu dari anggota �(�,P pada �Q��� ,P . Misalkan (� = {τ�,τ�} dan Q��� `a�,a�b. Selanjutnya, anggota (� dikorespondensikan satu-satu pada titik-titik dari �� sebagai berikut: τ�~a� τ�~a� untuk � genap maupun � ganjil Karena dari teorema 3 grup automorfisme graf lintasan �� dan grup siklik orde-2 �(� adalah 2, jadi ���,P 5 �(�,P . Selanjutnya, untuk fungsi identitas tidak perlu ditunjukkan karena sudah jelas automorfisme. PENUTUP Dari hasil dan pembahasan, secara umum dapat disimpulkan bahwa: 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 ��,��,�� � �� �,� . 2. Dari graf lintasan �� maka banyaknya automorfisme hanya ada 2 fungsi yang berbentuk: a. Untuk n genap, permutasinya berbentuk: �� ����� ������� … ������� �! dan �� = ��� ��� ��� …��� b. Untuk n ganjil, permutasinya berbentuk: �� ����� ������� ������� … "��#$� ����#$� �%"��#$� % dan �� = ��� ��� ��� …��� 3. Grup automorfisme dari graf bintang �,� isomorfik dengan grup simetri '� atau �'�,P 5 �Q� �,��,P�. 4. Grup automorfisme dari graf lintasan �� isomorfik dengan grup siklik orde-2 �(� atau �(�,P 5 ���,P . DAFTAR PUSTAKA [1] Wilson, R.J. dan Watkins, J. J. 1990, Graphs An Introductory Approach, Canada: John Wiley and Sons, Inc. [2] Chartrand, Gery dan Lesniak, Linda, 1986, Graphs and Digraphs Second Edition, Hal. 5, 10, 250, California: A Division of Wadsworth, Inc.