PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN...

38
PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN GRAF GARENGPUNG SKRIPSI Faiz Muhammad Khan NIM 1113094000002 PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UIN SYARIF HIDAYATULLAH JAKARTA 2020 M /1441 H

Transcript of PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN...

Page 1: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

PELABELAN PRODUCT CORDIAL PADA

GRAF MUSHROOM DAN GRAF GARENGPUNG

SKRIPSI

Faiz Muhammad Khan

NIM 1113094000002

PROGRAM STUDI MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UIN SYARIF HIDAYATULLAH JAKARTA

2020 M /1441 H

Page 2: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

i

PELABELAN PRODUCT CORDIAL PADA

GRAF MUSHROOM DAN GRAF GARENGPUNG

Skripsi

Diajukan kepada

Universitas Islam Negeri Syarif Hidayatulah Jakarta

Fakultas Sains dan Teknologi

Untuk Memenuhi Salah Satu Persyaratan dalam

Memperoleh Gelar Sarjana Matematika (S.Mat)

Oleh

Faiz Muhammad Khan

NIM 1113094000002

PROGRAM STUDI MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UIN SYARIF HIDAYATULLAH

JAKARTA

2020 M/1441 H

Page 3: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

ii

Page 4: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

iii

Page 5: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

iv

Page 6: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

v

PERSEMBAHAN DAN MOTTO

فإَ نِ مَعَِ الْعسُْرِ يسُْرًا

“Karenaِsesungguhnyaِbersama kesulitanِituِadaِkemudahan.”ِ- QS. Al - Insyirah: 5-

“skripsi ini saya persembahkan terkhusus untuk kedua orang tua saya yang tiada henti

terus bedoa untuk anak-anaknya dan tanpa perjuangan dan doa mereka apalah arti semua

perjuangan ini”

Page 7: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

vi

ABSTRAK

Faiz Muhammad Khan, Pelabelan Product Cordial Pada Graf Mushroom dan Graf

Garengpung, dibawah bimbingan, Dr. Nur Inayah , M.Si dan Yudi Mahatma , M.Si

Suatu graf 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) dikatakan memiliki pelabelan product cordial pada

𝐺 jika terdapat suatu fungsi pelabelan titik 𝑓: 𝑉(𝐺) → {0,1} yang menginduksi

pelabelan sisi 𝑓∗: 𝐸(𝐺) → {0,1} dengan 𝑓∗(𝑢𝑣) = 𝑓(𝑢) ⋅ 𝑓(𝑣), ∀𝑢𝑣 ∈ 𝐸(𝐺)

sehingga |𝑣𝑓(0) − 𝑣𝑓(1)| ≤ 1 dan |𝑒𝑓∗(0) − 𝑒𝑓∗(1)| ≤ 1. Graf 𝐺 yang memuat

pelabelan product cordial disebut graf product cordial. Pada skripsi ini, akan

dibahas tentang pelabelan product cordial pada graf mushroom 𝑀𝑟𝑚 dan graf

garengpung 𝐺𝑝(𝑚,𝑛).

Kata Kunci: Graf Product Cordial, Pelabelan Product Cordial, Graf Mushroom,

Graf Garengpung.

Page 8: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

vii

ABSTRACT

A graph 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) is side to home a product cordial labelling of 𝐺 if a

there exist function 𝑓: 𝑉(𝐺) → {0,1} induced an edge labelling 𝑓∗: 𝐸(𝐺) → {0,1}

given by 𝑓∗(𝑢𝑣) = 𝑓(𝑢). 𝑓(𝑣), ∀𝑢𝑣 ∈ 𝐸(𝐺) such that |𝑣𝑓(0) − 𝑣𝑓(1)| ≤ 1 and

|𝑒𝑓∗(0) − 𝑒𝑓∗(1)| ≤ 1. In this research we investigate whetner mushroom graph

𝑀𝑟𝑚 and garengpung graph 𝐺𝑝(𝑚,𝑛), are product cordial.

Keywords: Product Cordial Graph, Product Cordial Labelling, Mushroom Graph,

Garengpung Graph.

Page 9: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

viii

KATA PENGANTAR

Bismillahirrahmaanirrahim

Assalamu’alaikum Warahmatullahi Wabarakatuh

Alhamdulilah, segala puji-pujian dan rasa syukur khadirat Allah Yang Maha

Baik yang telah menganugerahkan penulis nikmat ilmu, kesempatan, dan hidayah-

Nya sehingga penulis dapat menyelesaikan penulisan skripsi ini yang berjudul

“Pelabelan Product Cordial pada Graf Mushroom dan Graf Garengpung”

dengan baik dan lancar. Penulisan skripsi ini merupakan salah satu kewajiban

penulis sebagai tugas akhir untuk memperoleh gelar sarjana matematika (S.Mat).

Penulis berharap skripsi ini diridhoi oleh-Nya sehingga dapat diperoleh suatu nilai

kebaikan dan manfaat di dalamnya.

Dalam penulisan skripsi ini penulis sadar bahwa banyak pihak yang terlibat

baik secara langsung maupun tidak, sehingga skripsi ini dapat terselesaikan. Untuk

itu penulis menyampaikan rasa terima kasih yang mendalam kepada :

1. Prof. Dr. Lily Surraya Eka Putri, M.Env. Stud, selaku Dekan Fakultas Sains dan

Teknologi, Universitas Islam Negeri Syarif Hidayatullah Jakarta.

2. Dr. Summaina, M.Si, selaku Ketua Program Studi Matematika dan Irma Fauziah,

M.Si, selaku Sekretaris Program Studi Matematika Fakultas Sains dan Teknologi,

Universitas Islam Negeri Syarif Hidayatullah Jakarta.

3. Dr. Nur Inayah, M.Si, selaku Pembimbing I dan Yudi Mahatma, M.Si, selaku

Pembimbing II, terima kasih atas segala ilmu, waktu, saran, dan bimbingannya

dalam penulisan skripsi ini.

4. Yanne Irene, M.Si, selaku Penguji I dan Wisnu Aribowo, M.Si, selaku Penguji II,

terima kasih atas masukan, kritik, dan saran yang telah diberikan kepada penulis

terhadap skripsi ini.

5. Seluruh dosen di Program Studi Matematika yang telah memberikan ilmunya

dengan penuh rasa sabar dan tanggung jawab.

Page 10: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

ix

6. Kedua orang tua penulis yang selalu mendukung dari jauh, Bapak Drs. Jaharih dan

Ibu Khurotulِ ‘aini beserta Adik-adik penulis Do’aِ Helmaِ Azkia dan Azzah

Nizamah, meskipun jarak memisahkan namun segala doa, nasihat, kasih sayang,

dan dukungannya selalu sampai kepada penulis terutama selama penulisan skripsi

ini sehingga terselesaikan dengan baik.

7. Keluarga besar Bapak Kastarih dan Bapak H. Syakuri yang tak pernah Lelah

