Graf [PDF]

Citation preview

BAB I PENDAHULUAN 1.1.



Latar Belakang Ilmu matematika merupakan salah satu ilmu pengetahuan yang banyak



memberikan alternatif maupun solusi dalam menyelesaikan permasalahan di segala bidang. Penyelesaian masalah yang sering di hadapi antara lain mencangkup antara objek-objek diskrit dan hubungan antara objek-objek tersebut. Contohnya menghubungkan sejumlah kota dengan kota lainnya dalam sebuah peta jaringan jalan raya. Permasalahan-permasalahan seperti ini dapat di modelkan secara baik dengan menggunakan konsep garf. Graf pertama kali dikenal pada saat matematikawan Swiss, bernama Leonhard Euler, berhasil mengungkap Misteri Teka-Teki Jembatan Konigsberg pada tahun 1736. Permasalahan ini iyalah membuktikan apakah dapat melakukan perjalanan berangkat dari satu daratan kembali ke daratan tersebut melewati semua jembatan yang ada. Kesimpulan itu di tuangkan dalam papernya yang berjudul : Solutio Problematis ad Geometriam Situs Pertitian (The Solution of a problem relating to the geometry of positions). Masalah jembatan Konigsberg tersebut dapat dinyatakan dalam istilah graph dengan menentukan empat daratan sebagai titik (vertex) dan ketujuh jembatan sebagai sisi (edge) yang menghubungkan pasangan titik yang sesuai (Ibrahim, dan Noor Saif Muhammad Mussafi, 2013)



Gambar 1.1.1 Teka -Teki Jembatan Konigsberg Pelabelan adalah bagian dari teori graf. pelabelan graf pertama kali di perkenalkan oleh Sedlàček pada tahun 1964. Konsep pelabelan graf sangat dikenal dalam teori graf tidak hanya karena tantangan pelabelannya tetapi juga karena



1



aplikasinya pada ilmu lain, seperti optimasi jaringan telepon, jaringan computer, jaringan listrik, model papan sirkuit, model ikatan struktur kimia, dan lain-lain. Pada suatu graf dapat dikenakan pelabelan (Murtiningrum, 2012:1). Pelabelan graf adalah pemberian nilai bilangan bulat pada titik atau sisi atau keduanya dengan memenuhi aturan-aturan tertentu (Gallian, 2014). Pelabelan titik adalah pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan domain gabungan himpunan titik dan himpunan sisi. Ada beberapa macam jenis pelabelan pada graf, salah satunya pelabelan product cordial. Secara umum pelabelan product cordial merupakan pelabelan titik biner dengan



f : V ( G )→{0,1}



¿



yang menginduksi pelabelan sisi



f ¿(uv)=f (u).f (v),∀uv∈E(G)



|vf (0)−vf (1)|≤1



dan



|e f (0)−e f (1)|≤1



sehingga



f :E(G)→{0,1}



memenuhi



syarat



, dengan v f ( 0),v f (1),e f (0),e f (1) berturut-



turut menyatakan banyaknya titik yang berlabel 0,banyaknya titik yang berlabel 1, banyaknya sisi yang berlabel 0, dan banyaknya sisi yang berlabel 1. Sebuah graf dengan pelabelan product cordial disebut juga graf product cordial. Konstruksi dari pelabelan product cordial telah dilakukan pada beberapa graf. diantaranya yaitu graf sikel, shadow graph, dan lain-lain. berdasarkan hal tersebut penulis melakukan konstruksi pelabelan product cordial pada graf



C3 3 S n dengan n bilangan asli. Graf C3 3 S n dibentuk dari graf lingkaran C3 dan 3 graf bintang



S n . Sehingga, penulis merumuskan makalah seminar dengan



judul "Konstruksi Pelabelan Product Cordial pada Graf 1.2.



C3 3 S n ".



Rumusan Masalah Berdasarakan



latar



belakang



tersebut,



maka



dapat



dirumuskan



permasalahan yaitu bagaimana mengkonstruksi pelabelan product cordial pada graf 1.3.



C3 3 S n ? Tujuan Penulisan 2



Berdasarkan rumusan masalah di atas, maka tujuan dari penulisan makalah ini adalah untuk mengetahui cara mengkonstruksi pelabelan product cordial pada graf 1.4.



