MATHunesa (Volume 3 No 3)
2014
PELABELAN CORDIAL DAN E-CORDIAL PADA GRAF KOMPLIT, GRAF SIKEL, GRAF BINTANG, DAN GRAF RODA Titik Widyawati Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Surabaya, e-mail :
[email protected]
Budi Rahadjeng, M.Si. Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Surabaya, e-mail :
[email protected] Abstrak Pelabelangraf merupakan pemberian label pada elemen-elemen graf seperti titik, sisi, titik dan sisi. Sebuah pelabelan disebut pelabelan cordial jika ada pemetaan biner π: π β {0,1} yang menginduksi pelabelan pada sisi π = π’π£ yang dinyatakan dengan π β : πΈ πΊ β {0,1} dandidefinisikan dengan π β π = π’π£=ππ’βππ£,sehingga memenuhi |π£π0βπ£π1|β€1 dan |ππ0βππ1|β€1. Suatu graf disebut graf cordial jika memenuhi pelabelan cordial. Suatu pelabelan disebut pelabelan e-cordial jika ada pemetaan biner π: πΈ β {0,1} yang menginduksi pelabelan titik yang didefinisikan dengan π(π£) = π’π£ βπΈ π(π’π£)(πππ2), sehingga memenuhi |π£π 0 β π£π 1 | β€ 1 dan |ππ 0 β ππ 1 | β€ 1 . Syarat cukup sebuah graf untuk memenuhi sebuah pelabelan e-cordial adalah π β’ 2(πππ4). Sebuah graf disebut graf e-cordial jika memenuhi pelabelan e-cordial. Pada skripsi ini dibahas pelabelan cordial dan e-cordial pada beberapa jenis graf sederhana, yaitu graf komplit, graf sikel, graf bintang, dan graf roda. Kata kunci : pelabelan pada graf, pelabelan cordial, graf cordial, pelabelan e-cordial, graf e-cordial, graf komplit, graf sikel, graf bintang, graf roda.
Abstract Graph labelling is give a label to elements of graph that like vertex, edge, both are vertex and edge. A labelling is called cordial labelling if there exist a binary mapping π: π β {0,1}, for an edge e=uv, the induced edge labelling π β : πΈ πΊ β {0,1} is given by π β π = π’π£ = |π π’ β π π£ |, such that following |π£π 0 β π£π 1 | β€ 1 and |ππ 0 β ππ 1 | β€ 1. The graph is called cordial if it admits a cordial labelling. A labeling is called e-cordial labelling if there exist binary mapping π: πΈ β 0,1 and induced vertex labeling is given as π(π£) = π’π£ βπΈ π(π’π£)(πππ2), such that following |ππ 0 β ππ 1 | β€ 1 and |π£π 0 β π£π 1 | β€ 1. Necessary condition for a graph to admit an e-cordial labeling is that π β’ 2(πππ4). The graph is called e-cordial if it admits an e-cordial labelling. The graph which will discussed are complete graph, cycle graph, star graph, and wheels graph. Keyword :graph labelling, cordial labelling, cordial graph, e-cordial labelling, e-cordial graph, complete graph, cycle graph, star graph, wheel graph.
teka-teki (puzzle), namun akhirnya mengalami perkembangan yang sangat pesat. Misalnya digunakan dalam pencarian lintasan terpendek, permasalahan tukang pos, transportasi, jaringan komunikasi, jaringan radio dan sebagainya. Salah satu topik dalam teori graf adalah pelabelan. Pelabelan pada suatu graf adalah suatu pemetaan (fungsi) yang memasangkan unsur-unsur graf (titik atau sisi) dengan bilangan (biasanya bilangan bulat) yang disebut label. Pelabelan pertama kali diperkenalkan oleh SadlΓ Δk (1964), Stewart (1966), kemudian Kotzig dan Rosa (1970).Ada banyak pelabelan yang telah dikembangkan, diantaranya adalah pelabelan cordial dan e-cordial.Pelabelan cordial adalah pelabelan titik, sedangkan pelabelan e-cordial adalah pelabelan sisi. Pada
PENDAHULUAN Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736 ketika mencoba membuktikan kemungkinan untuk melewati empat daerah yang terhubung dengan tujuh jembatan di atas sungai Pregel di Konigsberg, Rusia dalam sekali waktu.Pembuktian Euler tersebut ditulis dalam karya tulisnya yang berjudul Solutio Problematis ad Geometriam Situs Pertinensi. Masalah jembatan Konigsberg tersebut dapat dinyatakan dalam istilah graf dengan menentukan keempat daerah itu sebagai titik (vertex) dan ketujuh jembatan sebagai sisi (edge) yang menghubungkan pasangan titik yang sesuai. Pada awalnya teori graf hanya digunakan untuk memecahkan 52
MATHunesa (Volume 3 No 3) tahun 1987, I. Cahit menulis jurnal yang berjudul βCordial Graphs: A weaker version of graceful and harmonious graphsβ. Jurnal tersebut menjelaskan tentang pelabelan cordial pada beberapa jenis kelas graf, misalnya graf komplit dan graf sikel.Pada tahun 1997, I. Cahit dan R. Yilman mengembangkan pelabelan cordial menjadi pelabelan e-cordial. Mereka menulis jurnal yang berjudul βE-Cordial Graphsβ.Graf yang dibahas dalam jurnal ini adalah beberapa jenis graf sederhana. Oleh karena itu, dalam penelitian ini penulis akan mengkaji lebih lanjut tentang sifat-sifat pelabelan cordial dan e-cordial pada beberapa jenis graf sederhana, yakni graf komplit, graf sikel, graf bintang, dan graf roda berdasarkan teorema-teorema yang ada.
2014
himpunan titik dan sisi maka pelabelan disebut pelabelan total (total labeling). Definisi4 Sebuah pemetaan π: π πΊ β {0,1} dari graf πΊ disebut pemetaan titik biner dari πΊ . Fungsi pemetaan tersebut menginduksi pelabelan pada sisi π = π’π£ yang dinyatakan dengan π β : πΈ πΊ β {0,1} dan memenuhi rumus pelabelan sisi π β π = π’π£ = |π π’ β π π£ |. Banyaknya titik pada G yang berlabel 0 dan 1 dinotasikan berturut-turut dengan π£π 0 dan π£π (1) . Banyaknya sisi pada G yang berlabel 0 dan 1 dinotasikan berturut-turut dengan ππ 0 dan ππ (1). 1
METODE PENULISAN Metode yang digunakan dalam menyusun makalah ini adalah metode kajian pustaka dengan cara memahami, mendalami dan mengidentifikasi pengetahuan yang ada dalam kepustakaan (referensi, jurnal, atau hasil penelitian lain untuk menunjang penelitian). Adapun jurnal utama yang digunakan adalah Cordial Graphs: A weaker version of graceful and harmonious graphs(I. Cahit, 1987) dan ECordial Graphs (I. Cahit dan R. Yilman, 1997).
0
0
1
0
1
0 0
0
0
Definisi 5 Pelabelan titik biner pada graf G disebut pelabelan cordial jika memenuhi π£π 0 β π£π (1) β€ 1dan ππ 0 β ππ (1) β€ 1. Graf G disebut graf cordial jika memenuhi pelabelan cordial.
KAJIAN PUSTAKA Definisi 1 Sebuah graf G didefinisikan sebagai pasangan terurut dua himpunan, yaitu himpunan hingga tak kosong V(G) yang elemen-elemennya disebut titik dan himpunan berhingga (mungkin kosong) E(G) yang elemenelemennya disebut sisisedemikian hingga setiap sisi elemen π dalam E(G) merupakan pasangan tak berurutan dari titik-titik di π(πΊ). V(G) disebut himpunan titik dari graf G dan E(G) disebut himpunan sisi dari graf G. Jika G tidak memiliki sisi, maka G disebut graf kosong.
0
1
0
1
1
1
1 0
0
0
Teorema 1 Jika G adalah graf euler dengan π sisi, dimana π β‘ 2(mod4) maka G tidak mempunyai pelabelan cordial. Bukti : Andaikan graf G mempunyai pelabelan cordial.Diketahui bahwa π β‘ 2 mod4 . Berdasarkan π teorema 2.3.4, maka β‘ 1 mod2 .
Definisi 2 Jika m suatu bilangan bulat positif, maka a kongruen dengan b modulo m (ditulis a β‘ b (mod m)) bila m membagi (a β b).Jika m tidak membagi (a-b) maka dikatakan bahwa a tidak kongruen dengan b modulo m (ditulis aβ’b (mod m)). Sifat kekongruenan : (1) Jika π β‘ π(mod m) maka π + π β‘ π + π(mod m) untuk setiap bilangan bulat c (2) Jika π β‘ π(mod m) maka ππ β‘ ππ(mod m) untuk setiap bilangan bulat c
2
Karena memenuhi ππ 0 β ππ 1 β€ 1dan banyak sisinya adalah π β‘ 2 mod4 , maka banyak sisi yang π berlabel 1 harus β‘ 1 mod2 atau ganjil. 2 Perhatikan untuk jejak tertutup euler yang dimulai dari titik berlabel 0, maka harus berakhir di titik yang sama yakni berlabel 0.Akan tetapi, karena banyak sisi yang dilabel 1 harus ganjil, maka titik terakhir jejak tersebut harus berlabel 1.Hal ini kontradiksi dengan sifat jejak tertutup euler.Maka pengandaian salah. Jadi, terbukti graf euler dengan π β‘ 2 mod4 adalah tidak cordial.
PEMBAHASAN Definisi 3 Pelabelan pada suatu graf adalah fungsi yang memasangkan unsur-unsur graf (titik atau sisi) dengan bilangan (biasanya bilangan bulat). Jika domain dari fungsi adalah himpunan titik, maka pelabelan disebut pelabelan titik (vertex labeling).Jika domain dari fungsi adalah himpunan sisi, maka pelabelan disebut pelabelan sisi (edge labeling) dan jika domain dari fungsi adalah 53
2014
MATHunesa (Volume 3 No 3)
Berdasarkan lemma 1, karena banyak titik yang berlabel πβ1 1 adalah π£π 1 β‘ 0(πππ2), maka π = β‘ 0(πππ2)
Definisi 6 Misal diberikan graf G dengan himpunan titik V(G) dan himpunan sisi E(G) dengan fungsi π: πΈ πΊ β 0,1 dan π π£ = π’π£ βπΈ(πΊ) π π’π£ (πππ2). Fungsi π disebut pelabelan E-Cordial dari G jika memenuhi kondisi sebagai berikut : 1. ππ 0 β ππ (1) β€ 1 2. π£π 0 β π£π (1) β€ 1 Dimana ππ 0 , ππ (1) berturut-turut menyatakan banyaknya sisi yang berlabel 0 dan 1, π£π 0 , π£π (1) berturut-turut menyatakan banyaknya titik yang berlabeldengan 0 dan 1. Suatu graf disebut graf E-Cordial jika memenuhi pelabelan E-Cordial.
dan π = π β π = π β π+1
πβ1
2
=
π+1 2
2
.
Didapatkan
nilai
π= = +1 =π+1 2 2 Jadi terbukti π£π 0 = π£π 1 + 1, dengan π£π 1 = π dan π£π 0 = π. Akibat 2 Jika πΊ adalah sebuah graf dengan titik sebanyak π β‘ 3(πππ4), dan π adalah sebuah pelabelan E-Cordial dari πΊ maka π£π 1 = π£π 0 + 1. Bukti : Diberikan sebuah graf G dengan titik sebanyak π β‘ 3 πππ4 dan π adalah pelabelan e-cordial pada graf G. Untuk memenuhi pelabelan e-cordial, maka π£π 0 dan π£π 1 harus memenuhi π£π 0 β π£π (1) β€ 1. Agar memenuhi syarat tersebut, dimisalkan titik π = π + π , dimana π = π£π 1 dan π = π£π 0 . Berdasarkan lemma 3.2.4, karena banyak titik yang berlabel 1 adalah π+1 π£π 1 β‘ 0(πππ2) , maka π = β‘ 0(πππ2) dan
Lemma 1 Jika dalam sebuah pelabelan π dari beberapa graf memenuhi ππ 0 β ππ (1) β€ 1, maka π£π (1) β‘ 0(πππ2) Bukti : Diberikan sebuah pelabelan π pada suatu graf G. Misal π£π dan π£π adalah titik-titik pada graf G. Jika sisi dari graf G diberikan label 1, maka label sisi tersebut akan menginduksi titik π£π , π£π tersebut. Karena pelabelan π memenuhi ππ 0 β ππ (1) β€ 1 , mengakibatkan titik yang dilabel 1 akan selalu berjumlah genap, tanpa memperhatikan banyak titik yang dilabel 0. Sehingga banyak titik yang dilabel 1 adalah π£π (1) β‘ 0(πππ2).
π =πβπ =πβ π+1
π+1 2
=
πβ1 2
2
. Didapatkan nilai π =
πβ1 2
=
β1 =πβ1 Jadi terbukti π£π 0 = π£π 1 β 1 atau π£π 1 = π£π 0 β 1 dengan π£π 1 = πdan π£π 0 = π. 2
Berikutakan dibahas sifat-sifat pelabelan cordial dan e-cordial pada graf komplit, graf sikel, graf bintang, dan graf roda. Teorema 3 Graf Komplit πΎπ adalah cordial jika dan hanya jika π β€ 3. Bukti : (β)Diberikan graf komplit πΎπ dengan π adalah pelabelan cordial pada πΎπ .Banyaknya titik pada graf komplit adalah π, maka akan dibagi menjadi 2 kasus: Kasus 1 (n genap) Banyaknya sisi pada graf komplit adalah π(πβ1) . Tanpa mengurangi keumuman, ditetapkan
Teorema 2 Syarat cukup dari pelabelan E-Cordial dengan π titik adalah jika Graf πΊ memenuhi pelabelan E-Cordial, maka π β’ 2 πππ 4 . Bukti : Diberikan graf G dengan titik sebanyak π β‘ 2(πππ4) . Karena π β‘ 2(πππ4) genap, maka untuk memenuhi pelabelan e-cordial dibutuhkan titik dengan π pelabelan yang sama yaitu π£π 0 = π£π 1 = . π
πβ1
2
2
Didapatkan π£π 0 = π£π 1 = = 1(πππ 2) . Maka 2 kontradiksi dengan Lemma 1. Jadi terbukti jika graf G memenuhi pelabelan e-cordial maka π β’ 2 πππ 4 .
π2
π 2 β2π
ππ 1 = dan ππ 0 = .Karena memenuhi 4 4 pelabelan cordial makahanya berlaku untuk πΎπ dengan n=2. Kasus 2 (n ganjil) Tanpa mengurangi keumuman, ditetapkan ππ 1 =
Akibat 1 Jika G adalah sebuah graf dengan π β‘ 1(πππ4) dan π adalah sebuah pelabelan E-Cordial dari πΊ maka π£π 0 = π£π 1 + 1. Bukti : Diberikan sebuah graf G dengan titik sebanyak π β‘ 1(πππ4) dan π adalah pelabelan e-cordial pada graf G. Untuk memenuhi pelabelan e-cordial, maka π£π 0 dan π£π 1 harus memenuhi π£π 0 β π£π (1) β€ 1. Agar memenuhi syarat tersebut, dimisalkan titik π = π + π , dimana π = π£π 1 dan π = π£π 0 .
π 2 β1
(πβ1)2
dan ππ 0 = 4 Karena memenuhi pelabelan cordial makahanya berlaku untuk πΎπ dengan π = 1 atau 3. (β) Akan dibuktikan graf komplit πΎπ dengan π β€ 3 Untuk π = 1 Perhatikan gambar πΎπ dengan π = 1 atau 4
1
0
Karena memenuhi syarat pelabelan cordial maka graf komplit πΎπ dengan π = 1 adalah cordial Untuk π = 2 54
2014
MATHunesa (Volume 3 No 3) Perhatikan gambar πΎπ dengan π = 2 1
1
Teorema 5 Graf Bintang πΎ1,π merupakan cordial Bukti: Diberikan graf bintang πΎ1,π dengan himpunan titik π = {π, π£1, π£2, β¦ , π£π } dengan π adalah titik pusat dan himpunan sisi πΈ = {π£π π ; 1 β€ π β€ π}. Untuk pelabelan titiknya didefinisikan sebagai berikut : π π =0 0, jikaπ β‘ 0(πππ2) π π£π = 1, jikaπ β‘ 1(πππ2 Dari definisi pelabelan titik dan sisi, maka diperoleh 2 kasus : Kasus 1 (n genap) : Karena banyak titik pada graf bintang πΎ1,π adalah π + π π 1,diperoleh π£π 0 = + 1dan π£π 1 = .
0
Karena memenuhi syarat pelabelan cordial maka graf komplit πΎπ dengan π = 2 adalah cordial Untuk π = 3 Perhatikan gambar πΎπ dengan π = 3 1 0
1 0
1 1
Karena memenuhi syarat pelabelan cordial maka graf komplit πΎπ dengan π = 3 adalah cordial
2
2
Untuk pelabelan sisinya diperoleh ππ 0 = ππ 1 =
Teorema 4 Graf Sikel πΆπ dengan π titik adalah cordial jika dan hanya jika π β’ 2 πππ4 . Bukti : (β) Berdasarkan teorema 1 graf sikel πΆπ adalah cordial untuk π β’ 2 πππ4 . (β) Diketahui π β’ 2 (πππ4) , berdasarkan sifat kekongruenan maka ππππ 4 β 2 Berasarkan definisi kekongruenan maka π = 4π + π, π β {0,1,3} Karena diketahui π β’ 2 (πππ4) , maka akan dibuktikan dengan 3 kasus yakni : Kasus 1 Jika π = 0 dan π = 4π β‘ 0(πππ4) Pelabelan titiknya didefinisikan sebagai berikut : 0 , jika π β‘ 1,2(πππ4) π π£π = 1 , jikaπ β‘ 0,3(πππ4) Dimana π£π 0 = 2π = π£π 1 , mengakibatkan ππ 0 = 2π = ππ 1 Kerena π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1)| β€ 1 sehingga memenuhi pelabelan cordial. Kasus 2 Jika π = 1 dan π = 4π + 1 β‘ 1(πππ4) Pelabelan titiknya didefinisikan seperti pada kasus 1, sehingga diperoleh : π+1 πβ1 π£π 0 = danπ£π 1 = 2 2 Mengakibatkan ππ 0 = ππ 1 + 1 didapatkan π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1)| β€ 1, sehingga memenuhi pelabelan cordial. Kasus 3 Jika π = 3 dan π = 4π + 3 β‘ 3(πππ4) Pelabelan titiknya didefinisikan seperti pada kasus 1, sehingga diperoleh : π+1 πβ1 π£π 0 = danπ£π 1 = 2 2 mengakibatkanππ 1 = ππ 0 + 1 didapatkan π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1)| β€ 1, sehingga memenuhi pelabelan cordial. Jadi graf sikel πΆπ dengan π β’ 2 (πππ4) adalah cordial.
π
2
Maka didapatkan π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1)| β€ 1, sehingga merupakan graf cordial. Kasus 2 (n ganjil) : Karena banyak titik pada graf bintang πΎ1,π adalah π + 1, π diperoleh π£π 0 = π£π 1 = 2
Untuk pelabelan sisinya diperoleh ππ 0 = ππ 1 =
πβ1 2
π+1 2
Maka didapatkan π£π 0 β π£π (1) β€ 1 dan ππ (1)| β€ 1, sehingga merupakan graf cordial. Jadi graf bintang πΎ1,π merupakan graf cordial.
dan
ππ 0 β
Teorema 6 Graf Roda ππ adalah cordial jika dan hanya jika π β’ 3 πππ4 . Bukti : (β)Andaikan π β‘ 3 πππ4 dengan π adalah pelabelan cordial pada graf roda ππ . Berdasarkan definisi, banyak titik pada graf roda adalah π + 1. Kita asumsikan label titik pusat adalah 0. Karena memenuhi pelabelan cordial, maka banyaknya titik yang berlabel 0 pada sikel dari πβ1 graf roda adalah dan titik yang berlabel 1 π+1
2
adalah . 2 Jika titik yang berlabel 0 diatur secara berurutan, πβ3 maka akan diperoleh sisi yang berlabel 0. Jika 2 titik yang berlabel 1 juga diatur secara berurutan , πβ1 maka akan diperoleh sisi yang berlabel 0. 2 Untuk sisi yang terkait dengan titik pusat, πβ1 banyaknya sisi yang berlabel 0 adalah . 2
Jadi banyak sisi yang berlabel 0 adalah πβ1
3πβ5
πβ3 2
+
πβ1 2
+ = β‘ 0(πππ2) 2 2 Banyak sisi pada graf roda adalah 2π . Jika π β‘ 3 πππ4 , maka ππ 0 = ππ 1 = π, dengan n ganjil. Karena banyak sisi yang berlabel 0 pada π β‘ 3 πππ4 adalah π β‘ 0(πππ2) atau genap, maka kontradiksi dengan n haruslah ganjil. Pengandaian salah. 55
MATHunesa (Volume 3 No 3) (β)
Jadi, jika graf roda ππ adalah cordial, maka π β’ 3 πππ4 Diberikan graf roda ππ dengan himpunan titik π = {π, π£1 , π£2 , β¦ , π£π } dengan π sebagai titik pusat Pelabelan titiknya didefinisikan sebagai berikut : π π =0 0, jikaπ β‘ 0,3(πππ4) π π£π = 1,jikaπ β‘ 1,2(πππ4) Karena diketahui π β’ 3(πππ4) , maka akan dibagi menjadi 3 kasus : Kasus 1 : Untuk π β‘ 1(πππ4) diperoleh π£π 0 = π£π 1 , mengakibatkan ππ 0 = ππ 1 Karena memenuhi π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1) β€ 1, maka graf roda ππ dengan π β‘ 1(πππ4) adalah graf cordial. Kasus 2 : Untuk π β‘ 2(πππ4) diperoleh π£π 1 = π£π 0 + 1, mengakibatkan ππ 0 = ππ 1 Karena memenuhi π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1) β€ 1, maka graf roda ππ dengan π β‘ 2(πππ4) adalah graf cordial. Kasus 3 : Untuk π β‘ 0(πππ4) diperoleh π£π 0 = π£π 1 + 1, mengakibatkan ππ 0 = ππ 1 Karena memenuhi π£π 0 β π£π (1) β€ 1 dan ππ 0 β ππ (1) β€ 1, maka graf roda ππ dengan π β‘ 0(πππ4) adalah graf cordial. Jadi, graf roda ππ dengan π β’ 3(πππ4) adalah graf cordial.
2014
Untuk kasus π β‘ 1 πππ4 Untuk πΎπ diperoleh π£π 0 = π£π 1 + 1 dan ππ 0 = ππ 1 . Untuk πΎπ +1 diperoleh π£π β² 1 = π£π β² 0 + 2 , ππ β² 1 = ππ β² 0 + 1. Karena π + 1 β‘ 2 πππ4 Untuk kasus π β‘ 2 πππ4 Untuk πΎπ diperoleh π£π 1 = π£π 0 + 2 dan ππ 1 = ππ 0 + 1. Untuk πΎπ +1 diperoleh π£π β² 1 = π£π β² 0 + 1 , ππ β² 1 = ππ β² 0 + 1. Jadi terbukti πΎπ dengan π β’ 2(πππ4) adalah graf e-cordial Teorema8 Graf sikel πΆπ adalah graf E-Cordialjika dan hanya jikaπ β’ 2(πππ4) Bukti : (β) Berdasarkan teorema 2 terbukti bahwa untuk memenuhi pelabelan E-cordial maka π β’ 2(πππ4). (β) Misalkan diberikan graf sikel πΆπ dengan banyaknya titik adalah π dengan himpunan titik π = {π£1 , π£2 , β¦ , π£π } dan himpunan sisi πΈ = π1 , π2 , β¦ , ππ . Untuk pelabelan sisinya didefinisikan sebagai berikut : 0, jikaπ β‘ 1,2(πππ4) π(ππ ) = 1, jikaπ β‘ 0,3(πππ4) Dari definisi tersebut akan dibuktikan graf roda πΆπ dengan π β’ 2(πππ4) adalah e-cordial pada 3 kasus, yakni : Kasus 1 Jika π β‘ 0(πππ4) Dari definisi pelabelan sisi, maka didapatkan π ππ 0 = ππ 1 = , mengakibatkan π£π 0 =
Teorema 7 Graf komplit πΎπ merupakan graf E-Cordialjika dan hanya jikaπ β’ 2(πππ4) Bukti : (β) Berdasarkan teorema 2 terbukti bahwa untuk memenuhi pelabelan E-cordial maka π β’ 2(πππ4). (β) Akan dibuktikan dengan menambahkan sebuah titik π£π +1 yang berhubungan terhadap semua titik pada graf πΎπ yang menghasilkan sebuah graf komplit πΎπ +1 , bahwa ketika sebuah graf komplit πΎπ +1 mempunyai titik π + 1 β‘ 2(πππ 4) , tidak memenuhi pelabelan E-cordial. Untuk kasus π β‘ 3 πππ4 Untuk πΎπ diperoleh π£π 1 = π£π 0 + 1 dan ππ 0 = ππ 1 + 1 Untuk πΎπ +1 diperoleh π£π β² 1 = π£π β² 0 , ππ β² 0 = ππ β² 1 . Untuk kasus π β‘ 0 πππ4 Untuk πΎπ diperoleh π£π 1 = π£π 0 dan ππ 0 = ππ 1 . Untuk πΎπ +1 diperoleh π£π β² 0 = π£π β² 1 + 1 , ππ β² 0 = ππ β² 1 .
π£π 1 =
π
2
2
.
Sehingga
memenuhi
π£π 0 β
π£π (1)| β€ 1dan ππ 0 β ππ (1) β€ 1. Oleh karena itu, graf sikel πΆπ dengan π β‘ 0(πππ4) merupakan graf e-cordial. Kasus 2 Jika π β‘ 1(πππ4) Dari definisi pelabelan sisi, maka didapatkan ππ 0 = ππ 1 + 1 yang mengakibatkan π£π 0 = π£π 1 + 1 . Sehingga memenuhi π£π 0 β π£π (1)| β€ 1dan ππ 0 β ππ (1) β€ 1. Oleh karena itu, graf sikel πΆπ dengan π β‘ 1(πππ4) merupakan graf e-cordial. Kasus 3 Jika π β‘ 3(πππ4) Dari definisi pelabelan sisi, maka didapatkan ππ 0 = ππ 1 + 1 yang mengakibatkan π£π 1 = π£π 0 + 1 . Sehingga memenuhi π£π 0 β π£π (1)| β€ 1dan ππ 0 β ππ (1) β€ 1. Oleh karena itu, graf sikel πΆπ dengan π β‘ 3(πππ4) merupakan graf e-cordial.
56
MATHunesa (Volume 3 No 3) Jadi, graf sikel πΆπ dengan β’ 2(πππ4) adalah graf cordial β Teorema 9 Graf Bintang πΎ1,π merupakan graf E-Cordial jika dan hanya jika π β’ 1(πππ4) Bukti : (β) Diberikan graf bintang πΎ1,π dengan π β‘ 1 πππ4 . Berdasarkan definisi, graf bintang πΎ1,π memiliki titik sebanyak π + 1 , yang berakibat π + 1 β‘ 2(πππ4). Oleh karena itu, kontradiksi dengan teorema 2, sehingga graf bintang πΎ1,π e-cordial untuk π β’ 1(πππ4) β Diberikan graf bintang πΎ1,π dengan himpunan titik π = {π, π£1 , π£2 , β¦ , π£π } dengan π adalah titik pusat dan himpunan sisi πΈ = { π£π π; 1 β€ π β€ π}. Untuk pelabelan sisinya didefinisikan sebagai berikut : 0, jikaπ β‘ 1,3(πππ4) π(π£π π) = 1, jikaπ β‘ 0,2(πππ4) Sebagai akibat dari pelabelan sisi, maka pelabelan titiknya didefinisikan π π£ = π’π£ βπΈ(πΊ) π π’π£ (πππ2) . Karena π β’ 1(πππ4) , maka akan dibuktikan dengan 3 kasus, yakni : Kasus 1: Untuk π β‘ 0(πππ4) Dari definisi pelabelan sisi diperoleh ππ 0 = π ππ 1 = , dan sebagai akibat dari pelabelan sisi 2
maka pada label titik diperoleh π£π 1 = π
π
2
dan
π£π 0 = + 1 2 Kasus 2: Untuk π β‘ 2(πππ4) Dari definisi pelabelan sisi diperoleh ππ 0 = π ππ 1 = , dan sebagai akibat dari pelabelan sisi 2
maka pada label titik diperoleh π£π 1 = π
π
2
dan
π£π 1 = + 1 2 Kasus 3: Untuk π β‘ 3(πππ4) Dari definisi pelabelan sisi diperoleh ππ 0 = πβ1
π+1
danππ 1 = , dan sebagai akibat dari 2 pelabelan sisi maka pada label titik diperoleh π π£π 1 = π£π 0 = . 2 Dari ketiga kasus tersebut terbukti bahwa graf bintang πΎ1,π dengan π β’ 1(πππ4) adalah graf ecordial. 2
2014
Jadi, jika graf roda ππ adalah e-cordial maka π β’ 1(πππ4) Diberikan graf roda ππ dengan himpunan titik π = {π£1 , π£2 , β¦ , π£π , π£π+1 } , himpunan sisi πΈ = {π1 , π2 , β¦ , ππ } sebagai sisi yang terkait dengan titik pada sikel dan titik pusat dan himpunan sisi πΈ = π1,2 , π2,3 , β¦ , ππ,1 sebagai sisi pada sikel dari graf πΆπ , dimana πΆπ β ππ . Didefinisikan pemetaan dari sisi yang terkait dengan titik pada sikel dan titik pusat dari graf roda ππ adalah sebagai berikut : π+1 1, jika 1β€iβ€ π(ππ ) = 2 0, untuk i lainnya Dan didefinisikan pemetaan sisi pada sikel dari graf roda ππ sebagai berikut : 0, jika π β‘ 1(πππ2) π(ππ,π+1 ) = 1, jika π β‘ 0(πππ2) Untuk pelabelan titiknya didefinisikan π π£ = π’π£ βπΈ(πΊ) π π’π£ (πππ2). Karena π β’ 1(πππ4) , maka akan dibagi menjadi 3 kasus : Kasus 1: Untuk π β‘ 0(πππ4) Karena banyak sisi pada graf roda adalah 2π maka dari definisi pelabelan sisi diperoleh ππ 0 = ππ 1 = π , dan sebagai akibat dari pelabelan sisi maka pada label titik diperoleh π£π 0 = π£π 1 + 1 Kasus 2: Untuk π β‘ 2(πππ4) Dari definisi pelabelan sisi diperoleh ππ 0 = ππ 1 = π , dan sebagai akibat dari pelabelan sisi maka pada label titik diperoleh π£π 1 = π£π 0 + 1 Kasus 3: Untuk π β‘ 3(πππ4) Dari definisi pelabelan sisi diperoleh ππ 0 = ππ 1 = π , dan sebagai akibat dari pelabelan sisi maka pada label titik diperoleh π£π 0 = π£π 1 . Dari ketiga kasus tersebut, memenuhi pelabelan e-cordial.Jadi, graf roda ππ dengan π β’ 1(πππ4) adalah graf e-cordial.
PENUTUP
Teorema 10 Graf Roda ππ , π β₯ 3 adalah E-Cordial jika dan hanya jika π β’ 1(πππ4) Bukti : β Diberikan graf roda ππ dengan π β‘ 1 πππ4 . Berdasarkan definisi, banyaknya titik pada graf roda adalah π + 1, yang berakibat ketika π β‘ 1 πππ4 maka π + 1 β‘ 2 πππ4 . oleh karena itu, kontradiksi dengan teorema 2.
Simpulan Dari pembahasan yang telah diuraikan dalam skripsi ini, dapat diambil kesimpulan bahwa : 1. Sebuah graf merupakan graf cordial jika memenuhi syarat π£π 0 β π£π 1 β€ 1 dan ππ 0 β ππ 1 β€ 1. Pelabelan sisi terinduksi dari pelabelan titiknya. Graf komplit πΎπ dan graf sikel πΆπ merupakan graf cordial dengan π β’ 2(mod4) . Graf bintang πΎ1,π dan graf 57
MATHunesa (Volume 3 No 3) roda ππ merupakan graf cordial dengan π β’ 3(mod4). 2. Sebuah graf merupakan graf e-cordial jika memenuhi syarat ππ 0 β ππ 1 β€ 1 dan π£π 0 β π£π 1 β€ 1. Pelabelan titiknya terinduksi dari pelabelan sisinya yakni π π£ = π’π£ βπΈ(πΊ) π(π’π£)(πππ2) . Graf komplit πΎπ dan graf sikel πΆπ merupakan graf e-cordial dengan π β’ 2(mod4) . Graf bintang πΎ1,π dan graf roda ππ merupakan graf e-cordial dengan π β’ 1(mod4). Saran Dalam skripsi inihanya dibahas tentang pelabelan cordial dan e-cordial pada beberapa jenis graf sederhana.Bagi para pembaca yang tertarik mengembangkan tulisan ini dapat membahas pelabelan cordial dan e-cordial pada jenis-jenis graf yang lain. 1. DAFTAR PUSTAKA Budayasa, I Ketut.2007.Teori Graph dan Aplikasinya.Surabaya : Unesa University Press. I.Cahit.Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs.Ars Combinatoria, 23, 1987, pp.201-208. Irawati, Dina. Pelabelan Total Sisi Ajaib pada Graf Bintang. Vol 2, No 1, 85-89. Padang : Universitas Andalas. Sari, Dian Noer. 2013. Pelabelan Graceful Sisi pada Graf Komplit, Graf Komplit Reguler K-Partit, Graf Roda, Graf Bisikel, dan Graf Trisikel. Skripsi tidak diterbitkan.Surabaya : FMIPA UNESA. Sukirman. 2005. Pengantar Teori Bilangan. Yogyakarta: Hanggar Kreator. Vaidya S. K and Lekha Bijukumar, 2011.Some NewFamilies of E-cordial Graphs. Journal of Mathematics Research, 3 : 105-111. Doi : 10.5539/jmr.v3n4p105 Yilmaz, R. And Cahit, I. (1997).E-Cordial Graphs, Ars.Combinatoria, No. 46 , 251-266.
58
2014