Line Graph dari Graf Kincir dan Graf Kipas Nanda Saputra1, Ahmad Fauzan2, Mukhni3 Student of Mathematic Department, State University of Padang1 Lecturer of Mathematic Department, State University of Padang2,3 Jl. Prof. Dr. Hamka Kampus FMIPA UNP Air Tawar Padang, Indonesia
[email protected] [email protected] [email protected]
( ) = ( ) for every , ∈ ( ), where a adjacent (directly Abstract – Line graph is a graph with connected) to b in ( )if and only if a and b adjacent in . This study will look how the general form of line graph of the windmill graph , and the fan graph , . Based on the results of the study found that line graph of the windmill graph ( ) with = 3 and ≥ 2 is a graph that consist of 3 points , and 2 − 1 edges. Line graph of the fan graph with = 1 and ≥ 2 is a graph that consist of , 2 − 1 points and + 5 − 8/2 edges. Keywords – line graph, windmill graph, fan graph ( ) = ( ) untuk setiap , ∈ ( ), di mana a Abstrak – Line graph adalah graf dengan terhubung langsung terhadap b di ( ) jika dan hanya jika a dan b terhubung langsung di . Pada tulisan ini diperlihatkan bagaimana bentuk umum line graph dari graf kincir , dan graf kipas , . Berdasarkan hasil penelitian diperoleh bahwa line graph dari graf kincir ( = 3 dan , ) dengan ≥ 2 merupakan graf yang terdiri dari 3 titik dan 2 + sisi. Line graph dari graf kipas ( , ) dengan = 1 dan ≥ 2 merupakan graf yang terdiri dari 2 − 1 titik dan + 5 − 8/2 sisi. Kata kunci – line graph, graf kincir, graf kipas
PENDAHULUAN Salah satu topik menarik dalam teori graf adalah line graph yang secara sederhana dapat diartikan sebagai bentuk perubahan sisi (edge) menjadi titik (vertex) dari suatu graf . Dalam hal ini, jika sebarang graf ditransformasikan ke dalam bentuk line graph akan menghasilkan suatu bentuk graf baru ( ) dengan perubahan jumlah titik dan sisi dari graf . Adapun definisi dari line graph itu sendiri adalah, jika G merupakan graf, V(G) dan E(G) adalah himpunan titik dan sisi dari graf G. L(G) merupakan notasi dari line graph yang didefinisikan sebagai V(L(G)) = E(G) untuk setiap , ∈ ( ) maka a terhubung langsung (adjacent) terhadap b di L(G) jika dan hanya jika a dan b terhubung langsung terhadap sisi di G [3]. Beberapa jenis dari graf khusus sebelumnya pernah diteliti bagaimana bentuk umumline graph nya. Seperti bentuk umum line graph dari graf lintasan, graf sikel, graf bintang, graf roda, dan graf gear [1][6]. Oleh karena itu penulis tertarik mencoba meneliti bagaimana bentuk umum line graph dari jenis graf khusus lainnya, yaitu graf kincir (windmill graph) dan graf kipas (fan graph). Graf kincir dan graf kipas keduanya merupakan graf beraturan yang dibangun dari operasi dua jenis graf, yaitu
operasi gabungan dan operasi penjumlahan [4]. Dari kedua graf ini, selanjutnya akan dicari bagaimana bentuk pola jumlah titik dan sisi dari line graph-nya dimulai dari n terkecil.Sehingga nantinya dari pola tersebut akan diperoleh suatu konjektur yang selanjutnya dinyatakan dalam suatu bentuk teorema yang mana merupakan rumus umum line graph dari graf kincir dan graf kipas. METODE Dalam tulisan ini, metode yang digunakan adalah studi literatur. Studi literatur merupakan penampilan argumentasi penalaran keilmuan yang memaparkan hasil olah piker mengenai suatu permasalahan atau topic kajian kepustakaan yang berisi satu topik kajian yang di dalamnya memuat beberapa gagasan atau proposisi yang terkait dan harus didukung oleh data yang diperoleh dari berbagai sumber kepustakaan. Pada tulisan ini, penulis menekankan kajian mengenai line graph pada graf kincir dan graf kipas. Adapun literatur utama yang digunakan yaitu materi yang terkait atau berhubungan dalam buku yang ditulis oleh penulis Gary Chartrand, Ketut Budayasa, Rinaldi Munir dan didukung oleh literatur pendukung lainnya seperti tulisan dari jurnal maupun sumber yang diambil dari internet.
43
HASIL DAN PEMBAHASAN Untuk menentukan bentuk umum line graph pada graf kincir , dan graf kipas , , dilakukan beberapa tahapan pencarian. Pada tahap awal, digambarkan beberapa bentuk graf kincir , dan graf kipas terkecil. Kemudian, dengan , dimulai dari indeks memperhatikan keterhubungan sisi-sisinya, graf tersebut diubah ke dalam bentuk line graph ( ). Tahapan selanjutnya, beberapa contoh line graph dari graf kincir dan graf kipas dihitung jumlah titik dan sisi pada setiap line graph-nya. Berdasarkan jumlah titik dan sisi dari contoh setiap graf, dicari pola yang terbentuk. Pola yang diperoleh dianggap sebagai konjektur atau dugaan sementara hingga nantinya dinyatakan dalam suatu teorema untuk dibuktikan. Pembahasan dalam karya tulis ini dibagi atas dua kelompok, yaitu pertama line graph pada graf kincir dan kedua line graph pada graf kipas. A. Line Graph pada Graf Kincir , Graf kincir (windmill) dinotasikan dengan , merupakan graf sederhana tak berarah dengan ( − 1) + 1 titik dan ( − 1)/2sisi, berlaku untuk ≥ 2 dan ≥ 2. Graf ini dapat dibangun dengan menggabungkan ncopy graf komplit dengan satu titik yang sama [7]. Dalam tulisan ini, graf kincir yang dibahas dibatasi untuk indeks = 3 dan indeks ≥ 2 adalah bilangan asli. Jadi indeks nya tetap, sementara indeks nya bergerak dimulai dari nilai terkecil. Berikut ini proses yang dilakukan dalam menemukan bentuk umum line graph dari graf kincir; 1. Line graph untuk graf kincir , Sesuai dengan definisi, graf kincir , di mana = 3 dan = 2 merupakan graf sederhana tak berarah dengan banyak himpunan titik ( − 1) + 1 dan banyak himpunan sisi ( − 1)/2. Dengan demikian, graf kincir adalah graf yang memiliki 5 titik , ( , , , , ) dan memiliki 6 sisi ( , , , , , ) seperti tampak pada Gambar.1
Gambar. 1 Graf Kincir
Gambar. 2 Line Graph (
,
) dari Graf
,
Dari Gambar 2 di atas, tampak bahwa titik-titik yang saling adjacent pada line graph ( , ) adalah sebagai berikut; titik adjacent dengan titik , , dan titik adjacent dengan titik , , dan titik adjacent dengan titik dan titik adjacent dengan titik , , dan titik adjacent dengan titik , , dan titik adjacent dengan titik dan Berdasarkan beberapa tahapan di atas, diperoleh bentuk line graph dari graf kincir , seperti pada Gambar. 3 berikut ini;
Gambar. 3 Line Graph (
,
)
Dari Gambar. 3 di atas, diperoleh bahwa line graph dari graf kincir , memiliki 6 titik dan 10 sisi atau dapat ditulis = ( , ) (dibaca: ( , ) adalah , line graph dari ). , 2. Line graph untuk graf kincir , Graf kincir di mana = 3 dan =3 , merupakan graf yang dibangun dari gabungan 3 graf komplit dengan satu titik yang sama. Graf ini memiliki 7 titik dan 9 sisi yang diberi nama sisi , , , , , , , dan seperti tampak pada Gambar. 4
,
Berdasarkan Gambar. 1 di atas, dengan memperhatikan sisi-sisi yang saling terhubung langsung, setiap sisi pada graf kincir , selanjutnya diubah menjadi titik pada line graph ( , ), sehingga jika dua titik dari ( terhubung langsung maka , ) korespondensi sisi dari graf juga terhubung , langsung. Adapun sisi-sisi yang saling terhubung langsung pada graf diperlihatkan pada contoh , Gambar. 2.
Gambar. 4 Graf Kincir
,
Berdasarkan Gambar. 4 di atas, dengan memperhatikan sisi-sisi yang saling terhubung langsung, setiap sisi pada
44
graf kincir line graph ( berikut ini;
,
selanjutnya diubah menjadi titik pada , )seperti tampak pada Gambar. 5
Gambar. 5 Line Graph
,
Dari Gambar. 5 di atas, diperoleh bahwa line graph dari graf kincir , memiliki 9 titik dan 21 sisi atau dapat ditulis ( , )= ( , ) (dibaca: ( , ) adalah line graph dari , ) 3. Line graph untuk graf kincir , Graf kincir di mana = 3 dan =4 , merupakan graf yang dibangun dari gabungan 4 graf komplit dengan satu titik yang sama. Graf ini memiliki 9 titik dan 12 sisi yang diberi nama , , , , , , , , , , dan seperti tampak pada Gambar. 6 berikut ini;
Gambar. 7 Line Graph
Gambar. 8 Graf Kincir
Gambar.6 Graf Kincir
,
Berdasarkan Gambar. 6 di atas, dengan memperhatikan sisi-sisi yang saling terhubung langsung, setiap sisi pada graf kincir , selanjutnya diubah menjadi titik pada line graph ( , ) sehingga tampak seperti pada Gambar. 7. Dari Gambar. 7, diperoleh bahwa line graph dari graf kincir , memiliki 12 titik dan 36 sisi atau dapat ditulis ( , )= ( , ) (dibaca: ( , ) adalah line graph dari ) ,
,
4. Line graph untuk graf kincir , Graf kincir di mana = 3 dan =5 , merupakan graf yang dibangun dari gabungan 5 graf komplit dengan satu titik yang sama. Graf ini memiliki 11 titik dan memiliki 15 sisi yang diberi nama , , , , , , , , , , , , , dan seperti tampak pada Gambar. 7
,
Berdasarkan Gambar. 8 di atas, dengan memperhatikan sisi-sisi yang saling terhubung langsung, setiap sisi pada graf kincir , selanjutnya diubah menjadi titik pada line graph ( , )seperti tampak pada Gambar.9. Dari Gambar. 9, diperoleh bahwa line graph dari graf kincir , memiliki 15 titik dan 55 sisi atau dapat ditulis ( , )= ( , ) (dibaca: ( , )adalah line graph dari ). , 5. Line graph untuk graf kincir , Graf kincir di mana = 3 dan =6 , merupakan graf yang dibangun dari gabungan 6 graf komplit dengan satu titik yang sama. Graf ini memiliki 13 titik dan memiliki 18 sisi yang diberi nama sisi , , , , , , , , , , , , , , ,
45
,
dan
seperti tampak pada Gambar. 10
Gambar. 9 Line Graph
dari line graph ( dalam Tabel I:
). Untuk lebih jelasnya disajikan
,
,
Gambar. 11 Line Graph
,
TABEL I LINE GRAPH PADA GRAF KINCIR
No
Gambar. 10 Graf Kincir
,
Berdasarkan Gambar. 10 di atas, dengan memperhatikan sisi-sisi yang saling terhubung langsung, setiap sisi pada graf kincir , selanjutnya diubah menjadi titik pada line graph ( , ) seperti tampak pada Gambar. 11. Dari Gambar. 11, diperoleh bahwa line graph dari graf kincir , memiliki 18 titik dan 78 sisi atau dapat ditulis ( , )= ( , ) (dibaca: ( , ) adalah line graph dari ). , Berdasarkan beberapa contoh line graph dari graf kincir di atas, dapat dilihat bahwa line graph pada graf kincir dan ≥ 2di mana . dengan = 3 merupakan indeks dari graf komplit dan merupakan banyak copy-an dari graf komplit yang membangun grafkincir, membentuk suatu barisan jumlah titik dan sisi, Dari bentuk pola inilah nanti akan dicari rumus umum
Graf
Line Graph
,
1
,
2
,
,
(
,
(
,
)=
( ,
)
)=
( ,
)
3
,
(
,
)=
(
,
)
4
,
(
,
)=
(
,
)
5
,
(
,
)=
(
,
)
Berdasarkan Tabel I di atas, dengan menganalisa barisan titik dan sisi dari line graph pada graf kincir ≥ 2, maka diperoleh , dengan = 3 dan kesimpulan sementara bahwa ( , ) memiliki 3 titik dan 2 + sisi. Teorema I Suatu graf kincir = 3 dan ≥ 2 adalah , dengan bilangan asli memiliki line graph berbentuk = , di mana M adalah line graph dengan 3 titik ( , ) dan 2 + sisi [8]. Bukti: Untuk jumlah titik; Berdasarkan definisi, diketahui bahwa graf kinci ( ) sisi. Karena , merupakan graf yang memiliki titik pada line graph , dibentuk dari sisi graf kincir , yang saling adjacent, sehingga untuk nilai = 3 diperoleh,
46
( − 1) 2 . 3(3 − 1) = 2 =3
| |=
Untuk jumlah sisi; Misalkan ( ) menyatakan proposisi bahwa jumlah sisi line graph dari graf kincir + untuk , adalah 2 ≥2
Langkah 1. (2) menyatakan bahwa jumlah sisi dari line graph untuk bilangan asli pertama 2 adalah 10, maka 10 = 2(2) + 2 = 10 ∴ (2) benar bahwa jumlah sisi untuk = 2 adalah 1 Langkah 2. Asumsikan bahwa ( ) benar untuk suatu bilangan asli n. 10 + 11 + 15 + 19 + 23 + ⋯ + (4 + 7) = 2 + Akan ditunjukan bahwa untuk ( + 1) juga benar yaitu,
10 + 11 + 15 + 19 + 23+. . +(4 + 7) + (4( − 1) + 7) = 2( + 1) + ( + 1) Diperoleh: 10 + 11 + 15 + 19 + 23+. . +(4 + 7) + (4( − 1) + 7) = (2
+ ) + (4 − 4 + 7) = 2
+5 +3
= 2( + 1) + ( + 1) Karena Langkah 1 dan Langkah 2 telah dibuktikan keduanya benar, maka untuk semua bilangan asli ≥ 2 terbukti bahwa jumlah sisi dari line graph , adalah 2 + . B. Line Graph pada Graf Kipas , Graf kipas atau Fan Graph dengan notasi ( , ) didefinisikan sebagai penjumlahan dari dua graf atau + , di mana adalah graf kosong dengan m titik dan adalah graf lintasan dengan n titik [9]. Gambar. 12 berikut ini merupakan contoh dari berbagai bentuk graf kipas , berdasarkan order dari graf yang membangunnya, diantaranya adalah graf kipas , , graf kipas , , dan graf kipas , .
TABEL II LINE GRAPH PADA GRAF KIPAS
No
Graf
Dalam tulisan ini, graf kipas yang dibahas merupakan graf kipas sederhana, yaitu graf kipas denganindeks nya tetap = 1 dan indeks ≥ 2 adalah bilangan asli. Jadi indeks nya tetap, sementara indeks nya bergerak dimulai dari nilai terkecil. Dengan tahapan pencarian yang sama dalam menentukan jumlah titik dan sisi line graphpada graf kincir , . Diperoleh jumlah titik dan sisi dari line graph ( , )untuk graf kipas , di mana = 1 dan ≥ 2 adalah bilangan asli yang diberikan dalam Tabel II. Berdasarkan Tabel II di atas, dengan menganalisa barisan titik dan sisi dari line graph pada graf kipas , untuk = 1 dan ≥ 2, maka diperoleh bahwa ( , ) memiliki 2 − 1 titik dan ( + 5 − 8)sisi.
,
1
,
,
=
( , )
2
,
,
=
( , )
3
,
,
=
( ,
)
4
,
,
=
( ,
)
5
,
,
=
(
,
)
Teorema II Suatu graf kipas , dengan = 1 dan ≥ 2 di mana n adalah bilangan asli memiliki line graph berbentuk ( , )= di mana N adalah line graph (
Gambar. 12 Graf Kipas (Fan Graph)
,
Line Graph
,
)
dengan 2 − 1 titik dan + 5 − 8/2 sisi. [8] Bukti: Untuk jumlah titik; Berdasarkan definisi, graf kipas , dibangun dari penjumlahan graf + . Jumlah sisi dari graf kipas adalah , | | = + ( − 1) = 2 −1 Karena jumlah titik pada line graph ( , ) berasal dari jumlah sisi dari graf , , maka jumlah titik = , 2 −1 Untuk jumlah sisi; Misalkan ( ) menyatakan proposisi bahwa jumlah sisi line graph dari graf kipas adalah + 5 − 8/2 , untuk ≥ 2 Langkah 1. (2) menyatakan bahwa jumlah sisi line graph untuk bilangan asli pertama 2 adalah 3 maka, (2) + 5(2) − 8 (2) = 2 4+2 = =3 2 ∴ (2) benar karena jumlah sisi untuk = 2 adalah 3
47
Langkah 2. Asumsikan ( ) benar untuk suatu bilangan asli ,
Akan ditunjukan bahwa untuk ( + 1) juga benar, yaitu; 3 + 5 + 6 + 7+. . +( + 4) + ( + 3) = + 7 − 2/2
3 + 5 + 6 + 7 + 8 + 9+. . +( + 4) =
Diperoleh:
+ 5 − 8/2
3 + 5 + 6 + 7 + 8 + 9+. . +( + 4) + ( + 3) = =
+7 −2 = 2
(
,
)
+5 −8 2 +6 + 2 2
+7 −2 2
Karena Langkah 1 dan Langkah 2 telah dibuktikan keduanya benar, maka untuk semua bilangan asli ≥ 2 terbukti bahwa jumlah sisi dari line graph , adalah + 5 − 8/2. SIMPULAN Berdasarkan hasil pembuktian teorema pada pembahasan, diperoleh kesimpulan bahwa: 1. Line graph untuk graf kincir =3 , dengan dan ≥ 2 bilangan asli memiliki bentuk umum = ( , dengan 3 titik dan , ) 2 + sisi 2. Line graph untuk graf kipas , dengan = 1 dan ≥ 2 bilangan asli memiliki bentuk umum ( , )= dengan2 − 1 titik dan (
+5 −8 + ( + 3) = 2
REFERENSI Assadillah, M.H. Line Graph Dari Graf Roda Dan Graf Gear , Malang: Universitas Negeri Islam (UIN) Malang. 2009. [2] Budayasa, Ketut. Teori Graph dan Aplikasinya, Surabaya: Universitas Negeri Surabaya. 2007. [3] Chartrand, G. &Lesniak, L. Graph and Digraph 2nd Edition. California: Wadsworth, Inc. 1986. [4] Goss, Jonathan and Yellen, Jay. Graph Theory and its Application. New York: CRC Press. 1999. [5] Munir, Rinaldi. Matematika Diskrit. Bandung: Informatika. 2005. [6] Nofandika, F. F. Graf Garis (Line Graph) Dari Graf Lintasan, Graf Sikel Dan Graf Bintang, Malang: Universitas Negeri Islam (UIN) Malang. 2009 [7] Purwanto, Matematika Diskrit. Malang: IKIP Malang. 1998. [8] Saputra, Nanda. Line Graph Dari Graf Kincir Dan Graf Kipas, Padang: Universitas Negeri Padang. 2013. [9] http://en.wikipedia.org/wiki/Windmill_graph. [10] http://mathworld.wolfram.com/FanGraph.html. [1]
+ 5 − 8)/2 sisi.
48
