SIFAT-SIFAT GRAF CAYLEY GRUP Sn

Afifan Hadi; Kiki Ariyanti Sugeng

Afifan Hadi Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia
Kiki Ariyanti Sugeng Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia

Keywords: Grup simetri, graf Cayley, transposisi, reversal

Abstract

Grup merupakan suatu struktur aljabar berupa himpunan tak kosong yang apabila didefinisikan suatu operasi biner harus memenuhi empat sifat yaitu: tertutup, berlaku aturan asosiatif, terdapat elemen identitas, serta tiap elemen memiliki elemen invers. Graf Cayley merupakan graf yang berupa representasi elemen-elemen suatu grup sebagai simpul-simpul di graf serta keberadaan busur ditentukan oleh suatu subhimpunan pembangkit dari grup yang tidak mengandung elemen identitas grup. Pada paper ini akan dibahas beberapa jenis graf Cayley yang dibentuk dari grup simetri dengan subhimpunan pembangkit berupa transposisi dan reversal, akan ditunjukkan pula konstruksinya, serta sifat-sifat dasar yang terkait graf Cayley yang dibentuk dengan tujuan untuk memberikan gambaran tentang graf Cayley dari grup simetri.

Downloads

Download data is not yet available.

References

[1] Steinhardt, J., “Cayley Graphs Formed by Conjugate Generating Sets of Sn”, arXiv preprint arXiv:0711.3057 (2007).
[2] Konstantinova, E., “Some Problems on Cayley Graphs”, Linear Algebra and its applications, 429(11-12), 2754-2769 (2008).
[3] Bhatia, S., Egri-Nagy, A., Serdoz, S., Praeger, C. E., Gebhardt, V., & Francis, A. “A Path-deformation Framework for Determining Weighted Genome Rearrangement Distance”. Frontiers in Genetics, 11, 1035 (2020).
[4] Otness, K. T. “Graph Convolutions and Machine Learning” (Doctoral dissertation). [internet] (diunduh pada 8 Oktober 2021) tersedia pada http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811540 (2018).
[5] Herstein, I. N., Abstract Algebra (3rd ed.), Prentice Hall, Inc (1996).
[6] Wilson, R. J., Introduction to Graph Theory (5th ed.), Pearson (2010).
[7] Gallian, J. A., Contemporary Abstract Algebra (9th ed.), Cengage Learning (2015).
[8] Conrad, K., “Generating sets”, [internet] (diunduh pada 21 Juni 2021), tersedia pada https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf
[9] Konstantinova, E., “Vertex Reconstruction in Cayley Graphs”, Discrete Mathematics, 309(3), 548-559 (2009).
[10] West, D. B., Introduction to Graph Theory (Vol. 2), Prentice Hall, Inc (2001).