C3 3 S n . Manfaat Penulisan Hasil penelitian ini diharapkan dapat memberikan manfaat sebagai berikut. 1.4.1



Manfaat Teoritis Hasil penelitian ini diharapkan dapat memberikan sumbangan yang



positif bagi pengembangan dan kemajuan ilmu pengetahuan terkait dengan pelabelan graf khususnya pelabelan product cordial, sehingga dapat diaplikasikan lebih lanjut. 1.4.2



Manfaat Praktis Memberikan informasi tentang pelabelan graf khususnya mengenai



pelabelan product cordial, dan menambah wawasan bagi pencinta matematika tentang Teori Graf. 1.5.



Batasan Masalah Dalam makalah ini hanya membahas tentang konstruksi pelabelan product



cordial pada graf



C3 3 S n



.



3



BAB II LANDASAN TEORI 2.1.



Definisi Graf Wilson (1990) menyatakan graf adalah suatu diagram yang terdiri dari titik-titik (points) yang disebut vertex (node/titik) yang dihubungkan dengan garis yang dinamakan sisi di mana setiap sisi terhubung dengan tepat 2 vertex. Secara matematis graf G dapat didefinisikan sebagai pasangan himpunan (V, E), yang mana dalam hal ini: V = himpunan tak kosong dari titik-titik (vertices atau node), seperti {v1,v2, ,..., vn} dan E = himpunan sisi (edges) yang menghubungkan sepasang titik, seperti {e1,e2,..., en}. Jadi G = (V,E). Himpunan titik (V) tidak boleh kosong, sedangkan himpunan sisi (E) boleh kosong. Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu pun, tetapi titiknya harus ada, minimal satu. Graf yang mempunyai satu titik tanpa sisi dinamakan graf trivial. Titik juga sering dinamakan noktah atau titik. Rosen Kenneth (1999) dalam mempelajari graf, terdapat beberapa istilah yang dipakai dalam mempelajari graf yaitu sebagai berikut a.



Tetangga (adjacent), bersisian (incident), dan titik ujung Dua titik u dan v dalam sebuah graf tak berarah G disebut tetangga di



dalam G jika uv merupakan sebuah sisi di G. Jika e = uv, sisi e tersebut disebut bersisian dengan titik u dan v. Jika sisi e menghubungkan titik u dan v maka titik u dan v disebut titik ujung dari sisi. b.



Derajat Derajat sebuah titik pada suatu graf tak berarah merupakan jumlah



dari sisi yang menempel terhadapnya, kecuali loop yang dihitung 2 pada titik tersebut. 2.2.



Jenis – Jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori atau jenis bergantung pada sudut pandang pengelompokkannya. Secara umum jenis-



4



jenis graf yang sering digunakan melipuiti graf pohon, graf lintasan, graf lengkap, graf bintang (star), graf lingkaran (cycle), dan lain-lain.



Gambar 2.2.1 Jenis -jenis Graf. (a) Graf Pohon, (b) Graf Lintasan (c) Graf Lengkap Berikut



Pn ,



K n , (d) Graf Bintang S n , (e) Graf Lingkaran C n



dijelaskan



beberapa



graf



yang



berkaitan



dengan



pembahasan. 1. Graf Bintang (Star) Graf bintang (Sn) adalah graf yang dibangun dari satu titik pusat dan n titik (daun) yang adjacent hanya dengan titik pusat tersebut. Graf bintang memiliki n + 1 titik dan n sisi (Amri, 2011).



5



Gambar 2.2.2. Graf Bintang (Star) S8. 3. Graf Lingkaran (Cycle) Graf lingkaran dengan panjang n adalah sebuah graf dengan lintasan tertutup



(sirkuit)



dengan



v 1 v 2 ,v 2 v3 ...,v n−1 v n ,v n v 1



n



dimana



simpul



v 1 , v 2 ,..., vn



dan



busur



(n≥3 ) . Graf lingkaran dinotasikan



dengan Cn (Amri, 2011). Gambar 2.2.3 di bawah merupakan gambar dari graf lingkaran



C3 ,C 4 ,C 5 ,C 6 ,C7



, dan C8



Gambar 2.2.3. Graf Lingkaran



C3 ,C 4 ,C 5 ,C 6 ,C7



, dan C8



4. Graf C33Sn Graf



