Grup Automorfisme dari graf lengkap dan graf sikel

INDONESIA:

Isomorfisme dari graf G ke dirinya sendiri disebut sebagai Automorfisme dari graf G dengan kata lain automorfime dari graf G merupakan suatu permutasi dari himpunan titik-titik V(G) atau sisi-sisi dari graf G,E(G). Jika ϕ adalah suatu automorfisme dari G dan v∈V(G) maka degϕv = deg v, sedangkan grup automorfisme dari graf G adalah grup permutasi dari semua automorfisme graf G yang dinotasikan dengan A(G). Graf terbagi dalam beberapa kelas, diantaranya yaitu graf lengkap dan graf sikel. Dalam penelitian ini automorfisme dari graf sederhana akan dikembangkan ke graf sederhana yang lebih khusus lagi yaitu graf lengkap dan graf sikel.

Permasalahan yang diangkat dalam penelitian ini adalah bagaimana bentuk grup automorfisme dari graf lengkap dan graf sikel. Dari definisi automorfisme graf lengkap dan graf sikel akan diberikan beberapa contoh sehingga diperoleh bentuk umum dari automorfisme graf lengkap dan graf sikel, yang selanjutnya akan diselidiki bentuk grup dari automorfisme graf lengkap dan graf sikel tersebut.

Berdasarkan hasil penelitian diperoleh bentuk grup automorfisme graf lengkap adalah grup simetri karena sifat dari graf lengkap yang setiap simpulnya dapat dipetakan ke semua simpul sehingga anggota himpunan automorfisme dari graf lengkap juga merupakan anggota himpunan dari grup simetri, dimana banyaknya angota himpunan grup simetri adalah n!.

Sedangkan bentuk grup dari automorfisme graf sikel adalah grup dihedral, karena sifat dari graf tersebut yang merupakan lintasan tertutup, sehingga automorfisme dari graf sikel hanya bisa diperoleh dari operasi rotasi sebanyak n, dan operasi refleksi sebanyak n juga, maka banyaknya automorfisme tersebut adalah 2n dimana anggota himpunan automorfisme dari graf sikel merupakan anggota himpunan dari grup dihedral.

ENGLISH:

An automorphism of a graph G is isomorphism of G with it self, that is, a permutation on V(G) that preserves adjacency. It is an immediate consequence of the definition that if ϕ is an automorphism of G and v∈V(G), then degϕv = deg v. The set of all automorphism of a graph G denoted by A(G) called automorphism group from graph G. Graph divided on some of
classes, that are, complete graph and cycle graph. In this examination, automorphism from simple graph will develop into simple graph with more specialization, namely complete graph and cycle graph.

The problem in this examination is how to know the shape of automorphism group from complete graph and cycle graph. First step to answer the question is found the definition of complete graph automorpism and cycle graph, after known the definition of it, writer will give some examples, so can found the general shape from complete graph automorphism and cycle graph. A final step is observed more accurate the shape of group from complete graph automorphism and cycle graph.

Based on this examination, found the shape of group complete graph automorphism is symmetric group, because the propertie of complete graph is every vertex can mapped to all vertex, so that the member of set from complete graph automorphism also is a member of symmetric group and sum member of symmetric group is n!.

In the other side, the shape of group from cycle graph automorphism is dihedral group, because the property of cycle graph is closed path, so that automorphism of cycle graph can found from rotation (n) and reflection (n). So sum of automorphism is 2n, wich the member of set from cycle graph automorphism also is a member of dihedral group.