Kontraksi pada graf tangga L_n dan graf kincir K_1 + mK_2

INDONESIA:

Misal graf G_1 dengan himpunan titik V (G_1) dan graf G_2 dengan himpunan titik V (G_2 ). Suatu graf G_2 didefinisikan sebagai suatu kontraksi dari graf G_1 jika terdapat pemetaan korespondensi satu-satu dan onto antara suatu unsur dari partisi di V (G_1) pada suatu unsur di V (G_2). Langkah-langkah yang dilakukan dalam membahas penelitian ini adalah sebagai berikut: (a) Menggambar graf tangga dimulai dari L_1 sampai dengan L_5, (b) Menentukan semua kemungkinan kontraksi titik dan kontraksi sisi yang dapat dikenakan pada graf tangga dimulai dari L_1 sampai dengan L_5, (c) Mencari pola yang terbentuk dari kontraksi graf tangga dimulai dari L_1 sampai dengan L_5, (d) Merumuskan pola ke dalam teorema dan membuktikan teorema, (e) Menggambar graf kincir dimulai dari K_1 + 1 K_2 sampai dengan K_1 + 5 K_2, (f) Menentukan semua kemungkinan kontraksi titik dan kontraksi sisi yang dapat dikenakan pada graf kincir dimulai dari K_ 1 + 1K_2 sampai dengan K_1 + 5 K_2 , (g) Mencari pola yang terbentuk dari kontraksi graf kincir dimulai dari K_1 + 1 K_2 sampai dengan K_ 1 + 5 K_2, (h) Merumuskan pola ke dalam teorema dan membuktikan teorema.

Berdasarkan hasil pembahasan dapat diperoleh bahwa:
1. Suatu graf tangga L_n (dengan n ∈ N) jika dikenai kontraksi titik sebanyak 2n dan kontraksi sisi sebanyak 2(n-1), maka hasil kontraksinya adalah graf lintasan P_n .
2. Suatu graf kincir K_1+ mK _2 (dengan m ∈ N) jika dikenai kontraksi titik sebanyak 2m dan kontraksi sisi sebanyak 2m , maka hasil kontraksinya adalah graf bintang K_1,m.

Pada skripsi ini, penulis hanya memfokuskan pokok bahasan pada masalah menentukan kontraksi pada graf tangga L_n (dengan n ∈ N) dan graf kincir K_1+ mK_2 (dengan m ∈ N). Oleh karena itu, penulis memberikan saran kepada pembaca yang tertarik pada permasalahan ini untuk mengembangkannya dan merumuskan teorema dari kontraksi pada graf lain.

ENGLISH:

For example graph G_1 with the set point V (G_1) and graph G_2 with the set point V (G_2). A graph G_2 defined as a contraction of the graph G_1 if there is one-to-one mapping between an element of the partition in V (G_1) on an element V (G_2). The steps are performed in this study are discussed as follows: (a) Draw a ladder graph starting from L_1 up to L_2, (b) Determine all possible ways of contracting every the ladders graph starting from L_1 up to L_2, (c) Finding patterns formed from the contraction the ladder graph starting from L_1 up to L_2 , (d) Formulate a pattern into the theorem and prove the theorem, (e) Draw a wheel graph starting from K_1 + 1 K_2 up to K_1 + 5 K_2 , (f) Determine all the possible ways of contracting every the wheel graph starting from K_1 + 1 K_2 up to K_1 + 5 K_2, (g) Finding patterns formed from contraction the wheel graph starting from K_1 + 1 K_2 up to K_1 + 5 K_2, (h) Formulate a pattern into the theorem and prove the theorem.

Based on the result of the discussion can be obtained that:
1. A ladder graph Ln (with n ∈ N) When subjected to contraction as 2n points and the contraction of as 2( n-1) edges, then the result is a graph contraction is path P_n.
2. A wheel graph K_1+ mK _2( with m ∈ N) When subjected to contraction as 2m points and the contraction of as 2m edges, then the result is a graph contraction is star graph K_1,m.

In this paper, the authors focus only on the subject matter of deciding on the graph contraction ladder graph Ln (with n ∈ N) and wheel graph K_1+ mK _2 with m ∈ N). Therefore, the author gives advice to readers who are interested in these issues to develop and formulate a theorem of contraction in the other graph.