C3 3 S n



adalah graf yang dibentuk dari graf lingkaran C3 dan 3 graf



bintang Sn dengan menambahkan sisi yang menghubungkan setiap titik di C3 dengan pusat sebuah Sn. Berikut contoh gambar graf



C3 3 S n



dengan n = 7.



6



Gambar 2.2.4 Graf 2.3.



C 3 3 S6



Fungsi Misalkan X dan Y adalah dua himpunan yang tidak kosong. Suatu cara atau aturan yang memasangkan setiap elemen dari himpunan X dengan tepat satu elemen di himpunan Y disebut pemetaan atau fungsi dari himpunan X ke himpunan Y. Fungsi dari himpunan X ke himpunan Y dinotasikan dengan f, yaitu



f : X →Y . Himpunan X disebut daerah asal (domain) dan himpunan Y disebut



daerah kawan (codomain), sedangkan f(x) disebut bayangan (image) dari x oleh f, dan semua himpunan image disebut daerah hasil (range). Suatu fungsi f dikatakan fungsi satu-satu (one to one) atau injektif jika tidak ada dua elemen berbeda di X yang dipetakan ke satu elemen yang sama di



Y.



Dengan



kata



lain,



jika



x1 , x2 ∈ X



f ( x 1 )≠ f ( x 2 ) . Hal ini ekuivalen dengan jika



x 1=x 2



dengan



x 1≠x 2 maka



f ( x 1 )= f ( x 2 )



maka



(Ariawan, 1996).



Fungsi f dikatakan fungsi pada (onto) atau surjektif jika range dari f adalah semua elemen dari himpunan Y. Dengan kata lain sedemikian sehingga



∀ y ∈Y , ∃x ∈ X



y=f ( x ) (Ariawan, 1996).



7



Apabila fungsi f memenuhi fungsi injektif dan surjektif maka f dinamakan fungsi bijektif (Ariawan, 1996).



a). Fungsi Injektif



b). Fungsi Surjektif



c). Fungsi Bijektif



Gambar 2.3.1 Macam-macam Fungsi 2.4.



Pelabelan Graf Pelabelan graf adalah pemberian label bilangan bulat tak negatif pada titik atau sisi atau keduanya dengan memenuhi aturan-aturan tertentu (Gallian, 2010). Banyak jenis pelabelan yang telah dikenalkan diantaranya pelabelan harmonis, pelabelan ajaib, pelabelan product cordial dan sebagainya. Pada makalah ini akan dibahas tentang pelabelan product cordial. 2.4.1.



Pelabelan Product Cordial Sebuah pelabelan product cordial dari sebuah graf G dengan



himpunan verteks V adalah sebuah fungsi f dari V ke {0,1} sehingga jika sisi



uv



diberi label



f (u )f ( v ) , banyak simpul dilabeli dengan 0 dan



banyak simpul dilabeli dengan 1 berbeda paling banyak 1, dan banyak sisi yang dilabeli dengan 0 dan banyak sisi yang dilabeli dengan 1 berbeda paling banyak 1 (Gallian, 2014). Misalkan graf pelabelan titik biner



f ¿ : E (G)→{0,1} memenuhi syarat



G=(V , E ) , pelabelan product cordial adalah



f : V ( G )→{0,1}



dengan



yang menginduksi pelabelan sisi



¿



f (uv)=f (u).f (v),∀uv∈ E(G)



|v f (0)−v f (1)|≤1



dan



sehingga



|e f (0)−e f (1)|≤1 , dengan



8



v f ( 0),v f (1),e f (0),e f (1)



berturut-turut menyatakan banyaknya titik yang



berlabel 0,banyaknya titik yang berlabel 1, banyaknya sisi yang berlabel 0, dan banyaknya sisi yang berlabel 1 (Vaidya, 2010). Sebagai contoh adalah graf lingkaran C3. Pada gambar 2.4.1.1 dibawah diberikan contoh pelabelan product cordial pada graf lingkaran C3.



Gambar 2.4.1.1 Pelabelan Product Cordial Pada C3 Pelabelan product cordial tidak mungkin dikonstruksikan pada graf lingkaran



C4



hal



|v f (0)−v f (1)|≤1



dan



ini



dikarenakan



|e f (0)−e f (1)|≤1



tidak



memenuhi



syarat



