Pola banyaknya graf yang tidak saling isomorfik menggunakan teorema polya

INDONESIA:

Salah satu kajian teori graf yang menarik untuk diteliti adalah kajian tentang graf yang tidak saling isomorfik. Tujuan penelitian ini adalah mencari pola banyaknya graf yang tidak saling isomorfik menggunakan teorema Polya.

Metode penelitian yang digunakan dalam penelitian ini adalah studi kepustakaan dengan tahapan analisis yang diawali dengan mengidentifikasi banyaknya titik pada graf dengan order n=2,3,…,8. Langkah selanjutnya menentukan banyaknya anggota grup simetri pada titik yang akan dihitung, menentukan semua bentuk tipe untai dan banyak anggota dari bentuk tipe untai tersebut, lalu menentukan bentuk indeks sikelnya dan menentukan keseluruhan perubahan indeks sikel dengan cara mencari pembangkit dari grup S_n (permutasi titik pada graf) yaitu grup R_n (permutasi sisi pada graf). Akan didapatkan indeks sikel grupnya, yaitu:
Z(g:x_1,x_2,x_3,x_4,…,x_n )≡1/m ∑_(g∈G)▒Z(g:x_1,x_2,x_3,x_4,…,x_n ) .
Setelah didapatkan indeks sikel grupnya akan diaplikasikan ke dalam teorema Polya I dan teorema Polya II. Hasil penelitian ini adalah:
a. Terdapat 1 jenis graf yang dapat dibuat dari titik sebanyak n tanpa sisi, n∈N.
b. Terdapat 1 jenis graf yang dapat dibuat dari titik sebanyak n≥2 dengan sisi sebanyak 1, n∈N.
c. Terdapat 2 jenis graf yang tidak saling isomorfik yang dapat dibuat dari titik sebanyak n≥4 dengan sisi sebanyak 2, n∈N.
d. Terdapat 5 jenis graf yang tidak saling isomorfik yang dapat dibuat dari titik sebanyak n≥6 dengan sisi sebanyak 3, n∈N.
e. Terdapat 11 jenis graf yang tidak saling isomorfik yang dapat dibuat dari titik sebanyak n≥8 dengan sisi sebanyak 4, n∈N.
Bagi penelitian selanjutnya dapat dilakukan pada jenis graf-graf yang lainnya.

ENGLISH:

One of an interesting study of graph theory is the study of non-mutually isomorphic graphs. The purpose of this research is to determine the pattern of the number of graphs that are not mutually isomorphic using the Polya’s theorem.

The research method used in this research is the study of literature in which the step is begun with identifying the number of vertices on the graph of order n=2,3,…,8. The next step is determining the number of members of symmetry group at the vertex to be calculated, determining all forms of cycle type and the number of members of the cycle type form, then determining the cycle index form and determining the overall cycle index change by finding the generating of group S_n (the vertex permutation of the graph) namely the group R_n (the edge permutations of the graph). Getting cycle index group that is obtained, namely: Z(g:x_1,x_2,x_3,x_4,…,x_n )≡1/m ∑_(g∈G)▒Z(g:x_1,x_2,x_3,x_4,…,x_n ) . After the new cycle index group obtained, then it is applied into the Polya I and Polya II theorem. The results of this study:
a. There is one graph kind that can be made from n vertices without edges, n∈N.
b. There is one graph kind that can be made from n≥2 vertices with one edge, n∈N.
c. There are two graph kinds that are not mutually isomorphic that can be made from n≥4 vertices with two edges, n∈N.
d. There are five graph kinds that are not mutually isomorphic that can be made from n≥6 vertices with three edges, n∈N.
e. There are eleven graph kinds that are not mutually isomorphic that can be made from n≥8 vertices with four edges, n∈N.
The next research can be done on the other type of graphs.