memberikan doa dan dukungannya kepada penulis.

8. Angga Saputra, Wahri Irawan dan Fajrul ahsan yang telah membantu penulis.

9. Seluruh teman-teman Matematika 2013 (cypress family), terima kasih atas

kebersamaan, semangat, dan saling mengingatkan untuk segera wisuda sejak kita

saling mengenal.

10. Teman-teman HIMATIKA, MACO, KOSAN, KMSGD JABODETABEK,

PERMAI-AYU DKI JAKARTA, RUMAH JURNAL TARBIYAH, seluruh

angkatan, dan KKN penulis juga berterima kasih untuk kebersamaan yang telah kita

lalui bersama.

11. Seluruh pihak yang telah membantu penulis dalam penyusunan skripsi ini dengan

tanpa mengurangi rasa hormat yang tidak dapat penulis sebutkan satu-persatu.

Penulis menyadari dalam penulisan skripsi ini masih banyak kekurangan.

Untuk itu seluruh kritik dan saran yang membangun sangat penulis harapkan dalam

rangka saling mengingatkan dan menasehati dalam kebaikan demi kemajuan di

masa yang akan mendatang.

Wassalamu’alaikum Warahmatullahi Wabarakatuh

Jakarta, Januari 2020

Penulis

Page 11: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

x

DAFTAR ISI

HALAMAN JUDUL ........................................................................................... i

PENGESAHAN UJIAN ..................................................................................... ii

PERNYATAAN KEASLIAN ........................................................................... iii

PERNYATAAN PERSETUJUAN DAN PUBLIKASI .................................... iv

PERSEMBAHAN DAN MOTTO ..................................................................... v

ABSTRAK ......................................................................................................... vi

ABSTRACT ..................................................................................................... vii

KATA PENGANTAR ..................................................................................... viii

DAFTAR ISI ...................................................................................................... x

DAFTAR GAMBAR ........................................................................................ xii

BAB I PENDAHULUAN ................................................................................... 1

1.1 Latar Belakang....................................................................................... 1

1.2 Perumusan Permasalahan ....................................................................... 3

1.3 Pembatasan Permasalahan ..................................................................... 3

1.4 Tujuan Penulisan ................................................................................... 3

1.5 Manfaat Penulisan ................................................................................. 4

BAB II LANDASAN TEORI ............................................................................. 5

2.1 Fungsi .................................................................................................... 5

2.2 Graf ....................................................................................................... 5

2.2.1 Jenis – Jenis Graf ...................................................................... 7

2.2.2 Graf Mushroom 𝑀𝑟𝑚................................................................. 8

2.3 Pelabelan Product Cordial ..................................................................... 9

Page 12: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

xi

BAB III HASIL DAN PEMBAHASAN .......................................................... 11

3.1 Pelabelan Product Pordial pada Graf Mushroom 𝑀𝑟𝑚 ......................... 11

3.2 Graf Garengpung Gp(m,n) ...................................................................... 16

3.3 Pelabelan Product Cordial pada Graf Garengpung Gp(m,n) ................... 16

BAB IV KESIMPULANAN DAN SARAN ..................................................... 23

4.1 Kesimpulan.......................................................................................... 23

4.2 Saran ................................................................................................... 23

REFERENSI .................................................................................................... 23

Page 13: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

xii

DAFTAR GAMBAR

Gambar 1. 1. Ilustrasi Interaksi antar Keluarga....................................................2

Gambar 2. 1. Graf G1…...…………...……..…………………………………… 6

Gambar 2.2. (a) Graf Sederhana, (b) Graf Ganda, (c) Graf Umum........................7

Gambar 2.3. (a) Graf Tak-Berarah, (b) Graf Berarah................ ..........................8

Gambar 2.4. Graf Mushroom 𝑀𝑟𝑚……………...................................................9

Gambar 2.5. Pelabelan Product Cordial graf C7.................................................10

Gambar 3.1. Graf Mushroom 𝑀𝑟3………..…………………………………….12

Gambar 3.2. Graf Mushroom 𝑀𝑟4 ……...………………..……………………15

Gambar 3.3. Graf Garengpung 𝐺𝑝(𝑚,𝑛)….……..…………..………………...16

Gambar 3.4. Graf Garengpung 𝐺𝑝(3,3)…...………...………..………………...18

Gambar 3.5. Graf Garengpung 𝐺𝑝(4,4)…...…………...……..………………...19

Gambar 3.6. Graf Garengpung 𝐺𝑝(7,8)...………………..…...………………...21

Page 14: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

1

BAB I

PENDAHULUAN

1.1 Latar Belakang

Teori graf adalah disiplin ilmu yang bekembang sangat pesat pada 25 tahun

belakangan. Ilmu ini pertama muncul pada tahun 1736 tatkala Euler mencoba

menyelesaikan sebuah masalah yang terkenal: Jembatan Konigsberg.

Leonhard Euler menulis sebuah artikel mengenai masalah ini dan juga

metode yang bersifat lebih umum untuk menyelesaikan masalah-masalah lain yang

sejenis. Artikelnya sangat penting, bukan saja bagi teori graf tapi juga bagi

matematika secara umum dan pengembangannya.

Teori graf kemudian digunakan dalam studi tentang jaringan listrik, kimia

organik, teka-teki, dan pewarnaan peta. Dewasa ini teori graf digunakan secara

masif dalam bidang sains modern dan teknik yang meliputi ilmu komputer, ekologi,

geografi, antropologi, genetika, fisika, elektronika, jaringan listrik, pemrosesan

informasi, arsitektur, dan desain [1].

Pada dasarnya graf adalah himpunan titik dinotasikan dengan 𝑉 dan sisi

dinotasikan dengan 𝐸. Himpunan titik tidak kosong namun himpunan sisi bisa saja

kosong [2]. Dalam kitab suci Al-Qur’an,ِsecaraِtersirat terdapat cukup banyak ayat

yang bila diperhatikan bersinggungan dengan teori graf. Salah satu ayat dalam Al-

Qur’anِyangِbersinggunganِdenganِteoriِgraf adalah surat An-Nisa ayat 1 sebagai

berikut:

“Haiِ sekalianِ manusia,ِ bertakwalahِ kepadaِ Tuhan-mu yang telah menciptakan

kamu dari seorang diri, dan dari padanya Allah menciptakan isterinya; dan dari pada

keduanya Allah memperkembangbiakkan laki-laki dan perempuan yang banyak.

Dan bertakwalah kepada Allah yang dengan (mempergunakan) nama-Nya kamu

saling meminta satu sama lain, dan (peliharalah) hubungan silaturrahim.

SesungguhnyaِAllahِselaluِmenjagaِdanِmengawasiِkamu.”

Ayat di atas menjelaskan tentang penciptaan manusia yang diciptakan oleh

Allah saling berpasang-pasangan untuk dapat saling mengenal, saling berinteraksi,