. Suatu graf yang memiliki



pelabelan product cordial disebut graf product cordial (Vaidya, 2010). Contohnya graf pada gambar 2.4.1.2 di bawah ini.



Gambar 2.4.1.2 Pelabelan Product Cordial Pada C4



9



Graf pada gambar diatas memiliki V = 4 dan E = 4. Graf di atas, tidak dapat di konstruksikan dengan pelabelan product cordial di karenakan tidak memenuhi



|e f (0)−e f (1)|≤1



.



10



BAB III PEMBAHASAN 3.1



Pelabelan Product Cordial pada Graf C33Sn Graf



C3 3 S n



adalah graf yang dibentuk dari graf lingkaran C3 dan 3 graf



bintang Sn dengan menambahkan sisi yang menghubungkan setiap titik di C3 dengan pusat sebuah Sn. Berikut diberikan beberapa konstruksi pelabelan product



C3 3 S n



cordial pada graf 3.1.1



Graf



.



C3 3 S n



dengan n = 1



Diberikan penotasian pada graf



C3 3 S1



seperti Gambar 3.1.1 di



bawah ini.



Gambar 3.1.1 Penotasian Titik Graf Graf



C3 3 S1



C3 3 S1



memiliki titik sebanyak |V| = 9 dan sisi sebanyak |



E| = 9. Diberikan label pada titik-titiknya sebagai berikut.



11



f ( v 1 )=1



f ( v 2 )=1



f (v 3 )=1 f (v 1,0 )=1 f (v 2,0 )=1



f (v 3,0 )=0 f (v 1,1 )=0 f (v 2.1 )=0 f (v 3,1 )=0



Gambar 3.1.2 Pelabelan Product Cordial Graf C33S1 Sebagai akibatnya, setiap sisi diberikan label dengan pelabelan sisi f * yang dinyatakan sebagai berikut. ¿



f (v 1 v 2 )=f ( v 1 )⋅f ( v 2 )=1⋅1=1 ¿



f (v 1 v 3 )=f (v 1 )⋅f ( v 3 )=1⋅1=1 f ¿ (v 2 v 3 )=f (v 1 )⋅f (v 2 )=1⋅1=1 f ¿ (v 1 v 1,0 )=f (v 1 )⋅f ( v 1.0 )=1⋅1=1 f ¿ (v 2 v 2,0 )=f (v 2 )⋅f (v 2.0 )=1⋅1=1 f ¿ (v 3 v 3,0 )=f (v 3 )⋅f (v 3,0 )=1⋅0=0 f ¿ (v 1,0 v 1,1 )=f ( v 1,0 )⋅f ( v 1,1 )=1⋅0=0 f ¿ (v 2,0 v 2,1 )=f (v 2,0 )⋅f (v 2,1 )=1⋅0=0 12



f ¿ (v 3,0 v 3,1 )=f ( v 3,0 )⋅f ( v 3,1 )=0⋅0=0 Dari uraian di atas pelabelan f untuk setiap titiknya memiliki himpunan bilangan {0,1}. Dari banyaknya titik yang berlabelkan 0 maupun 1 telah memenuhi syarat



|v f (0)−v f (1)|≤1



. Kemudian



pelabelan f* yang diinduksi dari pelabelan titik f, memiliki himpunan bilangan {0,1}. Dari banyaknya sisi yang berlabelkan 0 maupun 1 telah memenuhi syarat



|e f (0)−e f (1)|≤1



. Dengan demikian, dapat



disimpulkan bahwa graf C33S1 memiliki pelabelan product cordial. 3.1.2



Graf



C3 3 S n



dengan n = 2



Diberikan penotasian pada graf



C 3 3 S2



seperti Gambar 3.1.3 di



bawah.



Gambar 3.1.3 Penotasian Titik Graf Graf



C 3 3 S2



C 3 3 S2



memiliki titik sebanyak |V| = 12 dan sisi



sebanyak |E| = 12. Diberikan label pada titik-titiknya sehingga berikut. f ( v 1 )=1



f (v 3 )=1



f ( v 2 )=1



13



f (v 1,0 )=1



f (v 2.1 )=0



f (v 2,0 )=1



f (v 2,2 )=0



f (v 3,0 )=1



f (v 3,1 )=0



f (v 1,1 )=0



