GRAF DAN BEBERAPA GRUP TERKAIT; GRAPHS AND SOME RELATED GROUPS

RESTI SULISTIANINGRUM, Diah Junia Eksi Palupi

2011 | Skripsi | PROGRAM STUDI MATEMATIKA

Graf terdiri dari himpunan titik-titik (vertex) dan himpunan garis-garis (edge). Dalam tugas akhir ini yang akan dipelajari adalah graf sederhana, yaitu graf komplit, graf sirkuit dan graf bipartit. Dalam graf, dikenal istilah adjacency, yaitu kedekatan antara dua buah vertex atau edge. Oleh karena itu, dapat dibentuk suatu fungsi/pemetaan yang mengkaitkan elemen-elemen (dalam hal ini vertex atau edge) dari suatu graf ke elemen-elemen graf lain. Dengan kata lain, jika diberikan graf sederhana G dan H maka dapat dibentuk korespondensi satu-satu (pemetaan bijektif) antara dua buah graf yang mengawetkan adjacency. Pemetaan ini yang disebut dengan isomorfisma graf. Isomorfisma yang mengkaitkan vertexvertex dalam graf G dengan vertex-vertex dalam graf H disebut isomorfisma vertex. Sedangkan isomorfisma yang mengkaitkan edge-edge dalam graf G dengan edge-edge dalam graf H disebut isomorfisma edge. Selanjutnya, isomorfisma suatu graf dengan dirinya sendiri disebut automorfisma graf. Himpunan dari semua automorfisma graf G membentuk grup yang disebut dengan grup automorfisma graf G*. G* dari graf komplit (Kn) adalah grup simetris, sedangkan G* dari graf sirkuit (Cn) adalah grup dihedral. Jika H* subgrup G*, maka H* dari Kn adalah grup alternating, sedangkan H* dari Cn adalah grup siklik (sekaligus grup abelian). Adjacency dari suatu graf dapat direpresentasikan dalam bentuk matriks yang disebut matriks adjacency. Jika nilai eigen dari matriks adjacency graf sederhana G semuanya berbeda, maka G* merupakan grup abelian. Aksi grup automorfisma G* pada himpunan vertex-vertex V(G) merupakan pemetaan bijektif yang asosiatif. Melalui aksi grup inilah dapat ditemukan struktur graf transitif vertex, graf transitif edge dan graf transitif jarak

Kata Kunci : Graf; beberapa grup terkait