Page 15: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

2

dan pada tujuan akhirnya adalah untuk saling mengasihi dan mempererat hubungan

silaturrahim. Secara teori graf, setiap laki-laki, perempuan dan keturunannya dapat

kita anggap sebagai titik dan proses interaksinya dapat kita anggap sebagai sisinya.

Gambar 1.1. Ilustrasi interaksi antar keluarga

Gambar 1.1 merupakan ilustrasi lima orang anggota keluarga. Setiap

anggota keluarga tersebut dapat kita ilustrasikan sebagai titik pada graf. Kelima

anggota keluarga tersebut saling berinteraksi satu sama lain dimana interaksi ini

dapat kita ilustrasikan sebagai sisi pada graf.

Salah satu cabang teori graf yang berkembang adalah konsep tentang

pelabelan atau lebih dikenal dengan istilah labeling, yaitu suatu pemetaan yang

membawa elemen-elemen graf ke bilangan-bilangan yang biasanya berupa

bilangan bulat positif atau non-negatif. Pilihan domain pelabelan yang paling lazim

digunakan adalah semua himpunan titik dan sisi yang disebut sebagai pelabelan

total, himpunan titik (pelabelan titik), atau himpunan sisi (pelabelan sisi) [3].

Pelabelan graf memainkan banyak peran vital dalam bidang ilmu

pengetahuan. Beberapa contoh dari bidang tersebut adalah astronomi, teori

pengkodean, x-ray crystallography, radar, dan manajemen database [4]. Pelabelan

graf juga bermanfaat untuk beberapa area dalam ilmu komputer dan jaringan

komputer [5]. Banyak variasi pelabelan yang ada di dalam teori graf ini salah satu

di antaranya adalah pelabelan product cordial.

Pada perkembangannya banyak yang membahas tentang pelabelan product

cordial. Misalnya, Vadya dan Kanani telah membahas tentang pelabelan product

Page 16: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

3

cordial pada beberapa graf yang terkait dengan graf lingkaran yaitu graf union dan

graf shadow [6]. Vaidya dan Barasara mempelajari pelabelan product cordial pada

beberapa graf baru yaitu pada graf 𝐹𝑛, satu chord pada graf 𝐶𝑛, dan dua chord pada

graf 𝐶𝑛 [7]. Kemudian Gao dkk mempelajari pelabelan product cordial pada graf

𝑃𝑛+1𝑚 [8].

Pelabelan product cordial yang ada dalam skripsi ini diterapkan pada graf

mushroom dan graf garengpung. Berdasarkan penjabaran yang sudah dijelaskan

penulis tertarik untuk mempelajari dan membahas secara mendalam mengenai

product cordial pada graf mushroom 𝑀𝑟𝑚 dan graf garengpung 𝐺𝑝(𝑚,𝑛). Pelabelan

tersebut memiliki suatu pola kasus ganjil dan genap yang diberikan dalam

pembuktian pada teorema yang diberikan. Pola yang sudah ada tersebut dapat

digunakan sebagai langkah dalam menghasilkan suatu persamaan.

1.2 Perumusan Permasalahan

Berdasarkan latar belakang masalah yang telah dipaparkan maka dapat

dirumuskan permasalahan yang akan dikaji dalam skripsi ini yaitu, bagaimanakah

pelabelan product cordial pada graf mushroom 𝑀𝑟𝑚 dan graf garengpung 𝐺𝑝(𝑚,𝑛).

1.3 Pembatasan Permasalahan

Pada penulisan kali ini penulis hanya akan membahas mengenai bagaimana

mengkonstruksi pelabelan poduct cordial pada graf Mushroom 𝑀𝑟𝑚 dan graf

garengpung 𝐺𝑝(𝑚,𝑛) dimana 𝑚 ≤ 𝑛.

1.4 Tujuan Penulisan

Mengkonstruksi pelabelan, membentuk pola dan menunjukan bahwa graf

mushroom 𝑀𝑟𝑚 dan graf garengpung 𝐺𝑝(𝑚,𝑛) dapat dilabeli dengan pelabelan

product cordial.

Page 17: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

4

1.5 Manfaat Penulisan

Salah satu manfaat dalam penulisan skripsi ini adalah untuk menambah

wawasan terkhusus bagi penulis dan pembaca pada umumnya mengenai graf,

terutama mengenai pelabelan product cordial.

Page 18: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

5

BAB II

LANDASAN TEORI

Dalam bab ini akan membahas mengenai definisi dan macam – macam graf,

definisi pelabelan product cordial serta definisi graf yang akan dilabeli.

2.1 Fungsi

Diberikan himpunan tidak kosong 𝐴 dan 𝐵. Suatu fungsi 𝑓 dari 𝐴 ke 𝐵

adalah penetapan tepat satu anggota 𝐵 ke setiap anggota 𝐴 yang ditulis 𝑓(𝑎) = 𝑏

dengan 𝑏 ∈ 𝐵 yang dipasangkan oleh fungsi 𝑓 ke 𝑎 ∈ 𝐴. Jika 𝑓 adalah fungsi dari

𝐴 ke 𝐵, ditulis 𝑓: 𝐴 → 𝐵 [2].

Jika 𝑓 adalah fungsi dari 𝐴 ke 𝐵, maka dapat dikatakan bahwa 𝐴

merupakan domain dan 𝐵 merupakan kodomain dari 𝑓. Jika 𝑓(𝑎) = 𝑏, maka dapat

dikatakan bahwa 𝑏 adalah image (bayangan) dari 𝑎 dan 𝑎 merupakan preimage

dari 𝑏. Range atau nama lain dari image dari 𝑓 adalah himpunan semua bayangan

dari anggota 𝐴 [2].

Bergantung pada bayangan, fungsi dapat dikelompokan menjadi menjadi

tiga kelompok, yaitu fungsi injektif, fungsi surjektif, dan fungsi bijektif [2].

Berikut adalah penjelasan mengenai ketiga kelompok fungsi tersebut.

1. Fungsi 𝑓 dikatakan fungsi injektif jika dan hanya jika 𝑓(𝑎) = 𝑓(𝑏)

berakibat 𝑎 = 𝑏 untuk setiap 𝑎, 𝑏 ∈ 𝐴.

2. Sebuah fungsi 𝑓 dari 𝐴 ke 𝐵 dikatakan fungsi surjektif jika dan hanya jika

untuk setiap anggota 𝑏 ∈ 𝐵 terdapat 𝑎 ∈ 𝐴 sehingga 𝑓(𝑎) = 𝑏 .

3. Fungsi 𝑓 dikatakan fungsi bijektif jika 𝑓 merupakan fungsi yang injektif

dan surjektif. Fungsi bijektif juga disebut korespondensi satu-satu.

2.2 Graf

