Automorfisme graf bintang dan graf lintasan

Damayanti, Reni Tri (2011) Automorfisme graf bintang dan graf lintasan. Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img]
Preview
Text (Fulltext)
07610029.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview

Abstract

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 ...

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Abidin, Munirul
Keywords: Graf Bintang ...; Graf Lintasan ...; Isomorfisme Graf; Automorfisme Graf; Grup Simetri; Star Graph ...; Path Graph ...; Graph Isomorphism, Graph Automorphism, and Symmetric Group
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Ida Lestari
Date Deposited: 23 May 2017 08:26
Last Modified: 23 May 2017 08:26
URI: http://etheses.uin-malang.ac.id/id/eprint/6709

Actions (login required)

View Item View Item