Automorfisme Graf bintang dan Graf lintasan

INDONESIA:

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 deg φ(v)=degG(v). 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. Tujuan penelitian ini adalah untuk mengetahui dan menguraikan automorfisme graf bintang dan graf lintasan serta penjabarannya.

Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research), dengan langkah-langkah penelitian sebagai berikut: (1) Merumuskan masalah; (2) Menggambarkan graf bintang (K_1,2 sampai K_1,6) dan graf lintasan (P_2 sampai P_6); (3) Memberikan label pada setiap titik dari masing-masing graf yang telah digambarkan; (4) Menentukan semua kemungkinan fungsi permutasi yang satu-satu dan onto dari setiap graf pada dirinya sendiri; (5) Memilah fungsi permutasi yang automorfisme dan tidak automorfisme dari semua kemungkinan fungsi; (6) Menentukan karakteristik dari fungsi permutasi automorfisme; (7) Membangun teorema tentang banyak fungsi permutasi yang automorfisme dan bentuk fungsi permutasinya, serta pembuktiannya; (8) Menunjukkan bahwa himpunan automorfisme dari graf bintang dan graf lintasan dengan komposisi fungsi adalah membentuk grup.

Berdasarkan hasil pembahasan, dapat diperoleh (1) Graf bintang-n (K_1,n) memiliki n+1 titik, banyaknya automorfisme dari graf tersebut adalah n! Permutasinya α adalah automorfisme yang harus mengawetkan derajat titik-titiknya, oleh karena itu permutasinya harus berbentuk α(v_1)=v_1 dan α(v_k)=vt untuk setiap v_1,v_k,v_t ∈ E(K_1,n). Jika α(K_1,n)=(v_1,v_2,v_3,...v_n) fungsi bijektif maka α(K_1,n) merupakan automorfisme; (2) Dari graf lintasan Pn maka banyaknya automorfisme hanya ada 2 fungsi permutasi yang berbentuk: (1) untuk n genap: ... untuk n ganjil: ...

ENGLISH:

One of the this topic of interesting to be studied by at graph theory is about graph automorphism. Automorphism at one particular graph of G is isomorphism of graph of G to G itself. Equally, graph automorphism of G represent an permutation of vertices set of V(G) or edges of graph of G, E(G) to itself. If ... is an automorphism of G and of ... hence ... To look for automorphism at one particular graph in circuit, is usually conducted by determining all possibility of function which is one-to-one, onto, and isomorphism of vertices set at graph. Target of this research is to know and elaborate an automorphism of star graph and path graph and also its formulation.

In this research, research method the used is method research of book (library research) with the following research steps: (1) Formulating problem, (2) Drawing a star graph (... until ... ) and path graph (... until ...); (3) Giving vertex label of each vertices at each graph; (4) Determining all of possibility one-to-one function and onto from each graph to itself; (5) Classifying the function are automorphism and not automorphism from of all possibility function already written; (6) Determining the characteristic from automorphism function; (7) Proving real correct conjecture in general; (8) Showing that the set of automorphism together with composition function be a group.

Based on result of solution can be obtained (1) Star Graph ... has n+1 vertex, the number of automorphism from mentioned graph is n! Let ... is an automorphism of ... to itself, thus ... and ... for each ... If ... is a bijection function, then ... is automorphism; (2) There are two automorphism functions of path graph. These are: (1) to even n, the permutation form is ... to odd n, the permutation form is ... and ...