Graf 𝐺 = (𝑉(𝐺), 𝐸(𝐺) didefinisikan sebagai suatu sistem yang terdiri atas

dua himpunan, yaitu himpunan tak kosong 𝑉(𝐺) yang elemennya disebut titik dan

himpunan (mungkin kosong) 𝐸(𝐺) ⊆ 𝑉2 = {(𝑢, 𝑣)|𝑢, 𝑣 ∈ 𝑉, 𝑢 ≠ 𝑣}. Setiap

elemen di 𝐸(𝐺) disebut sisi. [9].

Page 19: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

6

Gambar 2.1. Graf 𝑮𝟏

Gambar 2.1 diatas Graf 𝐺1 memiliki jumlah titik |𝑉(𝐺)| = 4 dan jumlah

sisi |𝐸(𝐺)| = 5, yaitu :

𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4} dan 𝐸 = {(𝑣1𝑣2), (𝑣2𝑣3), (𝑣3𝑣4), (𝑣4𝑣1), (𝑣2𝑣4)}.

Teori graf memiliki beberapa istilah yang sering digunakan. Dibawah ini

didefinisikan beberapa istilah yang sering dipakai.

Jalan dari 𝑣0 ke 𝑣𝑛 dengan panjang 𝑛 adalah barisan hingga

𝑣0, 𝑒0, 𝑣1, 𝑒1 … 𝑣𝑛−1, 𝑒𝑛−1, 𝑣𝑛 dari titik-titik dan sisi-sisi di 𝐺 sedemikian sehingga

𝑣𝑖𝑣𝑖+1 adalah sisi di 𝐺 untuk setiap 𝑖 < 𝑛. Lintasan adalah suatu jalan yang semua

titiknya berbeda. Titik 𝑢 dikatakan terhubung dengan titik 𝑣 jika terdapat lintasan

dari 𝑢 ke 𝑣 di 𝐺. Graf 𝐺 dikatakan terhubung jika setiap dua titik berbeda yang

terhubung [10].

Sisi dan titik dalam graf mempunyai hubungan yang biasa dikenal dengan

bertetangga dan beririsan, jika 𝑒 = (𝑢𝑣) adalah sebuah sisi dari 𝐺, maka 𝑢 dan 𝑣

adalah titik yang bertetangga yang dihubungkan oleh sisi 𝑒. Dalam hal ini berarti

titik 𝑢 dan sisi 𝑒 (begitu juga titik 𝑣 dan sisi 𝑒) dapat dikatakan bersisian satu sama

lain, sedangkan sisi berbeda yang bersisian dengan titik yang sama disebut sisi

yang bertetangga [11].

Derajat titik pada graf 𝐺 dinotasika dengan 𝑑(𝑣) adalah jumlah sisi yang

bersisian dengan titik 𝑣 [12]. Berdasarkan gambar 2.1 dapat diperoleh untuk

Page 20: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

7

derajat titik graf 𝐺1 sebagai berikut :

𝑑(𝑣1) = 2 𝑑(𝑣2) = 3 𝑑(𝑣3) = 2 𝑑(𝑣4) = 3.

Pada graf 𝐺 juga terdapat derajat sisi. Derajat sebuah sisi 𝑒 = 𝑢𝑣 dari 𝐺

didefinisikan dengan 𝑑(𝑒) = 𝑑(𝑢𝑣) = 𝑑(𝑢) + 𝑑(𝑣) − 2 [13]. Berdasarkan

gambar 2.1 dapat diperoleh juga untuk derajat sisi graf 𝐺1sebagai berikut:

1. 𝑑(𝑣1𝑣2) = 𝑑(𝑣1) + 𝑑(𝑣2) − 2 = 2 + 3 − 2 = 3

2. 𝑑(𝑣2𝑣3) = 𝑑(𝑣2) + 𝑑(𝑣3) − 2 = 3 + 2 − 2 = 3

3. 𝑑(𝑣3𝑣4) = 𝑑(𝑣3) + 𝑑(𝑣4) − 2 = 2 + 3 − 2 = 3

4. 𝑑(𝑣4𝑣1) = 𝑑(𝑣4) + 𝑑(𝑣1) − 2 = 3 + 2 − 2 = 3

2.2.1 Jenis – jenis Graf

Graf dapat dikelompokkan menjadi beberapa kategori bergantung pada

pengelompokannya. Pengelompokan graf dapat dilihat berdasarkan ada atau

tidaknya sisi ganda berdasarkan orientasi arah pada sisi [14].

Berdasarkan ada atau tidaknya sisi ganda pada suatu graf, maka secara

umum graf dapat dikelompokan menjadi dua jenis yaitu graf sederhana dan graf

tak sederhana. Graf sederhana adalah graf yang tidak mengandung sisi ganda

ataupun gelang, sedangkan graf tak sederhana adalah graf yang mengandung sisi

ganda dan jika mengandung sisi loop disebut graf semu, sisi loop adalah sisi yang

menghubungkan sebuah titik dengan dirinya (titik itu) sendiri. Graf yang terbentuk

dari sebuah sisi ganda dan loop disebut graf umum [14].

Gambar 2.2. (a) Graf Sederhana, (b) Graf Ganda, (c) Graf Umum

Berdasarkan orientasi arah dapat dikelompokkan menjadi dua jenis yaitu

Page 21: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

8

graf tak-berarah dan graf berarah. Graf tak-berarah adalah graf yang tidak

memiliki orientasi arah. Graf berarah adalah graf yang memiliki orientasi arah.

Geraf berarah 𝐺 terdiri dari himpunan titik 𝑉(𝐺) dan himpunan sisi 𝐸(𝐺) dan suatu

fungsi 𝜓 yang memetakan setiap sisi dalam 𝐸(𝐺) ke suatu pasangan berurutan titik

(𝑣𝑖, 𝑣𝑗). Jika 𝑒𝑘 adalah suatu sisi dalam 𝐺, maka 𝑣𝑖 disebut titik awal 𝑒𝑘 dan 𝑣𝑗

disebut titik akhir 𝑒𝑘, dengan arah sisi adalah dari 𝑣𝑖 ke 𝑣𝑗 [12].

Gambar 2.3. (a) Graf Tak-Berarah, (b) Graf Berarah

Berdasarkan gambar 2.3(b) dapat dilihat bahwa 𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4} dan

𝐸 = {𝑒1, 𝑒2, 𝑒3, 𝑒4}. Fungsi 𝜓 memetakan sisi-sisi graf 𝐺 dengan pasangan titik-

titik graf 𝐺 sebagai berikut : 𝜓 (𝑒1) = {𝑣1, 𝑣2}, 𝜓 (𝑒2) = {𝑣2, 𝑣3}, 𝜓 (𝑒3) =

{𝑣3, 𝑣4}, 𝜓 (𝑒4) = {𝑣4, 𝑣1}, 𝜓 (𝑒4) = {𝑣4, 𝑣2}.

2.2.2 Graf Mushroom 𝑴𝒓𝒎