f (v 3,2 )=0



f (v 1,2 )=0



Gambar 3.1.4 Pelabelan Product Cordial Graf C33S2 Dari uraian di atas pelabelan f untuk setiap titiknya memiliki himpunan bilangan {0,1}. Dari banyaknya titik yang berlabelkan 0 maupun 1 telah memenuhi syarat



|v f (0)−v f (1)|≤1



. Kemudian



pelabelan f* yang diinduksi dari pelabelan titik f, memiliki himpunan bilangan {0,1}. Dari gambar 3.1.4 dapat dilihat bahwa banyaknya sisi yang berlabelkan 0 maupun 1 telah memenuhi syarat



|e f (0)−e f (1)|≤1



. Dengan demikian, dapat disimpulkan bahwa graf



C33S2 memiliki pelabelan product cordial. 3.1.3



Graf



C3 3 S n



dengan n = 6



14



Diberikan penotasian pada graf



C 3 3 S6



seperti Gambar 3.1.5 di



bawah.



Gambar 3.1.5 Penotasian Titik Graf Graf



C 3 3 S6



C3 3 S6 memiliki titik sebanyak |V| = 24 dan sisi sebanyak



|E| = 24. Diberikan label pada titik-titiknya sehingga berikut. f ( v 1 )=1



f ( v 2 )=1



f (v 3 )=1 f (v 1,0 )=1 f (v 2,0 )=1 f (v 3,0 )=1 f (v 1,1 )=1 f (v 1,2 )=1 f (v 1,3 )=1



f (v 1,4 )=1 f (v 1,5 )=1 f (v 1,6 )=1 f (v 2.1 )=0 f (v 2,2 )=0 f (v 2,3 )=0 f (v 2,4 )=0 f (v 2,5 )=0 f (v 2,6 )=0 15



f (v 3,1 )=0



f (v 3,4 )=0



f (v 3,2 )=0



f (v 3,5 )=0



f (v 3,3 )=0



f (v 3,6 )=0



Gambar 3.1.6 Pelabelan Product Cordial Graf C33S6 Dari uraian di atas pelabelan f untuk setiap titiknya memiliki himpunan bilangan {0,1}. Dari banyaknya titik yang berlabelkan 0 maupun 1 telah memenuhi syarat



|v f (0)−v f (1)|≤1



. Kemudian



pelabelan f* yang diinduksi dari pelabelan titik f, memiliki himpunan bilangan {0,1}. Dari gambar 3.1.6 dapat dilihat bahwa banyaknya sisi yang berlabelkan 0 maupun 1 telah memenuhi syarat



|e f (0)−e f (1)|≤1



. Dengan demikian, dapat disimpulkan bahwa graf



C33S6 memiliki pelabelan product cordial. 3.1.4



Graf



C3 3 S n



dengan n = 10



Diberikan penotasian pada graf



C3 3 S10



seperti Gambar 3.1.7 di



bawah.



16



Gambar 3.1.5 Penotasian Titik Graf Graf



C3 3 S10



C3 3 S10



memiliki titik sebanyak |V| = 36 dan sisi



sebanyak |E| = 36. Diberikan label pada titik-titiknya sehingga berikut. f ( v 1 )=1 f ( v 2 )=1



f (v 3 )=1 f (v 1,0 )=1 f (v 2,0 )=1 f (v 3,0 )=1 f (v 1,1 )=1 f (v 1,2 )=1 f (v 1,3 )=1 f (v 1,4 )=1 f (v 1,5 )=1



f (v 1,6 )=1 f (v 1,7 )=1 f (v 1,8 )=1 f (v 1,9 )=1 f (v 1,10 )=1 f (v 2.1 )=1 f (v 2,2 )=1 f (v 2,3 )=0 f (v 2,4 )=0 f (v 2,5 )=0 f (v 2,6 )=0 17



f (v 2,7 )=0



f (v 3,4 )=0



f (v 2,8 )=0



f (v 3,5 )=0



f (v 2,9 )=0



f (v 3,6 )=0



f (v 2 ,10 )=0



f (v 3,7 )=0



f (v 3,1 )=0



f (v 3,8 )=0



f (v 3,2 )=0



f (v 3,9 )=0



f (v 3,3 )=0



f (v 3 ,10 )=0



