Automorfisme graf roda dan graf tangga

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 graf awalnya. Jika ... adalah suatu automorfisme dari G dan ... V(G) maka ... 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 roda dan graf tangga 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 roda dan graf tangga sebagai data; (3) Memberi label pada setiap titik pada masing-masing graf; (4) Menentukan semua kemungkinan fungsi yang satu-satu dan onto dari setiap graf pada dirinya sendiri; (5) Memilah fungsi yang isomorfisme dari semua kemungkinan fungsi yang satu-satu dan onto; (6) Menentukan karakteristik dari fungsi isomorfisme; (7) Membuktikan konjektur benar secara umum.

Berdasarkan hasil pembahasan, dapat diperoleh (1) Automorfisme pada graf Roda Wn dimana n bilangan prima maka fungsi automorfismenya sebanyak n-1; (2) Automorfisme pada graf tangga Ln yang berpola (1 . . . . ) hanya ada pada graf tangga L2; (3) Himpunan fungsi yang automorfisme pada graf roda-3 (W3) membentuk grup bila dikenai oleh fungsi komposisi.

Automorfisme graf roda dan graf tangga diaplikasikan untuk mencari banyaknya fungsi yang automorfisme pada graf roda dengan pola (1)(. . .) dan graf tangga dengan pola (1 . . . ). Sehingga, pada penelitian selanjutnya penulis menyarankan untuk melanjutkan penelitian automorfisme pada bentuk pola yang lain atau jenis graf yang lain.

ENGLISH:

One of interesting topics in graph theory is graph automorphism. Let ... is bijective function from G to itself and ... is isomorphism then ... is automorphism. In other words automorphism graph G is a permutation of the set points V(G) or the sides of graph G, E (G). If ... is a automorphism of G and v ... V(G) then degG ...(v) = degG v. In this research automorphism on a graph usually by probability of bijective function and isomorphism the set point of the graph. The object of study is knowing and describe to automorphism of wheel graph and ladder graph.

The method of study is library research with steps of research are: (1) Formulate the problem, (2) Describe of the wheel graph and ladder graph, (3) Labeling of point to graph, (4) Determine bijective function from graph to itself, (5) Classify graph isomorphism, (6) Determine the characteristics of graph isomorphism; (7) Prove the conjecture.

According to discussion have (1) Wheel graph-n (Wn) automorphism where n is prime number the automorphism function is n-1, (2) Ladder graph-n (Ln) automorphism form (1. . . ) just only on ladder graph-2 (L2) , (3) The set of automorphism function of W3 with composition function is a group.

Wheel graph and ladder graph automorphism applied to find automorphism function of wheel graph with form (1)( . . . ) and ladder graph with form (1 . . . ). The researcher suggest to other form and other graph on the next research.