Graf Mushroom 𝑀𝑟𝑚 didefinisikan untuk 𝑚 himpunan bilangan asli adalah

graf yang himpunan titik nya 𝑉 = {𝑣𝑖, 𝑤, 𝑢𝑖 | 𝑖 = 1,2,3, . . . , 𝑚} dan himpunan

sisi nya E = {𝑤𝑣𝑖 | 𝑖 = 1,2, … , 𝑚} ∪ {𝑤𝑢𝑖 | 𝑖 = 1,2, … , 𝑚} ∪ {𝑣𝑖𝑣𝑖+1 | 𝑖 =

1,2, … , 𝑚}. Ilustrasi graf mushroom 𝑀𝑟𝑚 dapat dilihat pada gambar 2.1.

Page 22: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

9

Gambar 2.4. Graf Mushroom 𝑀𝑟𝑚

2.3 Pelabelan Product Cordial

Graf product cordial mungkin merupakan versi yang lebih lemah dari graf

gracefull dan graf harmonious. Pelabelan product cordial muncul berawal dari

suatu kegagalan dalam membuktikan dugaan bahwa pelabelan gracefull dan

harmonious berlaku untuk semua tree. Pelabelan product cordial dapat diterapkan

untuk beberapa graf famili, seperti graf siklus, graf komplit, dan sebagainya [15].

Pelabelan product cordial itu sendiri mempunyai suatu aturan

kombinatorik, yaitu aturan dasar menambah dan mengalikan atau menambah saja.

Mengenai aturan kombinatorik dengan aturan dasar mengalikan, jumlah setiap

bagian titik yang dapat dituliskan dalam bentuk persamaan baik untuk bagian yang

berlabel 0 ataupun yang berlabel 1 sesuai dengan aturan bentuk pola fungsi yang

sudah ditentukan [7].

Aturan tersebut diterapkan pada pelabelan titik dan sisi. Aturan pelabelan

titik akan menghasilkan label sisi dengan mengoperasikan setiap titik yang hadir

pada sisi tersebut

Pelabelan biner titik pada graf 𝐺 yang menginduksi pelabelan sisi

𝑓∗: 𝐸(𝐺) → {0,1}, dengan 𝑓∗(𝑒 = 𝑢𝑣) = 𝑓(𝑢)𝑓(𝑣) dimana 𝑓∗ adalah pelabelan

sisi pada 𝐺 dengan perkalian titik 𝑢 dikali titik 𝑣 disebut pelabelan product cordial

atau pelabelan product cordial titik.

Page 23: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

10

Suatu graf 𝐺 disebut pelabelan product cordial jika |𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1

dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1 dengan 𝑣𝑓(𝑗) adalah banyaknya titik pada 𝐺 yang

berlabel 𝑗 atas 𝑓 dan 𝑒𝑓∗(𝑗) adalah banyaknya sisi pada 𝐺 yang berlabel 𝑗 atas 𝑓

dengan 𝑗 = 0,1. Suatu graf 𝐺 dengan pelabelan product cordial disebut graf

product cordial. [7]

Sebagai ilustrasi dari definisi definisi di atas, perhatikan graf lingkaran 𝐶7

pada gambar 1. Dapat dilihat bahwa 𝑣𝑓(0) = 3, 𝑣𝑓(1) = 4, 𝑒𝑓∗(0) = 4, 𝑒𝑓∗(1) =

3, sehingga |𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1 dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1. Jadi, graf lingkaran 𝐶7

merupakan graf product cordial [7].

Gambar 2.5. Pelabelan product cordial graf 𝐶7

Page 24: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

11

BAB III

HASIL DAN PEMBAHASAN

3.1 Pelabelan Product Cordial Pada Graf Mushroom 𝑴𝒓𝒎

Pada subbab kali ini penulis akan mengkonstruksi suatu persamaan untuk

melakukan pelabelan product cordial dari graf mushroom 𝑀𝑟𝑚 dan dijabarkan pada

teorema berikut.

Teorema 3.1 𝑀𝑟𝑚 adalah Product Cordial

Bukti: Misalkan 𝑀𝑟𝑚 adalah graf mushroom untuk 𝑚 bilangan asli.

Definisikan 𝑓: 𝑉(𝑀𝑟𝑚) → {0,1}, dengan 𝑚 akan dibagi dalam dua kasus.

Kasus 1. Untuk 𝑚 ganjil

Pembahasan :

𝑓(𝑤) = 1

𝑓(𝑢𝑖) = 1, 1 ≤ 𝑖 ≤ 𝑚−1

2

𝑓(𝑢𝑖) = 0, 𝑚+1

2≤ 𝑖 ≤ 𝑚

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤𝑚+1

2

𝑓(𝑣𝑖) = 0, 𝑚+3

2≤ 𝑖 ≤ 𝑚

Dengan pelabelan 𝑓 di atas untuk 𝑚 ganjil pada graf mushroom 𝑀𝑟𝑚 memenuhi

definisi pelabelan product cordial dengan :

|𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1 dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1

Maka diperoleh bahwa:

Page 25: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

12

𝑣𝑓(1) = 𝑚 + 1

𝑣𝑓(0) = 𝑚

𝑒𝑓∗(1) = 3𝑚−1

2

𝑒𝑓∗(0) = 3𝑚−1

2

Sehingga :

|(𝑚 + 1) − 𝑚| ≤ 1 dan |(3𝑚−1)

2−

(3𝑚−1)

2| ≤ 1

Berikut adalah contoh ilustrasi pelabelan product cordial pada graf mushroom

𝑀𝑟𝑚 untuk 𝑚 = 3, dijabarkan sebagai berikut.

𝑓(𝑤) = 1

𝑓(𝑢𝑖) = 1, 1 ≤ 𝑖 ≤ 3−1

2= 1

𝑓(𝑢𝑖) = 0, 3+1

2= 2 ≤ 𝑖 ≤ 3

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤3+1

2= 2

𝑓(𝑣𝑖) = 0, 3+3

2= 3 ≤ 𝑖 ≤ 3

Berdasarkan ilustrasi pelabelan tersebut, kita dapat membentuk graf mushroom

𝑀𝑟3 dengan pelabelan cordial yang telah diperoleh dari contoh ilustrasi yang

penulis lakukan dan ditunjukan oleh gambar 3.1.

Gambar 3.1. Graf Mushroom 𝑀𝑟3

Page 26: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

13

Selanjutnya penulis akan menghitung banyaknya label pada titik dan sisi

menggunakan aturan pelabelan product cordial dan membandingkan perhitungan

tersebut dengan melihat hasil ilustrasi di gambar 3.1. dan diperoleh:

𝑣𝑓(1) = 𝑚 + 1 = 3 + 1 = 4 , terlihat dari gambar 3.1. banyaknya titik dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 4 buah.