Gambar 3.1.8 Pelabelan Product Cordial Graf C33S10 Dari uraian di atas pelabelan f untuk setiap titiknya memiliki himpunan bilangan {0,1}. Dari banyaknya titik yang berlabelkan 0 maupun 1 telah memenuhi syarat



|v f (0)−v f (1)|≤1



. Kemudian



pelabelan f* yang diinduksi dari pelabelan titik f, memiliki himpunan bilangan {0,1}. Dari gambar 3.1.8 dapat dilihat bahwa banyaknya sisi yang berlabelkan 0 maupun 1 telah memenuhi syarat



18



|e f (0)−e f (1)|≤1



. Dengan demikian, dapat disimpulkan bahwa graf



C33S10 memiliki pelabelan product cordial. Teorema 3.1 Graf C33Sn memiliki pelabelan product cordial Bukti. Misalkan notasi titik graf C33Sn diberikan pada Gambar 2.1.9 di bawah ini.



Gambar 3.1.9 Penotasian Titik Graf C33Sn Pada gambar 3.1.9 di atas terlihat bahwa himpunan titik graf C33Sn adalah



{ v 1 ,.v 2 ,v 3, v 1,0 , v1,1 ,...,v 1 ,n ,v 2,0 , v 2,1 ,..., v 2,n ,v 3,0 ,v 3,1 ,..., v3 ,n }



dan himpunan sisinya adalah



{ v 1 v 2 ,v2 v 3 ,v 3 v1 ,v 1 v1,0 ,v 2 v 2,0 , v3 v3,0 , v1,0 v1,1 ,...,v 1,0 v 1 ,n ,v 2,0 v 2,1 ,..., v 2,0 v2 ,n ,v 3,0 v3,1 ,...,v 3,0 v 3 ,n } maka



|V|=3n+6



dan



|E|=3n+6



.



Pembuktian C33Sn memiliki pelabelan product cordial : 



Untuk n=1 dan n=2 menggunakan pelabelan pada sub bab (3.1.1) dan (3.1.2) 19







Untuk n=3 dan n=4 Pelabelan titik :



f (v i )=1



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤n−1



f (v 1,n )=0 f (v i, j )=0



; i=2,3



; 1≤ j≤n



Penjelasan : Untuk menjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|v f (0)−v f (1)|≤1 Dari pelabelan diperoleh :



v f (1)=3+3+n−1=n+5 v f ( 0)=2n+1 Sehingga,



|v f (0)−v f (1)|



=|(2n+1)−(n+5)| =|n−4|



Untuk n=3 maka



|3−4|≤1 1≤1 (Benar) Untuk n=4 maka



|4−4|≤1 0≤1 (Benar). Pelabelan sisi yang diinduksi dari pelabelan titik :



f ¿ (v 1 v 2 )=1 f ¿ (v 2 v 3 )=1 20



f ¿ (v 3 v 1 )=1 f ¿ (v 1 v 1,0 )=1 f ¿ (v 2 v 2,0 )=1 f ¿ (v 3 v 3,0 )=1 f ¿ (v 1,0 ,v 1, j )=1



; 1≤ j≤n−1



¿



f (v 1,0 ,v 1,n )=0 f ¿ (v i ,0 v i, j )=0



; i=2,3



; 1≤ j≤n



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|e f (0)−e f (1)|≤1 Dari pelabelan diperoleh :



e f (1)=3+3+n−1=n+5 e f (0)=2n+1 Sehingga,



=|(2n+1)−(n+5)| =|n−4|



|e f (0)−e f (1)|



Untuk n=3 maka



|3−4|≤1 1≤1 (Benar) Untuk n=4 maka



|4−4|≤1 0≤1 (Benar). Jadi, karena pelabelan titik dan pelabelan sisi sudah memenuhi syarat, maka untuk



n=3



dan



n=4



dapat dikonstruksikan dengan product



cordial labelling. 



Untuk n=5



dan n=6 21



Pelabelan titik :



f (v i )=1



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤n



f (v i, j )=0



; i=2,3



; 1≤ j≤n



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|v f (0)−v f (1)|≤1 Dari pelabelan diperoleh :



v f (1)=3+3+n=n+6 v f ( 0)=2n Sehingga,



|v f (0)−v f (1)|



=|2n−(n+6)| =|n−6|



Untuk n=5 maka