𝑣𝑓(0) = 𝑚 = 3 , terlihat dari gambar 3.1. banyaknya titik dengan label 0 sesuai

dengan perhitungan yaitu sebanyak 3 buah.

𝑒𝑓∗(1) = 3𝑚−1

2=

3.3−1

2= 4 , terlihat dari gambar 3.1. banyaknya sisi dengan label

1 sesuai dengan perhitungan yaitu sebanyak 4 buah.

𝑒𝑓∗(0) = 3𝑚−1

2=

3.3−1

2= 4 , terlihat dari gambar 3.1. banyaknya sisi dengan label

0 sesuai dengan perhitungan yaitu sebanyak 4 buah

Sehingga |4 − 3| = 1 ≤ 1 dan |4 − 4| = 0 ≤ 1.

Jadi, untuk graf mushroom 𝑀𝑟3 merupakan graf product cordial.

Kasus 2. Untuk 𝑚 genap.

Pembahasan :

𝑓(𝑤) = 1

𝑓(𝑢𝑖) = 1, 1 ≤ 𝑖 ≤𝑚

2

𝑓(𝑢𝑖) = 0, 𝑚+2

2≤ 𝑖 ≤ 𝑚

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤𝑚

2

𝑓(𝑣𝑖) = 0, 𝑚+2

2≤ 𝑖 ≤ 𝑚

Dengan pelabelan 𝑓 di atas untuk 𝑚 genap, graf mushroom 𝑀𝑟𝑚 memenuhi definisi

pelabelan product cordial dengan:

|𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1 dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1

Page 27: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

14

Maka diperoleh bahwa:

𝑣𝑓(1) = 𝑚 + 1

𝑣𝑓(0) = 𝑚

𝑒𝑓∗(1) =3𝑚−2

2

𝑒𝑓∗(0) = 3𝑚

2

Sehingga:

|(𝑚 + 1) − 𝑚| ≤ 1 dan |(3𝑚−2)

2−

(3𝑚)

2| ≤ 1

Berikut adalah contoh ilustrasi pelabelan product cordial pada graf mushroom 𝑀𝑟𝑚

untuk 𝑚 = 4, dijabarkan sebagai berikut.

𝑓(𝑤) = 1

𝑓(𝑢𝑖) = 1, 1 ≤ 𝑖 ≤4

2= 2

𝑓(𝑢𝑖) = 0, 4+2

2= 3 ≤ 𝑖 ≤ 4

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤4

2= 2

𝑓(𝑣𝑖) = 0, 4+2

2= 3 ≤ 𝑖 ≤ 4

Berdasarkan ilustrasi pelabelan tersebut, kita dapat membentuk graf mushroom 𝑀𝑟4

dengan pelabelan cordial yang telah diperoleh dari contoh ilustrasi yang penulis

lakukan dan ditunjukan oleh gambar 3.2.

Page 28: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

15

Gambar 3.2. Graf Mushroom 𝑀𝑟4

Selanjutnya penulis akan menghitung banyaknya label pada titik dan sisi

menggunakan aturan pelabelan product cordial dan membandingkan perhitungan

tersebut dengan melihat hasil ilustrasi di gambar 3.2. dan diperoleh:

𝑣𝑓(1) = 𝑛 + 1 = 4 + 1 = 5 , terlihat dari gambar 3.2. banyaknya titik dengan label

1 sesuai dengan perhitungan yaitu sebanyak 5 buah.

𝑣𝑓(0) = 𝑛 = 4 , terlihat dari gambar 3.2. banyaknya titik dengan label 0 sesuai

dengan perhitungan yaitu sebanyak 4 buah..

𝑒𝑓∗(1) = 3𝑛−2

2=

3.4−2

2= 5 , terlihat dari gambar 3.2. banyaknya sisi dengan label

1 sesuai dengan perhitungan yaitu sebanyak 5 buah..

𝑒𝑓∗(0) = 3𝑛

2=

3.4

2= 6 , terlihat dari gambar 3.2. banyaknya sisi dengan label 0

sesuai dengan perhitungan yaitu sebanyak 6 buah.

Sehingga |5 − 4| = 1 ≤ 1 dan |5 − 6| = −1 ≤ 1.

Jadi, untuk graf mushroom 𝑀𝑟4 merupakan graf product cordial.

Berdasarkan ilustrasi yang telah dilakukan untuk graf 𝑚𝑢𝑠ℎ𝑟𝑜𝑜𝑚 𝑀𝑟𝑚,

dapat disimpulkan untuk tiap kasus pada graf Mushroom 𝑀𝑟𝑚 memenuhi definisi

dari product cordial yaitu |𝑣𝑓(0) − 𝑣𝑓(1)| ≤ 1 dan |𝑒𝑓∗(0) − 𝑒𝑓∗(1)| ≤ 1. Oleh

karena itu graf Mushroom 𝑀𝑟𝑚 adalah graf product cordial.

Page 29: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

16

3.2 Graf Garengpung Gp(m,n)

Pada pembahasan ini dikenalkan definisi dari sebuah graf, graf tersebut

penulis beri nama graf garengpung yang di notasikan dengan Gp. Graf

garengpung Gp untuk 𝑚, 𝑛 himpunan bilangan asli adalah graf yang himpunan

titik nya

𝑉 = {𝑢𝑗 , 𝑤0 , 𝑤1, 𝑤2, 𝑣𝑖 | 𝑗 = 1,2,3, . . . , 𝑚, 𝑖 = 1,2,3, . . . , 𝑛} dan himpunan sisi

nya

𝐸 = {𝑤0𝑤1, 𝑤0𝑤2, 𝑤1𝑤2} ∪ {𝑤1𝑢𝑗 | 𝑗 = 1,2, . . . , 𝑚} ∪ {𝑤2𝑣𝑖 | 𝑖 = 1,2, . . . , 𝑛}

Ilustrasi graf garengpung Gp dapat dilihat pada gambar 3.3.

Gambar 3.3. Graf Garengpung Gp(m,n)

3.3 Pelabelan product cordial pada graf Garengpung Gp(m,n)

Pada subbab kali ini penulis akan mengkonstruksi suatu persamaan untuk

melakukan pelabelan product cordial dari graf garengpung 𝐺𝑝(𝑚,𝑛) dan dijabarkan

pada teorema berikut.

Teorema 3.2 𝐺𝑝(𝑚,𝑛) adalah product cordial

Bukti: Misalkan 𝐺𝑝 adalah graf garengpung untuk 𝑚, 𝑛 bilangan asli.

Definisikan 𝑓: 𝑉(𝐺𝑝) → {0,1}, dimana 𝑚, 𝑛 akan dibagi dalam dua kasus.

Kasus 1. Untuk 𝑚 ≤ 𝑛 dimana 𝑚, 𝑛 ganjil atau 𝑚, 𝑛 genap

Page 30: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

17

Pembahasan :

𝑓(𝑤𝑖) = 1, 1 ≤ 𝑖 ≤ 3

𝑓(𝑢𝑖) = 0, 1 ≤ 𝑖 ≤ 𝑚

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤𝑛+𝑚 −2

2

𝑓(𝑣𝑖) = 0, 𝑛+𝑚

2≤ 𝑖 ≤ 𝑛

Dengan pelabelan 𝑓 di atas, graf garengpung 𝐺𝑝(𝑚,𝑛) memenuhi definisi pelabelan

product cordial dengan:

|𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1 dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1

Maka diperoleh bahwa:

𝑣𝑓(1) =𝑚+𝑛+4

2

𝑣𝑓(0) =𝑚+𝑛+2

2

𝑒𝑓∗(1) = 𝑚+𝑛+4

2

𝑒𝑓∗(0) = 𝑚+𝑛+2

2

Sehingga:

|(𝑚+𝑛+4)

2−

(𝑚+𝑛+2)

2| ≤ 1 dan |

(𝑚+𝑛+4)

2−

(𝑚+𝑛+2)

2| ≤ 1

Berikut adalah ilustrasi pelabelan product cordial pada graf garengpung

𝐺𝑝(𝑚,𝑛)untuk 𝑚 = 3 dan 𝑛 = 3 yang akan dijabarkan sebagai berikut.

𝑓(𝑤𝑖) = 1, 1 ≤ 𝑖 ≤ 3

𝑓(𝑢𝑖) = 0, 1 ≤ 𝑖 ≤ 3

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤3+3−2

2

Page 31: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

18

𝑓(𝑣𝑖) = 0, 3+3

2≤ 𝑖 ≤ 3

Berdasarkan ilustrasi pelabelan tersebut, kita dapat membentuk graf garengpung

𝐺𝑝(3,3) dengan pelabelan product cordial yang telah diperoleh dari contoh ilustrasi

yang penulis lakukan dan ditunjukan oleh gambar 3.4.

Gambar 3.4. Graf Garengpung Gp(3,3)

Selanjutnya penulis akan menghitung banyaknya label pada titik dan sisi

menggunakan aturan pelabelan product cordial dan membandingkan perhitungan

tersebut dengan melihat hasil ilustrasi di gambar 3.4. dan diperoleh:

𝑣𝑓(1) =𝑚+𝑛+4

2 =

3+3+4

2= 5 , terlihat dari gambar 3.4. banyaknya titik dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 5 buah.

𝑣𝑓(0) =𝑚+𝑛+2

2=

3+3+2

2 = 4 , terlihat dari gambar 3.4. banyaknya titik dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 4 buah..

𝑒𝑓∗(1) = 𝑚+𝑛+4

2 =

3+3+4

2 = 5 , terlihat dari gambar 3.4. banyaknya sisi dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 5 buah..

𝑒𝑓∗(0) = 𝑚+𝑛+2

2 =

3+3+2

2 = 4 , terlihat dari gambar 3.4. banyaknya sisi dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 4 buah..

Sehingga |5 − 4 = 1| ≤ 1 dan |5 − 4| = 1 ≤ 1.

Jadi, untuk graf garengpung 𝐺𝑝(3,3) merupakan graf product cordial.

Page 32: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

19

Berikut adalah ilustrasi pelabelan product cordial pada graf garengpung

𝐺𝑝(𝑚,𝑛) untuk 𝑚 = 4 dan 𝑛 = 4 yang akan dijabarkan sebagai berikut.

𝑓(𝑤𝑖) = 1, 1 ≤ 𝑖 ≤ 3

𝑓(𝑢𝑖) = 0, 1 ≤ 𝑖 ≤ 4

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤4+4−2

2

𝑓(𝑣𝑖) = 0, 4+4

2≤ 𝑖 ≤ 4

Berdasarkan ilustrasi pelabelan tersebut, kita dapat membentuk graf garengpung

𝐺𝑝(4,4) dengan pelabelan product cordial yang telah diperoleh dari contoh ilustrasi

yang penulis lakukan dan ditunjukan oleh gambar 3.5.

Gambar 3.5. Graf Garengpung Gp(4,4)

Selanjutnya penulis akan menghitung banyaknya label pada titik dan sisi

menggunakan aturan pelabelan product cordial dan membandingkan perhitungan

tersebut dengan melihat hasil ilustrasi di gambar 3.5. dan diperoleh:

𝑣𝑓(1) =𝑚+𝑛+4

2 =

4+4+4

2= 6 , terlihat dari gambar 3.5. banyaknya titik dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 6 buah.

Page 33: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

20

𝑣𝑓(0) =𝑚+𝑛+2

2=

4+4+2

2 = 5 , terlihat dari gambar 3.5. banyaknya titik dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 5 buah.

𝑒𝑓∗(1) = 𝑚+𝑛+4

2 =

4+4+4

2 = 6 , terlihat dari gambar 3.5. banyaknya sisi dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 6 buah.

𝑒𝑓∗(0) = 𝑚+𝑛+2

2 =

4+4+2

2 = 5 , terlihat dari gambar 3.5. banyaknya sisi dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 5 buah.

Sehingga |6 − 5| = 1 ≤ 1 dan |6 − 5| = 1 ≤ 1.

Jadi, untuk graf garengpung 𝐺𝑝(4,4) merupakan graf product cordial.

Kasus 2. Untuk 𝑚 < 𝑛 dimana 𝑚 ganjil 𝑛 genap atau 𝑚 genap 𝑛 ganjil

Pembahasan :

𝑓(𝑤𝑖) = 1, 1 ≤ 𝑖 ≤ 3

𝑓(𝑢𝑖) = 0, 1 ≤ 𝑖 ≤ 𝑚

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤𝑛+𝑚 −3

2

𝑓(𝑣𝑖) = 0, 𝑛+𝑚−1

2≤ 𝑖 ≤ 𝑛

Dengan pelabelan 𝑓 di atas, graf garengpung 𝐺𝑝(𝑚,𝑛) memenuhi definisi pelabelan

product cordial dengan:

|𝑣𝑓(1) − 𝑣𝑓(0)| ≤ 1 dan |𝑒𝑓∗(1) − 𝑒𝑓∗(0)| ≤ 1

Maka diperoleh bahwa:

𝑣𝑓(1) =𝑚+𝑛+3

2

𝑣𝑓(0) =𝑚+𝑛+3

2

𝑒𝑓∗(1) = 𝑚+𝑛+3

2

Page 34: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

21

𝑒𝑓∗(0) = 𝑚+𝑛+3

2

Sehingga:

|(𝑚+𝑛+3)

2−

(𝑚+𝑛+3)

2| ≤ 1 dan |

(𝑚+𝑛+3)

2−

(𝑚+𝑛+3)

2| ≤ 1

Berikut adalah ilustrasi pelabelan product cordial pada graf garengpung