|5−6|≤1 1≤1 (Benar) Untuk n=6 maka



|6−6|≤1 0≤1 (Benar). Pelabelan sisi yang diinduksi dari pelabelan titik :



f ¿ (v 1 v 2 )=1 f ¿ (v 2 v 3 )=1 ¿



f (v 3 v 1 )=1 ¿



f (v 1 v 1,0 )=1



22



f ¿ (v 2 v 2,0 )=1 f ¿ (v 3 v 3,0 )=1 f ¿ (v 1,0 ,v 1, j )=1 f ¿ (v i ,0 v i, j )=0



; 1≤ j≤n ; i=2,3



; 1≤ j≤n



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|e f (0)−e f (1)|≤1 Dari pelabelan diperoleh:



e f (1)=3+3+n=n+6 e f (0)=2n Sehingga,



|e f (0)−e f (1)|



=|2n−(n+6)| =|n−6|



Untuk n=5 maka



|5−6|≤1 1≤1 (Benar) Untuk n=6 maka



|6−6|≤1 0≤1 Benar. Jadi, karena pelabelan titik dan pelabelan sisi sudah memenuhi syarat,



n=5



maka untuk



dan



n=6



dapat dikonstruksikan dengan product



cordial labelling. 



Untuk n≥7 Pelabelan titik :



f (v i )=1 f (v i,0 )=1



; i=1,2,3 ; i=1,2,3 23



f (v 1, j )=1



; 1≤ j≤n



f (v 2 , j )=1



; 1≤ j≤k



f (v 2 , j )=0



; k +1≤ j≤n



f (v 3 , j )=0



; 1≤ j≤n



;



n k=⌈ ⌉−3 2



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|v f (0)−v f (1)|≤1 Dari pelabelan diperoleh :



n v f (1 )=6+n+⌈ ⌉−3 2



n =3+n+⌈ ⌉ 2



n v f ( 0)= (3 n+6 )− 3+n+⌈ ⌉ 2



(



n =3+2 n−⌈ ⌉ 2



)



Sehingga,



|v f (0)−v f (1)| Untuk



n



|2 p−2⌈



n n =| 3+2n−⌈ ⌉ − 3+n+⌈ ⌉ | 2 2



(



genap n=2 p



)(



)



n =|n−2⌈ ⌉| 2



maka



2p ⌉|≤1 2



|2 p−2 p|≤1 0≤1 (Benar) Untuk n ganjil n=2 p+1 maka



|( 2 p+1 )−2⌈



2 p+1 ⌉|≤1 2



|2 p+1−2 ( p+1 )|≤1



|1−2|≤1 1≤1 (Benar). 24



Pelabelan sisi yang diinduksi dari pelabelan titik:



f ¿ (v 1 v 2 )=1 f ¿ (v 2 v 3 )=1 f ¿ (v 3 v 1 )=1 f ¿ (v 1 v 1,0 )=1 f ¿ (v 2 v 2,0 )=1 f ¿ (v 3 v 3,0 )=1 ¿



f (v 1,0 ,v 1, j )=1 ¿



f (v 2,0 v 2, j )=1



; 1≤ j≤n ; 1≤ j≤k



n k=⌈ ⌉−3 2



;



f ¿ (v 2,0 v 2, j )=0



; k +1≤ j≤n



f ¿ (v 3,0 v 3, j )=0



; 1≤ j≤n



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|e f (0)−e f (1)|≤1 Dari pelabelan diperoleh :



n e f (1)=6+n+⌈ ⌉−3 2



n =3+n+⌈ ⌉ 2 n =3+2 n−⌈ ⌉ 2



n e f (0 )=( 3 n+6 )− 3+ n+⌈ ⌉ 2



(



)



Sehingga,



|e f (0)−e f (1)| Untuk



n



|2 p−2⌈



n n =| 3+2n−⌈ ⌉ − 3+n+⌈ ⌉ | 2 2



(



genap n=2 p



)(



)



n =|n−2⌈ ⌉| 2



maka



2p ⌉|≤1 2 25



|2 p−2 p|≤1 0≤1 (Benar) Untuk n ganjil n=2 p+1 maka



|( 2 p+1 )−2⌈



2 p+1 ⌉|≤1 2



|2 p+1−2 ( p+1 )|≤1