𝐺𝑝(𝑚,𝑛) untuk 𝑚 = 7 dan 𝑛 = 8 yang akan dijabarkan sebagai berikut.

𝑓(𝑤𝑖) = 1, 1 ≤ 𝑖 ≤ 3

𝑓(𝑢𝑖) = 0, 1 ≤ 𝑖 ≤ 7

𝑓(𝑣𝑖) = 1, 1 ≤ 𝑖 ≤8+7−2

2

𝑓(𝑣𝑖) = 0, 8+7−1

2≤ 𝑖 ≤ 8

Berdasarkan ilustrasi pelabelan tersebut, kita dapat membentuk graf garengpung

𝐺𝑝(7,8) dengan pelabelan product cordial yang telah diperoleh dari contoh ilustrasi

yang penulis lakukan dan ditunjukan oleh gambar 3.6.

Gambar 3.6. Graf Garengpung Gp(7,8)

Page 35: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

22

Selanjutnya penulis akan menghitung banyaknya label pada titik dan sisi

menggunakan aturan pelabelan product cordial dan membandingkan perhitungan

tersebut dengan melihat hasil ilustrasi di gambar 3.6. dan diperoleh:

𝑣𝑓(1) =𝑚+𝑛+3

2 =

7+8+3

2= 9 , terlihat dari gambar 3.6. banyaknya titik dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 9 buah.

𝑣𝑓(0) =𝑚+𝑛+3

2=

7+8+3

2 = 9 , terlihat dari gambar 3.6. banyaknya titik dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 9 buah.

𝑒𝑓∗(1) = 𝑚+𝑛+3

2 =

7+8+3

2 = 9 , terlihat dari gambar 3.6. banyaknya sisi dengan

label 1 sesuai dengan perhitungan yaitu sebanyak 9 buah.

𝑒𝑓∗(0) = 𝑚+𝑛+3

2 =

7+8+3

2 = 9 , terlihat dari gambar 3.6. banyaknya sisi dengan

label 0 sesuai dengan perhitungan yaitu sebanyak 9 buah.

Sehingga |9 − 9| = 0 ≤ 1 dan |9 − 9| = 0 ≤ 1.

Jadi, untuk graf garengpung 𝐺𝑝(7,8) merupakan graf product cordial.

Berdasarkan ilustrasi yang telah dilakukan untuk graf garengpung 𝐺𝑝(𝑚,𝑛)

dapat disimpulkan untuk tiap kasus pada graf garengpung 𝐺𝑝(𝑚,𝑛) memenuhi

definisi dari product cordial yaitu |𝑣𝑓(0) − 𝑣𝑓(1)| ≤ 1 dan |𝑒𝑓∗(0) − 𝑒𝑓∗(1)| ≤ 1.

Oleh karena itu graf garengpung 𝐺𝑝(𝑚,𝑛) adalah graf product cordial.

Page 36: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

23

BAB IV

KESIMPULAN DAN SARAN

4.1 Kesimpulan

Berdasarkan hasil pembuktian, maka dapat diperoleh Teorema, Teorema

3.1 dan teorema 3.2 menyatakan bahwa graf mushroom 𝑀𝑟𝑚 dan graf garengpung

𝐺𝑝(𝑚,𝑛) memuat pelabelan product cordial maka graf mushroom 𝑀𝑟𝑚 dan graf

garengpung 𝐺𝑝(𝑚,𝑛) adalah graf product cordial.

4.2 Saran

Penulisan skripsi ini terbatas pada pelabelan product cordial pada graf

mushroom 𝑀𝑟𝑚 dan graf garengpung 𝐺𝑝(𝑚,𝑛) selanjutnya dapat dikembangkan

lebih banyak lagi untuk graf yang lainnya.

Page 37: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

24

REFERENSI

[1] H. Muhammad Yahya, "Matematika Diskrit", Bandung: IKIP Bandung Press,

1998.

[2] Kenneth H. Rosen, "Discrete Mathematics and Its Applications", New York

McGraw-Hill: RPK Editorial Services, 2007.

[3] W. Wallis, P. Shoubridge, M. Kraetz and D. Ray, "Graph distance using graph

union". Patern Recognition Latter, no. 22, pp. 701-704, 2001.

[4] R. Ponraj, S. Sathis Narayanan and R. Kala, "Difference Cordial Labeling Of

Subdivision Of Snake Graphs", Universal Journal Of Applied Mathematics,

no. 2(1), pp. 40-45, 2014.

[5] S. K. Vaidya and N. Shah, "Some New Result On Prime Cordial Labeling",

Research Article. Hindawi Publishing Corporation, no. 9, p. 9, 2014.

[6] S. K. Vaidya and K. K. Kanani, "Some cycle Related Product Cordial

Graphs", International Journal Of Algorithms, Computing and Mathematics,

vol. 3, no. 1, pp. pp. 109-116, 2010.

[7] S. K. Vaidya and C. M. Barasara, "Product Cordial Labelling For Some New

Graphs", Journal Of Mathematics Research, vol. 2, no. 2, pp. 206-211, 2011.

[8] Z. Ghao, G. Sun, Y. Sun, Y. Meng and G. Lau, "Product Cordial and Total

Product Cordial Labeling Of Pn+1m , " Journal of Discrete Mathematics, 2015.

[9] E. K. Lloyd, A. Bondy and U. S. R. Murty, "Graph Theory with Application,"

Math Gaz, vol. 62, no. 419, p. 63, 1978.

[10] N. Hartsfield and G. Ringel, "Pearl in Graph Theory Comprehensive

Introduction", San Diego: Academic Press Limited, 1990.

[11] Chartrand, dkk, "Applied and Algoritmatic Graph Theory", Mac Graw-Hill:

New york, 2005.

[12] M. Jong Jek Siang, "Matematika Diskrit dan Aplikasinya pada ilmu

komputer", Yogyakarta: ANDI, 2006.

[13] S. K.Vaidya and R. M. Pandit, "Edge Domination in Various Snake Graphs,"

Math Soft Comput, vol. 7, no. 1, p. 43, 2017.

[14] R. J. Wilson, "Pengantar Teori Graf ", Jakarta: Erlangga, 2010.

Page 38: PELABELAN PRODUCT CORDIAL PADA GRAF MUSHROOM DAN …repository.uinjkt.ac.id/dspace/bitstream/123456789/50616... · 2020. 3. 25. · , satu chord pada graf , dan dua chord pada graf

25

[15] I. Cahit, "Cordial Graph : A Weaker Version Of Gracefull and Harmonious

Graphs," ARS Combinatoria 23(1987), pp. 201-208, no. 23, pp. 201-208,

1987.

[16] B. Harianto, "Pelabelan Product Cordial Pada Graf Dragonfly," PROSIDING

SENAMAS SEMINAR NASIONAL MATEMATIKA INDOMS WILAYAH

SULAWESI 2017, vol. 1, no. 1, pp. pp. 96-100, 2017.