|1−2|≤1 1≤1 (Benar). Jadi,, karena pelabelan titik dan pelabelan sisi sudah memenuhi syarat,



n≥7



maka untuk



dapat dikonstruksikan dengan product cordial



labelling. Berikut akan disajikan contoh pembahasan pada graf



C3 3 S n



untuk n = 15. Diberikan penotasian pada graf



C3 3 S15



seperti Gambar 3.1.10



di bawah.



Gambar 3.1.10 Penotasian Titik Graf



C3 3 S15



26



C3 3 S15



Graf



memiliki titik sebanyak



|V| = 51 dan sisi



sebanyak |E| = 51. Diberikan label pada titik-titiknya sehingga berikut.



f (v i )=1



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤15



k=⌈



f (v 2 , j )=1



; 1≤ j≤k



f (v 2 , j )=0



; k +1≤ j≤15



f (v 3 , j )=0



; 1≤ j≤15



;



15 ⌉−3=5 2



Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat berikut.



|v f (0)−v f (1)|≤1 Dari pelabelan diperoleh:



v f (1 )=3+15+⌈



15 ⌉ 2



=26



(3+15+⌈ 152 ⌉)



v f (0)= (3 . 15+6 ) −



=25



Sehingga,



|v f (0)−v f (1)|



=|25−26|



=|−1|



=1



1≤1 (Benar).



27



Gambar 3.1.11 Pelabelan Product Cordial Graf



C3 3 S15



Diberikan label pada sisi-sisinya sehingga sebagai berikut. ¿



f (v 1 v 2 )=1 f ¿ (v 2 v 3 )=1 f ¿ (v 3 v 1 )=1 ¿



f (v 1 v 1,0 )=1 ¿



f (v 2 v 2,0 )=1 f ¿ (v 3 v 3,0 )=1 f ¿ (v 1,0 ,v 1, j )=1 ¿



f (v 2,0 v 2, j )=1



; 1≤ j≤15 ; 1≤ j≤k



k=⌈ ;



f ¿ (v 2,0 v 2, j )=0



; k +1≤ j≤15



f ¿ (v 3,0 v 3, j )=0



; 1≤ j≤15



15 ⌉−3=5 2



Penjelasan : Untuk menunjukkan bahwa pelabelan tersebut merupakan pelabelan product cordial maka haruslah memenuhi syarat beikut. 28



|e f (0)−e f (1)|≤1 Dari pelabelan diperoleh :



e f (1)=3+15+⌈



15 ⌉ 2



=26



(3+15+⌈ 152 ⌉)



e (0)=( 3 .15+6 )− f



=25



Sehingga,



|e f (0)−e f (1)|



=|25−26|



=|−1|



=1



1≤1 Benar. Jadi, karena pelabelan titik dan pelabelan sisi sudah memenuhi syarat, maka untuk



n=15



dapat dikonstruksikan dengan product cordial



labelling.



29



BAB IV PENUTUP 4.1



Simpulan Berdasarkan pembahasan, maka dapat di simpulkan bahwa graf



C3 3 S n adalah graf product cordial. Pelabelan product cordial



untuk titik-titik pada graf 



Untuk



C3 3 S n di definisikan sebagai berikut.



n=1 dan n=2 merupakan kasus khusus, jadi untuk



pelabelannya dapat di lihat pada sub bab (3.1.1) dan (3.1.2). 



Untuk n=3 dan n=4



f (v i )=1



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤n−1



f (v 1,n )=0 f (v i, j )=0 



Untuk n=5



f (v i )=1



; 1≤ j≤n



dan n=6



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤n



f (v i, j )=0 



; i=2,3



; i=2,3



; 1≤ j≤n



Untuk n≥7



f (v i )=1



; i=1,2,3



f (v i,0 )=1



; i=1,2,3



f (v 1, j )=1



; 1≤ j≤n



30



4.2



f (v 2 , j )=1



; 1≤ j≤k



f (v 2 , j )=0



; k +1≤ j≤n



f (v 3 , j )=0



; 1≤ j≤n



;



n k=⌈ ⌉−3 2



Saran Pembahasan pelabelan product cordial ini masih terbuka bagi peneliti lain untuk melanjutkan penelitian ini pada konstruksi pelabelan produc cordial terhadap graf



C m mSn untuk m > 3.



31