penentuan bilangan ramsey pada graf bintang s2n terhadap graf...

PENENTUAN BILANGAN RAMSEY PADA GRAF BINTANG S2n

TERHADAP GRAF RODA Wn DENGAN n ≥ 10 DAN n GENAP

THE DETERMINATION OF RAMSEY NUMBER FOR THE STAR GRAPH

S2n VERSUS WHEELS Wn WITH n ≥ 10 AND n EVEN

NUR ROHMAH OKTAVIANI PUTRI

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN

MAKASSAR

2017

ii

PENENTUAN BILANGAN RAMSEY PADA GRAF BINTANG S2n

TERHADAP GRAF RODA Wn DENGAN n ≥ 10 DAN n GENAP

Tesis

Sebagai Salah Satu Syarat Untuk Mencapai Gelar Magister

Program Studi

Matematika

Disusun dan diajukan oleh

NUR ROHMAH OKTAVIANI PUTRI

Kepada

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN

MAKASSAR

2017

iv

PERNYATAAN KEASLIAN TESIS

Yang bertanda tangan di bawah ini :

Nama : Nur Rohmah Oktaviani Putri

Nomor Mahasiswa : P3500215008

Program Studi : Matematika

Menyatakan dengan sebenarnya, bahwa tesis yang saya tulis ini

benar – benar merupakan hasil karya saya sendiri, bukan merupakan

pengambilalihan tulisan atau pemikiran orang lain. Apabila dikemudian

hari terbukti, atau dapat dibuktikan bahwa sebagian atau keseluruhan

tesis ini hasil karya orang lain, saya bersedia menerima sanksi atas

perbuatan tersebut.

Makassar, 8 Agustus 2017

Yang menyatakan,

Nur Rohmah Oktaviani Putri

v

PRAKATA

Alhamdulillahi Rabbil Alamin. Tak ada kalimat indah lain yang

mampu menggambarkan ungkapan syukur penulis ke hadirat Allah SWT.

Karena atas limpahan rahmat, hidayah, dan kasih sayang-Nya, penulis

masih diberikan kesempatan dan kesehatan sehingga tesis ini dapat

terselesaikan dengan baik. Shalawat dan salam juga tak henti – hentinya

tercurah kepada Baginda Rasulullah SAW sebagai tauladan bagi umat

muslim.

Tesis ini dapat terselesaikan berkat bantuan dan motivasi dari

berbagai pihak. Oleh karena itu, penulis menyampaikan ucapan terima

kasih yang tulus dan mempersembahkan karya ini kepada : kedua orang

tua, terkhusus Ibunda Sri Maryani, S.Pd yang tak pernah berhenti

mendoakan dan memberikan motivasi, Moch. Dimas Saputra, A.Md

selaku adik dari penulis, serta keluarga lainnya di Jawa.

Penghargaan yang tulus dan ucapan terima kasih dengan penuh

keikhlasan juga penulis ucapkan kepada :

1. Prof. Dr. Hasmawati dan Dr. Loeky Haryanto, MS., M.Sc., MA.

selaku pembimbing pertama dan kedua, yang dengan kesabaran

dan keikhlasannya telah membimbing serta membagi ilmunya.

2. Prof. Dr. Amir Kamal Amir, Prof. Dr. Hj. Aidawayati Rangkuti, MS,

dan Dr. Eng. Mawardi, M.Si selaku penguji yang sudah

memberikan banyak kritik dan saran yang sangat membangun.

vi

3. Seluruh dosen Prodi Matematika Unhas yang telah membimbing,

mendidik, serta membekali penulis dengan ilmu yang berguna.

4. Dekan, Wakil Dekan, staf fakultas, Bu Evi, dan Pak Irsan yang

selama ini banyak membantu penulis dalam urusan administrasi.

5. PRISMA 2015 : Riska, Mala, Kak Meri, Kak Dian, Kak Tina, Yaya,

Kak Anita, Kak Rika, Dina, Kak Nitnot, Ikbal, Fajrin, Kak Syukur,

Kak Armin, Kak Amil, Kak Muhlis, Kak Aris, dan Pak Agus.

6. Senior dan junior PPs Matematika angkatan 2012, 2013 2014, dan

2016. Terkhusus Kak Lisa, Kak Agus, Kak Edy, Kak Ammar, dan

Kak Ilmy yang setahun belakangan ini banyak menemani penulis.

7. Regresi 2010 : Inda, Juni, Madi, Ryan, Kiky, dan lainnya yang tak

sempat disebut. Kanda dan adinda di Himatika FMIPA Unhas,

adikku Oktosar Sabri, serta adik – adik panitia SENAMAS 2017.

8. Semua pihak yang tidak dapat disebutkan satu persatu.

Dengan segala kerendahan hati, penulis menerima segala kritik

dan saran yang dapat membantu penyempurnaan tesis ini. Semoga

segala bantuan yang telah diberikan bernilai ibadah dan mendapat

imbalan yang setimpal dari Allah SWT. Akhir kata, semoga tulisan ini

dapat memberikan manfaat bagi semua pihak yang membutuhkan. Amin

Yaa Rabbal Alamin.

Makassar, 8 Agustus 2017

Nur Rohmah Oktaviani Putri

ix

DAFTAR ISI

HALAMAN JUDUL i

HALAMAN PENGAJUAN ii

HALAMAN PENGESAHAN iii

LEMBAR PERNYATAAN KEASLIAN iv

PRAKATA v

ABSTRAK vii

ABSTRACT viii

DAFTAR ISI ix

DAFTAR TABEL xi

DAFTAR GAMBAR xii

DAFTAR ARTI LAMBANG xiv

BAB I. PENDAHULUAN

A. Latar Belakang ………………………………………… 1

B. Rumusan Masalah ………………………………………… 5

C. Tujuan Penelitian ………………………………………… 6

D. Manfaat Penelitian ………………………………………… 6

E. Batasan Masalah ………………………………………… 6

BAB II. TINJAUAN PUSTAKA

A. Tinjauan Pustaka

1. Konsep Dasar Graf ………………………………………… 7

2. Pewarnaan dan Operasi Dalam Graf …………………… 12

x

3. Jenis – Jenis Graf ………………………………………… 15

4. Beberapa Teorema, Lemma, dan Sifat Yang Terkait Batas Bawah dan Batas Atas Bilangan Ramsey ………………

24

5. Bilangan Ramsey ………………………………………… 30

B. Kerangka Pikiran ………………………………………… 36

BAB III. METODOLOGI PENELITIAN

A. Rancangan Penelitian ………………………………… 38

B. Metode yang Digunakan ………………………………… 39

C. Lokasi dan Waktu Penelitian ………………………………… 39

BAB IV. HASIL DAN PEMBAHASAN

A. Penentuan Bilangan Ramsey 𝑅(𝑆20 , 𝑊10) …………………… 40

B. Penentuan Bilangan Ramsey 𝑅(𝑆24 , 𝑊12) …………………… 45

C. Penentuan Bilangan Ramsey 𝑅(𝑆28 , 𝑊14) …………………… 50

D. Penentuan Bilangan Ramsey 𝑅(𝑆32 , 𝑊16) …………………… 55

E. Penentuan Bilangan Ramsey 𝑅(𝑆36 , 𝑊18) …………………… 60

BAB V. KESIMPULAN DAN SARAN

A. Kesimpulan ……………………………………………… 70

B. Saran ……………………………………………… 71

DAFTAR PUSTAKA 72

xi

DAFTAR TABEL

Nomor Halaman

1. Hasil Penelitian Bilangan Ramsey Graf 34

xii

DAFTAR GAMBAR

Nomor Halaman

1. Graf Sederhana 9

2. Graf H Adalah Pseudograf 10

3. Derajat Titik Pada Graf 𝐺 11

4. Graf, Subgraf, dan Komplemennya 12

5. Pewarnaan Titik Pada 𝑊7, 𝑊6, dan 𝑆7 13

6. Pewarnaan – 𝑓 pada graf 𝐺 14

7. (a) Graf 𝑃3 ∪ 𝐾 4 dan (b) Jumlah graf 𝑃3 + 𝐾 4 15

8. Graf Siklus 16

9. Graf Lengkap 17

10. Graf Bipartit 17

11. Graf Siklus 𝐶6 17

12. Graf Bipartit Lengkap 18

13. (a) Graf Bipartit (b) Graf Multipartit (c) Graf multipartit Lengkap (d) Graf Multipartit Seimbang

19

14. Jalur Euler 𝑎𝑏𝑑𝑐𝑏𝑓𝑒𝑑𝑓 Pada Graf 𝑀 dan Sirkuit Euler 𝑢𝑟𝑠𝑡𝑟𝑞𝑝𝑢 Pada Graf 𝑁

19

15. Graf Hamilton Dengan siklus 𝑎𝑏𝑐𝑕𝑙𝑔𝑘𝑓𝑜𝑗𝑛𝑠𝑡𝑝𝑞𝑟𝑚𝑖𝑑𝑒𝑎 21

16. Graf Semi-Hamilton 𝐺 21

17. Graf Pohon 22

18. Graf Bintang 22

19. Graf Roda 23

xiii

20. 𝐺1 Graf Pansiklik dan 𝐺2 Graf Pansiklik Lemah 23

21. Graf Non Pansiklik 24

22. Graf 𝐺 25

23. Graf Non Bipartit 𝐻 26

24. Graf Terhubung 𝐺 dan Graf Tak Terhubung 𝐺 − 𝑐 dan 𝐺 − 𝑒4

27

25. Berat titik pada graf 29

26. Pewarnaan Pada Graf 𝐾10 31

27. Identifikasi 𝑆4 pada 𝐹 dan 𝑊5 pada 𝐹 32

28. Flowchart Penelitian 37

29. Graf 𝐹 = 2𝐾3×7 41

30. Komplemen Graf 𝐹 41

31. Graf 𝐾23 ∪ 𝑇 45


33. Graf 𝐹 = 𝐾2×14 ∪ 𝐾5×6 50


35. Graf 𝐹 = 𝐾2×16 ∪ 𝐾6×6 56


37. Graf 𝐾35 ∪ 𝐾8×5 61


39. Graf 𝐹 = 𝐾2𝑛−1 ∪ 𝐾𝑛−2

2×5

65


xiv

DAFTAR ARTI LAMBANG

Lambang Arti dan Keterangan

∪𝑖=1𝑘 𝐺𝑖 Gabungan saling lepas graf 𝐺𝑖

𝐵𝑛1 ,𝑛2 ,…,𝑛𝑘 Graf multipartit

𝐵𝑛1 ,𝑛2 Graf bipartit

𝐶𝑛 Graf siklus berorde 𝑛

𝐸 𝐺 Ukuran atau banyaknya sisi pada graf 𝐺

𝐺 Komplemen graf 𝐺

𝐺1 + 𝐺2 Graf jumlah

𝐺𝑛 Graf 𝐺 dengan 𝑛 titik

𝐾𝑛1 ,𝑛2 ,…,𝑛𝑘 Graf multipartit lengkap

𝐾𝑘×𝑡 Graf multipartit seimbang

𝐾𝑛 Graf lengkap berorde 𝑛

𝑃𝑛 Graf lintasan berorde n

𝑆𝑛 Graf bintang berorde 𝑛

𝑇𝑛 Graf pohon berorde 𝑛

𝑊𝑛 Graf roda berorde 𝑛 + 1

𝑑(𝑣𝑖) Derajat titik 𝑣𝑖

𝑑(𝑢, 𝑣) Jarak dari titik 𝑢 ke titik 𝑣 di 𝐺

|𝐹| Kardinalitas himpunan 𝐹

∅ Himpunan kosong

⊉ Tidak memuat

⨁ Dekomposisi

ℕ Bilangan asli

Δ 𝐺 Derajat titik maksimum dari suatu graf 𝐺

𝐶(𝐺) Banyaknya titik pada komponen terbesar graf 𝐺

𝐸(𝐺) Himpunan sisi pada graf 𝐺

𝐺 – 𝑒 Subgraf dari 𝐺 dengan menghilangkan sisi 𝑒 dari 𝐺

xv

𝐺 – 𝑣 Subgraf dari 𝐺 dengan menghilangkan titik 𝑣 dari 𝐺

𝐺(𝑉, 𝐸) Graf dengan himpunan titik 𝑉 dan himpunan sisi 𝐸

𝐺[𝑆] Subgraf dari 𝐺 yang diinduksi oleh himpunan titik 𝑆

𝐺\𝐻 Subgraf dari 𝐺 yang diinduksi oleh himpunan titik 𝑉 𝐺 \𝑉(𝐻)

𝐺 + {𝑢𝑣} Graf 𝐺 tambah sisi 𝑢𝑣

𝑅(𝐺1, 𝐺2, … , 𝐺𝑘) Bilangan Ramsey untuk graf 𝐺1, 𝐺2, … , 𝐺𝑘

𝑅(𝑆𝑛 , 𝑊𝑛) Bilangan Ramsey graf bintang terhadap graf roda

𝑅(𝐺, 𝐻) Bilangan Ramsey untuk graf 𝐺 dan 𝐻

𝑉(𝐺) Himpunan titik pada graf 𝐺

𝑐(𝐺) Circumference atau panjang siklus terbesar pada suatu graf 𝐺

𝑑𝑖𝑎𝑚 𝐺 Diameter atau jarak terbesar dari setiap dua titik pada 𝐺

𝑒(𝑣) Eksentrisitas atau jarak antara titik 𝑣 dengan sebuah titik terjauh dari 𝑣

𝑔(𝐺) Girth atau panjang siklus terkecil pada suatu graf 𝐺

𝑟𝑎𝑑 𝐺 Radius atau eksentrisitas minimum dari titik pada 𝐺

𝛼(𝐺) Kardinalitas himpunan bebas terbesar dari 𝐺

𝛿(𝐺) Derajat titik minimum dari suatu graf 𝐺

𝜅(𝐺) Keterhubungan titik pada 𝐺

𝜒(𝐺) Bilangan kromatik 𝐺

1

BAB I

PENDAHULUAN

A. Latar Belakang

Graf umumnya merupakan suatu model Matematika yang

digunakan untuk menganalisa banyak masalah kongkrit yang

berhubungan dengan dunia nyata. Beberapa masalah dalam Fisika,

Kimia, Sains Komunikasi, Teknologi Komputer, Genetika, Psikologi dan

Sosiologi bisa diformulasikan sebagai masalah dalam teori graf. Selain itu,

cabang Matematika seperti teori grup, matriks, peluang, dan topologi juga

memiliki implementasi dalam teori graf (Balakrishnan & Ranganathan,

2012).

Tiga puluh tahun terakhir ini merupakan periode yang sangat

intensif dalam aktivitas pengembangan teori graf baik murni maupun

terapan. Sejumlah penelitian besar telah dilakukan, ribuan artikel telah

diterbitkan dan banyak buku telah ditulis. Di antaranya orang terkenal

yang banyak berkecimpung dalam bidang ini adalah J.A. Bondy, Paul

Erdos, Frank Harary, dan masih banyak lagi.

Graf didefinisikan sebagai struktur diskrit yang terdiri dari pasangan

himpunan berhingga dari obyek yang disebut titik (vertex) dan pasangan

titik yang disebut sisi (edge). Jumlah sisi yang berkaitan dengan suatu titik

pada suatu graf disebut derajat. Suatu graf yang memiliki 2 titik berderajat

2

1 dan titik lainnya berderajat 2 disebut lintasan. Jika untuk setiap

pasangan titik 𝑢 dan 𝑣 pada suatu graf, terdapat lintasan dari 𝑢 ke 𝑣, maka

graf tersebut disebut graf terhubung.

Terdapat beberapa graf khusus antara lain lintasan, graf siklus, graf

bipartit, graf lengkap, graf Euler, graf Hamilton, graf bintang, graf roda, dan

lain-lain. Lintasan adalah graf yang dua titiknya berderajat 1 dan titik – titik

lainnya berderajat 2. Graf dikatakan terhubung jika dua titiknya

dihubungkan oleh suatu lintasan. Suatu graf terhubung yang setiap titiknya

berderajat dua disebut graf siklus. Graf siklus berorde n dilambangkan

dengan 𝐶𝑛 . Graf 𝐺 yang himpunan titiknya dapat dipisah menjadi dua

himpunan bagian 𝑉1 dan 𝑉2, sedemikian sehingga setiap sisi pada 𝐺

menghubungkan sebuah titik di 𝑉1 ke sebuah titik di 𝑉2 disebut graf bipartit.

Selanjutnya, jalur pada graf 𝐺 disebut jalur Euler apabila melewati

setiap sisi di 𝐺 tepat satu kali. Jika suatu jalur Euler berawal dan berakhir

pada titik yang sama (tertutup), maka jalur itu disebut sirkuit Euler. Suatu

graf yang memiliki sirkuit Euler disebut graf Euler. Sedangkan graf yang

hanya memiliki jalur Euler disebut graf semi Euler.

Selain graf Euler, graf yang memiliki sifat yang berbeda dengan

graf-graf lainnya yaitu graf Hamilton. Lintasan Hamilton adalah lintasan

yang melalui setiap titik di dalam graf tepat satu kali. Bila lintasan tersebut

kembali ke titik awal membentuk siklus, maka siklus tersebut dinamakan

siklus Hamilton. Graf 𝐺 disebut graf Hamilton jika 𝐺 memuat siklus

Hamilton.

3

Suatu graf yang terdiri atas satu titik berderajat 𝑛 – 1 dan titik lainnya

berderajat satu disebut graf bintang. Graf bintang dengan 𝑛 titik

dinotasikan dengan 𝑆𝑛 . Selain graf bintang, dikenal pula graf roda atau

biasa disimbolkan dengan 𝑊𝑚 . Graf roda merupakan graf yang diperoleh

dengan cara menambahkan satu titik pada graf lingkaran 𝐶𝑛 , dan

menghubungkan titik tersebut dengan semua titik pada graf lingkaran

tersebut.

Salah satu topik kajian dalam teori graf yang berkaitan dengan

kombinatorik yaitu mengenai penentuan bilangan Ramsey, Perkembangan

teori ini diawali dari ide dasar mengenai bilangan Ramsey klasik dua

warna oleh Erdos dan Szekeres (Wikipedia, 2016). Adapun definisi

bilangan Ramsey dua warna, yaitu : diberikan sebarang dua graf 𝐺 dan 𝐻,

bilangan Ramsey graf dua warna 𝑅(𝐺, 𝐻) adalah bilangan asli terkecil 𝑚

sedemikian sehingga untuk setiap pewarnaan dengan dua warna pada

setiap sisi graf lengkap 𝐾𝑚 katakanlah merah atau biru, maka 𝐾𝑚 akan

selalu memuat subgraf merah yang isomorf dengan 𝐺 atau subgraf biru

yang isomorf dengan 𝐻.

Selanjutnya, Chvátal dan Harary (1972) menemukan batas bawah

untuk 𝑅(𝐺, 𝐻), yaitu 𝑅 𝐺, 𝐻 ≥ 𝜒 𝐻 − 1 𝐺 − 1 + 1) dengan 𝜒 𝐻

merupakan bilangan kromatik graf 𝐻. Sejak saat itu, banyak peneliti yang

mengkaji tentang bilangan Ramsey. Salah satunya adalah Parson (1973)

yang mengkaji tentang bilangan Ramsey untuk graf lintasan dan graf

lengkap 𝑅 𝑃𝑛 , 𝐾𝑚 . Selanjutnya Chvátal (1977) memperluas kajian

4

tentang bilangan Ramsey untuk graf pohon dan graf lengkap 𝑅(𝑇𝑛 , 𝐾𝑚 ).

Kemudian, Burr S.A. (1984) mengkaji bilangan Ramsey 𝑅 𝐺, 𝑛𝐻 dan

𝑅(𝑛𝐺, 𝑛𝐻) untuk 𝐺 dan 𝐻 merupakan graf lengkap 𝐾𝑘 dan 𝐾𝑙 dan

menghasilkan 𝑅 𝐾𝑘 , 𝑛𝐻 = 𝑛 ∙ 𝑙 + 𝑟 𝐾𝑘−1, 𝐻 − 1 serta

𝑅 𝑛𝐾𝑘 , 𝑛𝐾𝑙 = 𝑘 + 𝑙 − 1 𝑛 + 𝑅 𝐾𝑘−1, 𝐾𝑙−1 − 2.

Pada tahun berikutnya, Surahmat dkk (2004) mengkaji tentang

bilangan Ramsey untuk graf siklus dan graf roda dan menghasilkan

𝑅 𝐶𝑛 , 𝑊4 = 2𝑛 − 1 dan 𝑅 𝐶𝑛 , 𝑤6 = 3𝑛 − 2, untuk 𝑛 ≥ 5 dan pada

tahun 2006, ia juga menghasilkan bilangan Ramsey untuk graf siklus dan

graf roda, yaitu 𝑅 𝐶𝑛 , 𝑊𝑚 = 3𝑛 − 2 dimana 𝑚 ganjil, 𝑚 ≥ 5, dan

𝑛 ≥5𝑚−9

2. Pada tahun yang sama, Chen Y. dkk (2004) mengkaji bilangan

Ramsey antara graf bintang dan graf roda yang menghasilkan

𝑅 𝑆𝑛 , 𝑊6 = 2𝑛 + 1 dimana n ≥ 3 dan 𝑅 𝑆𝑛 , 𝑊𝑚 = 3𝑛 − 2 untuk m ganjil

dan 𝑛 ≥ 𝑚 – 1 ≥ 2.

Selanjutnya, Hasmawati dkk (2008) mengkaji bilangan Ramsey

untuk graf gabungan saling lepas bintang dan siklus yang menghasilkan

𝑅 𝑘𝑆1+𝑝 , 𝐶4 = 𝑘 𝑝 + 1 + 1 untuk 𝑘 ≥ 2 dan 𝑝 ≥ 3. Pada tahun 2009,

ia juga melakukan penelitian dan menghasilkan 𝑅 𝑆𝑛 , 𝑊𝑚 = 3𝑛 − 6,

dimana 𝑚 = 2𝑛 − 8 atau 2𝑛 − 6 dan 𝑛 ganjil. Kemudian Hamdana

Hadaming (2014) membahas tentang bilangan Ramsey pada graf bintang

𝑆2𝑛 versus roda 𝑊𝑚 dengan 𝑚 = 2𝑛 + 2 dan 𝑛 ≥ 4 yang menghasilkan

𝑅 𝑆2𝑛 , 𝑊2𝑛+2 = 5𝑛 − 1 dan Andi Ardhilla (2014) menemukan bilangan

5

Ramsey graf bintang 𝑆𝑛 versus roda 𝑊𝑛+4 yang menghasilkan

𝑅 𝑆2𝑛 , 𝑊𝑛+4 = 2𝑛 +𝑛

2.

Hingga saat ini, perkembangan kajian tentang bilangan Ramsey

berkembang sangat pesat. Dalam uraian sebelumnya dapat dilihat bahwa

bilangan Ramsey untuk graf bintang terhadap graf roda berorde ganjil

sudah banyak ditemukan. Namun bilangan Ramsey untuk graf bintang

berorde genap terhadap roda berorde sembarang dengan orde bintang

yang lebih besar daripada orde roda masih kurang. Oleh karena itu, dalam

penelitian ini akan dikaji bilangan Ramsey pada graf bintang berorde

genap terhadap roda 𝑊𝑛 dimana n ≥ 10.

B. Rumusan Masalah

Berdasarkan uraian di atas, maka rumusan masalah pada

penelitian ini disusun dalam bentuk pertanyaan sebagai berikut :

1. Bagaimana konstruksi graf kritis untuk mendapatkan batas bawah

bilangan Ramsey graf bintang berorde genap terhadap roda

berorde sembarang?

2. Bagaimana menentukan batas atas bilangan Ramsey untuk graf

bintang berorde genap terhadap roda berorde sembarang?

3. Apakah terdapat batas atas dan batas bawah yang nilainya sama?

6

C. Tujuan Penelitian

Adapun tujuan dari penelitian ini antara lain :

1. Menentukan konstruksi graf kritis maksimal dan batas bawah

terbesar bilangan Ramsey graf bintang berorde genap terhadap

roda berorde sembarang.

2. Menentukan batas atas bilangan Ramsey untuk graf bintang

berorde genap terhadap roda berorde sembarang.

3. Mencari bilangan Ramsey graf bintang berorde genap terhadap

roda berorde sembarang yang eksak.

D. Manfaat Penelitian

Hasil penelitian ini diharapkan dapat menambah pengetahuan

penulis tentang penentuan bilangan Ramsey, khususnya untuk graf yang

memuat bintang dan roda. Selain itu, dapat menjadi referensi bagi peneliti

lain yang akan melakukan penelitian yang terkait dengan bilangan

Ramsey graf yang memuat bintang dan roda.

E. Batasan Masalah

Kajian bilangan Ramsey untuk bintang dan roda meliputi cakupan

yang luas, olehnya itu penulis membatasi permasalahan pada penentuan

bilangan Ramsey untuk bintang 𝑆2𝑛 versus roda 𝑊𝑛 untuk 𝑛 ≥ 10.

7

BAB 2

TINJAUAN PUSTAKA

Pada bab ini dijelaskan tentang konsep dasar, serta beberapa

istilah – istilah penting dalam teori graf. Selain itu, akan disajikan kerangka

pemikiran dan flowchart yang berkaitan dengan penelitian ini.

A. Tinjauan Pustaka

Dalam subbab ini akan dikaji beberapa definisi, teorema, dan

lemma yang akan digunakan dalam membuktikan hasil penelitian.

1. Konsep Dasar Graf

Pada bagian ini akan dijelaskan definisi graf dan definisi dari

beberapa istilah dalam graf yang terkait dengan pembahasan hasil

penelitian dalam tesis ini. Namun, sebelum masuk ke definisi graf, maka

terlebih dahulu akan dijelaskan mengenai batas bawah, batas atas,

suprimum, infimum, maksimum, dan minimum.

Misalkan terdapat himpunan bilangan 𝐴 dan 𝑎 ∈ 𝐴. Bilangan 𝑎

disebut batas atas dari himpunan 𝐴 apabila untuk setiap 𝑥 ∈ 𝐴 berlaku

𝑥 ≤ 𝑎. Selanjutnya 𝑏 ∈ 𝐴 disebut batas bawah himpunan 𝐴 apabila untuk

setiap 𝑥 ∈ 𝐴 berlaku 𝑥 ≥ 𝑏.

8

Kemudian, 𝑠 disebut batas atas terkecil (suprimum) dari 𝐴 jika 𝑠

merupakan batas atas 𝐴 dan jika 𝑎 batas atas 𝐴 maka 𝑠 ≤ 𝑎. Dengan kata

lain, sebuah batas atas 𝑠 dikatakan suprimum dari 𝐴 jika tidak terdapat

bilangan yang lebih kecil dari 𝑠 yang merupakan batas atas dari 𝐴.

Sebaliknya, 𝑡 disebut batas bawah terbesar (infimum) dari 𝐴 jika 𝑡

merupakan batas bawah 𝐴 dan jika 𝑏 batas bawah maka 𝑏 ≤ 𝑡. Atau bisa

dikatakan sebuah batas bawah 𝑡 disebut infimum dari 𝐴 jika tidak ada

bilangan yang lebih besar dari 𝑡 yang merupakan batas bawah dari 𝐴.

Ketika suprimum adalah anggota dari himpunan 𝐴 maka suprimum

tersebut disebut maksimum, begitu pula apabila infimum merupakan

anggota himpunan 𝐴 maka infimum tersebut disebut minimum.

Selanjutnya akan dibahas mengenai beberapa definisi, istilah, dan

notasi yang terkait dengan graf.

Definisi II.1

Graf 𝐺 adalah pasangan himpunan 𝑉 dan 𝐸, dengan 𝑉 himpunan diskrit,

𝑉 ≠ ∅ dan 𝐸 = 𝑢𝑣 𝑢, 𝑣 ∈ 𝑉 }.

Anggota himpunan 𝑉 kadang – kadang disebut titik, simpul, atau

titik simpul. Dan anggota himpunan 𝐸 kadang – kadang disebut sisi, rusuk,

atau garis. Di dalam penulisan tesis ini, anggota 𝑉 disebut titik dan

anggota 𝐸 disebut sisi sehingga 𝑉 disebut himpunan titik dan 𝐸 disebut

himpunan sisi. Notasi sebuah graf adalah 𝐺 = (𝑉, 𝐸). Jika pada 𝐺, 𝑢 ≠ 𝑣

dan 𝑢𝑣 = 𝑣𝑢 maka 𝐺 disebut graf sederhana. Jika 𝑢 = 𝑣, maka sisi 𝑢𝑣

dinamakan gelang atau loop karena berawal dan berakhir pada titik yang

9

sama. Dan jika 𝑢𝑣 ≠ 𝑣𝑢 maka titik 𝑢 dan 𝑣 memiliki sisi paralel. Graf 𝐺

yang memiliki sisi paralel dan loop disebut pseudograf.

Misalkan 𝐺 adalah graf dan 𝑢, 𝑣 ∈ 𝑉(𝐺). Jika 𝑒 = 𝑢𝑣 ∈ 𝐸 𝐺 , maka

titik 𝑢 disebut tetangga dari 𝑣, begitu pula sebaliknya. Sehingga titik 𝑢 dan

𝑣 disebut bertetangga. Lebih jauh, sisi 𝑒 disebut terkait (incident) dengan 𝑢

atau 𝑣. Banyaknya titik dari 𝐺 disebut orde dari 𝐺 yang biasanya

disimbolkan dengan 𝑛 dan banyaknya sisi dari 𝐺 disebut ukuran (𝑠𝑖𝑧𝑒)

yang disimbolkan dengan 𝐸 𝐺 . Suatu graf 𝐺 dengan 𝑛 titik, disebut graf

berlabel orde 𝑛 apabila masing-masing titik pada 𝐺 mempunyai nama

yang berlainan, misalkan 𝑣1, 𝑣2, 𝑣3,…, 𝑣n.

Jika diberikan sebuah graf 𝐺, dimana 𝑉 𝐺 = {𝑎, 𝑏, 𝑐, 𝑑} dan

𝐸 𝐺 = {𝑎𝑏, 𝑏𝑐, 𝑐𝑑, 𝑑𝑎, 𝑎𝑐}, maka graf 𝐺 dapat digambarkan sebagai

berikut.

Pada Gambar II.1, terdapat sisi 𝑎𝑏 ∈ 𝐸(𝐺), sehingga dapat

dikatakan bahwa titik 𝑎 merupakan tetangga dari 𝑏, begitupula sebaliknya.

Karena 𝑏𝑐 dan 𝑐𝑑 terkait dengan titik 𝑐, maka sisi 𝑏𝑐 dan 𝑐𝑑 juga disebut

bertetangga. Graf 𝐺 pada Gambar II.1 merupakan contoh graf sederhana.

Selanjutnya, untuk contoh pseudograf, misalkan diberikan sebuah graf 𝐻,

a b

⋯

c d

Gambar II.1 Graf Sederhana

𝐺 :

10

dengan 𝑉 𝐻 = 𝑎, 𝑏, 𝑐, 𝑑 dan 𝐸 𝐻 = {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8}. Maka

𝐻 dapat digambarkan sebagai berikut.

Definisi II.2

Derajat suatu titik 𝑣𝑖 pada graf 𝐺, yang dilambangkan dengan 𝑑(𝑣𝑖),

adalah banyaknya sisi 𝑒 𝐸(𝐺) yang terkait dengan titik 𝑣𝑖 . (Hasmawati.

1989).

Titik suatu graf yang berderajat nol disebut titik terasing dan graf

yang hanya terdiri dari satu titik disebut graf trivial. Sedangkan titik yang

derajatnya satu disebut titik terminal atau titik ujung. Derajat titik terkecil

dari graf 𝐺 dinotasikan dengan 𝛿(𝐺), atau secara matematis dapat ditulis

𝛿(𝐺) = min 𝑑(𝑣𝑖) 𝑣𝑖𝜖 𝑉(𝐺)}. Sedangkan derajat titik terbesar dari graf 𝐺

dinotasikan dengan Δ 𝐺 atau Δ 𝐺 = max 𝑑(𝑣𝑖) 𝑣𝑖𝜖 𝑉(𝐺)} (Chartrand &

Zhang, 2009).

Teorema II.1

Misalkan 𝐺 adalah sebarang graf berorde 𝑛 dan berukuran 𝑞. Jika

𝑉 𝐺 = 𝑣1, 𝑣2 , … , 𝑣𝑛 , maka

Gambar II.2 Graf H Adalah Pseudograf

𝐻 ∶

a

b

d

e 1

e 2

e 3

e 5 e 6

e 4

e 7

e 8

c

11

𝑑(𝑣𝑖)

𝑛

𝑖=1

= 2𝑞

Misalkan diberikan suatu graf 𝐺, dengan 𝑉 𝐺 = {𝑎, 𝑏, 𝑐, 𝑒, 𝑓, 𝑔} dan

𝐸 𝐺 = {𝑎𝑒, 𝑏𝑒, 𝑐𝑒, 𝑒𝑓}. Maka graf 𝐺 dapat digambarkan sebagai berikut.

Pada Gambar II.3, terdapat empat titik yang berderajat satu yaitu

titik 𝑎, 𝑏, 𝑐, dan 𝑓 atau 𝑑(𝑎) = 𝑑(𝑏) = 𝑑(𝑐) = 𝑑(𝑓) = 1 sebagai titik

terminal. Satu titik berderajat nol yaitu titik 𝑔 atau d(𝑔) = 0 sebagai titik

terasing. Dari sini terlihat bahwa derajat terkecil dalam 𝐺 adalah 0 atau

𝛿(𝐺) = 0. Selanjutnya, titik berderajat empat adalah titik e atau 𝑑(𝑒) = 4.

Jadi ∆(𝐺) = 4.

Akibat II.1

Banyaknya titik berderajat ganjil dalam sebuah graf selalu genap.

Sebagai contoh, perhatikan graf pada Gambar II.3. Titik yang

berderajat ganjil adalah 𝑎, 𝑏, 𝑐, dan 𝑓.

Definisi II.3

Misalkan 𝐺 = (𝑉, 𝐸) adalah sebuah graf. 𝐺1 = (𝑉1, 𝐸1) adalah subgraf dari

𝐺 jika 𝑉1 ⊆ 𝑉(𝐺) dan 𝐸1 ⊆ 𝐸(𝐺). Komplemen dari subgraf 𝐺1 terhadap graf

a

b

c

e f g

1

1

1

4 1

0

Gambar II.3 Derajat Titik Pada Graf 𝐺

𝐺 ∶

12

𝐺 adalah graf 𝐺2 = (𝑉2, 𝐸2) sedemikian sehingga 𝐸2 = 𝐸 − 𝐸1 dan 𝑉2

adalah himpunan titik yang terkait dengan sisi 𝐸2.

Berdasarkan Definisi II.3, subgraf 𝐺1 dikatakan subgraf maksimal

dari 𝐺 jika 𝐺1 memuat semua sisi 𝑥𝑦 ∈ 𝐸(𝐺) untuk semua 𝑥, 𝑦 ∈ 𝑉1. Untuk

sebarang himpunan 𝑆 ⊂ 𝑉(𝐺), subgraf terinduksi oleh 𝑆 dari 𝐺 adalah

subgraf maksimal dari 𝐺 dengan himpunan titik 𝑆 dan dinotasikan dengan

𝐺[𝑆].

2. Pewarnaan dan Operasi Dalam Graf

Dalam teori graf terdapat beberapa aturan dan operasi yang akan

digunakan dalam penentuan batas atas dan batas bawah bilangan

Ramsey graf antara lain sebagai berikut.

a. Pewarnaan Graf

Di dalam teori graf, terdapat konsep yang disebut pewarnaan graf.

Pewarnaan terbagi atas tiga jenis, yaitu pewarnaan titik, pewarnaan sisi,

serta pewarnaan yang tidak umum yaitu pewarnaan – 𝑓. Pewarnaan titik

merupakan pemberian warna pada himpunan titik 𝑉(𝐺) dimana setiap titik

Komplemen Subgraf

a

d

e b

a

c d

e

Graf G

Gambar II.4 Graf, Subgraf, dan Komplemennya

b e

c d Subgraf

a

13

diberi hanya satu warna dan dua titik yang bertetangga diberi warna yang

berbeda.

Suatu graf 𝐺 dikatakan berwarna 𝑘 apabila terdapat 𝑘 warna dalam

pewarnaan graf tersebut. Jumlah warna minimum yang digunakan dalam

pewarnaan titik tersebut dinamakan bilangan kromatik dari 𝐺, yang

dinotasikan dengan 𝜒(𝐺). Perhatikan gambar berikut.

Pada Gambar II.5, diperoleh berturut – turut bahwa jumlah warna

minimum pada 𝑊7 adalah 5, pada 𝑊6 adalah 3, dan pada 𝑆7 adalah 2,

sehingga diperoleh bilangan kromatik 𝜒 𝑊7 = 5, 𝜒 𝑊6 = 3, dan 𝜒 𝑆7 =

2.

Selanjutnya, dikenal pula pewarnaan sisi yaitu memberi warna

pada himpunan sisi 𝐸(𝐺) sedemikian sehingga sisi – sisi yang bertetangga

memiliki warna yang berbeda. Metode pemberian warna pada sisi tidak

berbeda dengan yang dilakukan pada pewarnaan titik.

Selain pewarnaan titik dan sisi, terdapat pula pewarnaan lain yang

tidak umum yaitu pewarnaan – 𝑓 . Pada tahun 1986. Hakim dan Kariv

memperumum konsep pewarnaan sisi sejati menjadi pewarnaan – 𝑓 .

Gambar II.5 Pewarnaan Titik Pada 𝑊7, 𝑊6, dan 𝑆7

14

Definisi II.4

Diketahui suatu graf 𝐺(𝑉, 𝐸) dan fungsi 𝑓 ∶ 𝑉 → ℕ. Pewarnaan – 𝑓 pada

𝐺 merupakan suatu pemetaan 𝑐 ∶ 𝐸 → ℕ sehingga setiap titik 𝑣 ∈ 𝑉

terkait dengan paling banyak 𝑓(𝑣) buah sisi yang berwarna sama.

Berdasarkan definisi tersebut, banyaknya sisi yang terkait dengan

titik 𝑣 berwarna sama paling banyak 𝑓(𝑣). Misalkan terdapat graf 𝐺

dimana sisi yang terkait pada setiap sisinya akan diwarnai paling banyak

2. Maka pewarnaan 𝐺 digambarkan sebagai berikut.

b. Operasi Dalam Graf

Di dalam teori graf dikenal beberapa jenis operasi yang akan

digunakan dalam penelitian ini, antara jumlah dan gabungan graf.

Misalkan 𝐺𝑖 adalah graf dengan himpunan titik simpul 𝑉𝑖 dan himpunan sisi

𝑥𝑖 , 𝑖 = 1,2,3, … . , 𝑘. Graf gabungan 𝐺 =∪𝑖=1𝑘 𝐺𝑖 adalah suatu graf dengan

himpunan titik 𝑉𝑉 =∪𝑖=1𝑘 𝑉𝑖𝑉𝑖 dan himpunan sisi 𝑉𝑋 =∪𝑖=1

𝑘 𝑋𝑖𝑉𝑖

(Hasmawati, 2007). Definisi jumlah dalam graf secara umum belum ada.

Namun pada tahun 1952, Zykov telah mendefinisikan untuk jumlah dua

graf seperti berikut.

𝐺 ∶

Gambar II.6 Pewarnaan – 𝑓 pada graf 𝐺

15

Definisi II.5

Jumlah 𝐺 = 𝐺1 + 𝐺2 adalah suatu graf dengan 𝑉 𝐺 = 𝑉1 ∪ 𝑉2 dan

𝑋 𝐺 = 𝑋1 ∪ 𝑋2 ∪ 𝑢𝑣 : 𝑢 ∈ 𝑉1, 𝑣 ∈ 𝑉2 .

Misalkan terdapat graf 𝑃3 dan 𝐾 4. Jumlah graf 𝑃3 + 𝐾 4 ditunjukkan pada

Gambar II.7 berikut.

Selain jumlah dan gabungan graf, dikenal pula istilah dekomposisi

pada graf. Misalkan 𝐺 adalah graf dan 𝐻𝑖 ⊆ 𝐺 untuk setiap 𝑖. Dekomposisi

graf 𝐺 adalah himpunan {𝐻1, 𝐻2, … , 𝐻𝑘} sedemikian sehingga 𝐸 𝐺 =

𝐸(𝐻𝑖)𝑘𝑖=1 , 𝑉 𝐻𝑖 = 𝑉(𝐻𝑗 ) dan 𝐸 𝐻𝑖 ∩ 𝐸 𝐻𝑗 = ∅ untuk setiap 𝑖 ≠ 𝑗 dan

𝑖, 𝑗 ∈ {1,2, … , 𝑘}, dengan 𝐸(𝐻𝑖) ≠ ∅. Dekomposisi dari graf 𝐺 dinyatakan

dengan 𝐺 = 𝐻1⨁𝐻2 ⨁…⨁𝐻𝑘 . Sebagai contoh 𝐾𝑚 = 𝐹𝑚 ⨁ 𝐹𝑚 .

3. Jenis – Jenis Graf

Sebelum membahas tentang jenis – jenis graf, perlu diketahui

beberapa definisi dari beberapa istilah berikut, seperti jalan (walk), lintasan

(path), jalur (trail), siklus (cycle).

Definisi II.6

Jalan 𝑊 pada graf 𝐺 dengan panjang 𝑘 adalah barisan barisan

berselang-seling titik dan sisi, yaitu 𝑣0 , 𝑒0, 𝑣1, 𝑒1, 𝑣2, 𝑒2, … , 𝑒𝑘−1, 𝑣𝑘 dengan

Gambar II.7 (a) Graf 𝑃3 ∪ 𝐾 4 dan (b) Jumlah graf 𝑃3 + 𝐾 4

𝑃3 ∶

𝐾 4 :

: (a) (b)

16

𝑒𝑖 = 𝑣𝑖𝑣𝑖+1, 𝑖 = 0,1,2, … , 𝑘 − 1.

Dalam hal ini, 𝑣0 disebut titik awal dan 𝑣𝑘 disebut titik akhir. Sebuah

jalan disebut sebagai jalan tertutup apabila 𝑣0 = 𝑣𝑘 . Jalan 𝑊 disebut

lintasan (path) bila semua titiknya berbeda. Sedangkan jika setiap sisinya

yang berbeda maka jalan tersebut dinamakan jalur (trail). Jalur yang

berawal dan berakhir pada titik yang sama disebut sirkuit dengan derajat

setiap titik adalah 2.

a. Graf Siklus

Sirkuit yang mengandung titik yang berlainan (kecuali titik awal dan

akhir) disebut siklus (cycle). Graf siklus adalah graf terhubung yang setiap

titiknya berderajat dua. Graf siklus berorde 𝑛 dilambangkan dengan 𝐶𝑛 .

Pada Gambar II.8 berikut, berturut-turut adalah graf siklus 𝐶3, 𝐶4, 𝐶5, dan

𝐶6.

Panjang siklus dapat dilihat dari banyaknya sisi dalam siklus

tersebut. Graf yang tidak mengandung siklus disebut asiklik.

b. Graf Lengkap

Jenis graf lainnya adalah graf lengkap. Graf lengkap ialah graf

sederhana yang setiap titiknya mempunyai sisi ke semua titik lainnya. Graf

lengkap dengan 𝑛 buah titik dilambangkan dengan 𝐾𝑛 . Jumlah sisi pada

𝐶3 𝐶4 𝐶5 𝐶6

Gambar II.8 Graf Siklus

17

graf lengkap yang terdiri dari 𝑛 buah titik adalah 𝑛 𝑛 – 1

2. Untuk 𝑛 = 3, maka

graf lengkap 𝐾3 juga dapat dikatakan sebagai graf siklus 𝐶3.

c. Graf Bipartit

Graf 𝐺 yang himpunan titiknya dapat dipisah menjadi dua himpunan

bagian 𝑉1 dan 𝑉2, sedemikian sehingga setiap sisi pada 𝐺 menghubungkan

sebuah titik di 𝑉1 ke sebuah titik di 𝑉2 disebut graf bipartit.

Salah satu contoh graf bipartit adalah graf siklus 𝐶6. Graf 𝐶6 dapat dilabeli

sebagai berikut, 𝑉 𝐶6 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓} dan 𝐸 𝐶6 = {𝑎𝑏, 𝑏𝑐, 𝑐𝑑, 𝑑𝑒, 𝑒𝑓, 𝑓𝑎}.

Himpunan titik 𝑉(𝐶6) dapat dipisah menjadi 𝑉1 = {𝑎, 𝑐, 𝑒} dan 𝑉2 = {𝑏, 𝑑, 𝑓}.

Graf bipartit lengkap adalah graf bipartit dimana setiap titik pada 𝑉1

terhubung ke setiap titik pada 𝑉2 (Wilson, 1999). Jika banyak titik pada 𝑉1

sama dengan 𝑉2, maka graf bipartit dilambangkan dengan 𝐾𝑚 ,𝑚 dimana 𝑚

Gambar II.10 Graf Bipartit

𝐺:

𝐶6 ∶ c

d e

f

Gambar II.11 Graf Siklus 𝐶6

a b

𝐾1 𝐾2 𝐾3 𝐾4 𝐾5 𝐾6

Gambar II.9 Graf Lengkap

18

adalah banyak titik 𝑉1 dan 𝑉2. Sedangkan apabila banyaknya titik pada 𝑉1

berbeda dengan 𝑉2, maka graf bipartit dilambangkan dengan 𝐾𝑚 ,𝑛 dimana

𝑚 adalah banyak titik di 𝑉1 dan 𝑛 adalah banyak titik di 𝑉2.

d. Graf k – Partit

Misalkan 𝑉1, 𝑉2, … , 𝑉𝑘 adalah beberapa himpunan bagian dari

himpunan titik 𝑉 𝐺 pada suatu graf 𝐺. Untuk setiap 𝑖, himpunan 𝑉𝑖 disebut

partisi dari 𝑉 𝐺 jika 𝑉𝑖 ≠ ∅ dan 𝑉 𝐺 = 𝑉i𝑘𝑖=1 serta 𝑉𝑖 ∩ 𝑉𝑗 = ∅ dengan

𝑖 ≠ 𝑗. Graf 𝐺 disebut 𝑘-partit jika 𝑉 𝐺 dapat di partisi ke dalam 𝑘 partisi

himpunan bebas 𝑉1, 𝑉2, … , 𝑉𝑘 . Graf 𝑘-partit untuk 𝑘 ≥ 2 dengan 𝑉𝑖 = 𝑛𝑖

disebut graf multipartit, dinotasikan dengan 𝐵𝑛1 ,𝑛2 ,…,𝑛𝑘. Khusus untuk 𝐵𝑛1 ,𝑛2

grafnya disebut graf bipartit.

Misalkan terdapat suatu graf multipartit 𝐵𝑛1 ,𝑛2 ,…,𝑛𝑖, jika 𝑛1 = 𝑛2 =

⋯ = 𝑛𝑖 sebanyak 𝑛, maka 𝐵𝑛1 ,𝑛2 ,…,𝑛𝑖 ditulis 𝐵𝑛𝑖×𝑛 . Graf multipartit 𝐵𝑛1 ,𝑛2 ,…,𝑛𝑘

disebut graf multipartit lengkap jika setiap titik di setiap partisi bertetangga

dengan semua titik di partisi-partisi lainnya. Graf multipartit lengkap

dinotasikan dengan 𝐾𝑛1 ,𝑛2 ,…,𝑛𝑘. Graf 𝐾𝑛1 ,𝑛2 ,…,𝑛𝑘

multipartit lengkap

dikatakan seimbang jika 𝑉𝑖 = 𝑡 untuk setiap 𝑖 dan dinotasikan dengan

𝐾𝑘×𝑡 . Perhatikan Gambar II.13 berikut.

𝐾1,3 𝐾2,3 𝐾3,3 𝐾4,3

Gambar II.12 Graf Bipartit Lengkap

19

e. Graf Euler

Jalur pada graf 𝐺 disebut jalur Euler apabila melewati setiap sisi di

𝐺 tepat satu kali. Jika suatu jalur Euler berawal dan berakhir pada titik

yang sama (tertutup), maka jalur itu disebut sirkuit Euler. Suatu graf yang

memiliki sirkuit Euler disebut graf Euler. Sedangkan graf yang hanya

memiliki jalur Euler disebut graf semi Euler.

Gambar II.14 Jalur Euler 𝑎𝑏𝑑𝑐𝑏𝑓𝑒𝑑𝑓 Pada Graf 𝑀 dan

Sirkuit Euler 𝑢𝑟𝑠𝑡𝑟𝑞𝑝𝑢 Pada Graf 𝑁

𝑀 ∶ 𝑁 ∶ a

b

c

d

e f p q

r s

t

u

Gambar II.13 (a) Graf Bipartit (b) Graf Multipartit (c) Graf multipartit Lengkap (d) Graf Multipartit Seimbang

(b) (a)

(c) (d)

20

Dari Gambar II.14 tersebut, dapat dilihat bahwa 𝑀 merupakan graf

yang memuat jalur Euler, yaitu 𝑎𝑏𝑑𝑐𝑏𝑓𝑒𝑑𝑓 karena melewati semua sisi

yang berlainan. Sedangkan pada graf 𝑁, dapat dilihat bahwa graf tersebut

merupakan sirkuit Euler karena melewati semua sisi yang berlainan dan

kembali ke titik awal, yaitu 𝑢𝑟𝑠𝑡𝑟𝑞𝑝𝑢.

Teorema II.2

Misalkan 𝐺 merupakan graf terhubung tak trivial. 𝐺 merupakan graf Euler

jika dan hanya jika setiap titik pada 𝐺 berderajat genap.

Teorema II.3

Suatu graf terhubung 𝐺 merupakan graf Euler jika dan hanya jika setiap

sisi pada 𝐺 berada pada siklus ganjil.

f. Graf Hamilton

Selain graf Euler, graf yang memiliki sifat yang berbeda dengan

graf-graf lainnya yaitu graf Hamilton.

Definisi II.6

Lintasan Hamilton adalah lintasan yang melalui setiap titik di dalam graf

tepat satu kali. Bila lintasan tersebut kembali ke titik awal membentuk

siklus, maka siklus tersebut dinamakan siklus Hamilton.

Graf 𝐺 disebut graf Hamilton jika 𝐺 memuat siklus Hamilton. Graf 𝐻 berikut

adalah contoh graf Hamilton karena memiliki siklus Hamilton 𝐶20.

21

Pada Gambar II.15, siklus Hamilton 𝐶20 yang termuat di dalamnya

yaitu siklus 𝑎𝑏𝑐𝑕𝑙𝑔𝑘𝑓𝑜𝑗𝑛𝑠𝑡𝑝𝑞𝑟𝑚𝑖𝑑𝑒𝑎. Suatu graf non Hamilton dikatakan

semi-Hamilton jika terdapat sebuah lintasan yang melewati setiap titik.

Suatu graf sederhana dapat dikatakan sebagai graf Hamilton

apabila memenuhi sifat pada teorema berikut.

Teorema II.4

Misalkan 𝐺 merupakan graf sederhana dengan orde 𝑛 ≥ 3. Jika

𝑑 𝑢 + 𝑑 𝑣 ≥ 𝑛,

untuk setiap pasangan titik tak bertetangga 𝑢, 𝑣 pada 𝐺, maka 𝐺 adalah

graf Hamilton.

Dari Teorema II.4 dapat diketahui bahwa tidak semua graf

sederhana juga merupakan graf Hamilton. Namun, dengan menggunakan

teorema tersebut, suatu graf dapat diidentifikasi, apakah termasuk graf

Hamilton atau bukan. Jika memenuhi 𝑑 𝑢 + 𝑑𝑒 𝑣 ≥ 𝑛, untuk setiap

Gambar II.16 Graf Semi-Hamilton 𝐺

𝐺 ∶

Gambar II.15 Graf Hamilton Dengan Siklus 𝑎𝑏𝑐𝑕𝑙𝑔𝑘𝑓𝑜𝑗𝑛𝑠𝑡𝑝𝑞𝑟𝑚𝑖𝑑𝑒𝑎

b

c d

e

f

g

h i

j k

l

m

n

o

p

q r

s

t

a

H :

22

pasangan titik tak bertetangga 𝑢, 𝑣 pada 𝐺, maka graf tersebut merupakan

graf Hamilton. Namun, hal itu belum tentu berlaku sebaliknya.

g. Graf Pohon

Suatu graf terhubung berorde 𝑛 yang tidak memuat siklus disebut

pohon atau biasa disimbolkan dengan 𝑇𝑛 .

h. Graf Bintang

Suatu pohon yang terdiri atas satu titik berderajat 𝑛 − 1 dan titik

lainnya berderajat satu disebut graf bintang dengan 𝑛 titik. Graf bintang

biasanya disimbolkan dengan 𝑆𝑛 . Selain itu, graf bintang juga dapat

didefinisikan sebagai suatu graf bipartit komplit 𝐾1,𝑡.

i. Graf Roda

Suatu graf yang terdiri atas 𝑛 + 1 titik dimana 𝑛 titik berderajat 3

dan 1 titik berderajat 𝑛 disebut graf roda, atau biasa disimbolkan dengan

𝑊𝑛 .

𝑇13:

Gambar II.17 Graf Pohon

𝑆9 ∶

Gambar II.18 Graf Bintang

23

j. Graf Pansiklik

Selain graf khusus yang telah disebutkan di atas, juga terdapat graf

pansiklik. Dalam pengertian graf pansiklik terdapat istilah girth dan

cirmcumference. Panjang siklus terbesar pada suatu graf 𝐺 disebut

circumference, dinotasikan dengan 𝑐(𝐺), sedangkan panjang siklus

terkecil disebut girth, dinotasikan dengan 𝑔(𝐺).

Sebuah graf 𝐺 yang berorde 𝑛 ≥ 3 disebut graf pansiklik (pancyclic)

jika 𝐺 memuat semua siklus dengan panjang dari 3 sampai 𝑛. Dan disebut

graf pansiklik lemah (weakly pancyclic) jika 𝐺 memuat siklus 𝐶𝑙 , untuk

𝑔(𝐺) ≤ 𝑙 ≤ 𝑐(𝐺). Berikut contoh graf yang termasuk graf pansiklik dan

pansiklik lemah.

Pada Gambar II.20 dapat dilihat bahwa 𝐺1 merupakan jenis graf

pansiklik yang memuat semua siklus 𝐶𝑙 dengan panjang 3 ≤ 𝑙 ≤ 5 dan 𝐺2

𝑊8 ∶

Gambar II.19 Graf Roda

𝑎

Gambar II.20 𝐺1Graf Pansiklik dan 𝐺2 Graf Pansiklik Lemah

𝑏 𝑐

𝑑 𝑒

𝐺1 ∶

𝑡

𝑢

𝑣

𝑤

𝐺2 ∶ 𝑥

𝑦

𝑧

24

adalah graf pansiklik lemah yang memuat semua siklus terkecil hingga

siklus terbesar 𝐶𝑙 dimana 3 ≤ 𝑙 ≤ 6.

Pada Gambar II.21, graf 𝐻 adalah graf non pansiklik karena hanya

memuat siklus 𝐶3, 𝐶6 dan 𝐶7. Dengan kata lain, graf 𝐻 tidak memuat

semua siklus 𝐶𝑙 , dimana 3 ≤ 𝑙 ≤ 7.

4. Beberapa Teorema, Lemma, dan Sifat yang Terkait Batas Bawah

dan Batas Atas Bilangan Ramsey

Pada subbab ini akan diberikan beberapa teorema dan lemma yang

akan terkait dengan masalah penentuan batas bawah dan batas atas

bilangan Ramsey graf. Selain itu juga akan dijelaskan beberapa sifat yang

akan digunakan dalam penentuan bilangan Ramsey.

a. Beberapa Teorema dan Lemma Yang Terkait Bilangan

Ramsey

Teorema dan Lemma yang terkait dengan penentuan batas atas

dan batas bawah bilangan Ramsey, antara lain sebagai berikut.

Gambar II.21 Graf Non Pansiklik

𝐻 ∶

25

Teorema II.5

Graf 𝐺 adalah graf bipartit jika dan hanya jika setiap siklus pada 𝐺 memiliki

panjang genap.

Teorema II.6

Jika 𝐺 adalah graf berorde 𝑛 dan berukuran 𝑛2

4 maka 𝐺 memuat sebuah

siklus ganjil atau 𝐺 = 𝐾𝑛

2,𝑛

2.

Lemma II.1 Lemma (Bondy, 1971)

Misalkan 𝐺 adalah graf berorde 𝑛. Jika 𝛿 𝐺 ≥𝑛

2, maka 𝐺 adalah pansiklik

atau 𝐺 = 𝐾𝑛

2,𝑛

2 untuk 𝑛 genap.

Lemma Bondy merupakan lemma yang digunakan untuk menjamin

keberadaan semua siklus. Salah satu contoh graf yang subgraf

pembangunannya adalah siklus yaitu graf roda, maka untuk mengetahui

keberadaan roda maka dapat pula digunakan Lemma II.2 tersebut. Berikut

disajikan contoh yang menerapkan Lemma II.2.

Contoh II.1

Misal terdapat suatu graf 𝐺 seperti berikut.

Pada Gambar II.22 dapat diketahui bahwa 𝛿 𝐺 = 3 ≥𝑛

2, maka

akan ditunjukkan bahwa 𝐺 pansiklik atau 𝐺 merupakan graf bipartit 𝐾3,3.

Karena pada graf 𝐺 tidak memuat siklus dengan panjang 3 dan 5, maka 𝐺

𝐺 ∶

Gambar II.22 Graf 𝐺

26

bukan graf pansiklik. Selanjutnya dapat dilihat bahwa derajat setiap titik

adalah 3. Oleh karena itu derajat terkecilnya juga 3. Sehingga

berdasarkan Lemma II.2, graf 𝐺 merupakan graf bipartit..

Selanjutnya, selain Lemma Bondy terdapat pula Lemma Brandt

yang berkaitan dengan graf pansiklik.

Lemma II.2 (Brandt)

Setiap graf non bipartit 𝐺 berorde 𝑛 dengan 𝛿 𝐺 ≥𝑛+2

3 adalah pansiklik

lemah dengan 𝑔 𝐺 = 3 atau 4.

Contoh II.2

Diberikan suatu graf 𝐻 sebagai berikut.

Pada Gambar II.23 dapat dilihat bahwa 𝐻 merupakan graf non bipartit

berorde 7 yang derajat titik terkecilnya adalah 3. Karena memenuhi

𝛿 𝐺 ≥𝑛+2

3 maka 𝐻 merupakan pansiklik lemah dimana 𝐻 memuat siklus

dengan panjang yang terkecil yaitu 3 hingga yang terbesar yaitu 6.

Lemma II.3 (Dirac, 1952)

Misalkan 𝐺 merupakan graf denga𝑛 titik 𝑛 ≥ 3 dan 𝛿 𝐺 = 𝛿. Jika 𝐺

adalah graf terhubung-2, maka 𝑐 𝐺 ≥ min 2𝛿, 𝐺 .

𝐻 ∶

Gambar II.23 Graf Non Bipartit 𝐻

27

Selain beberapa teorema dan lemma tersebut terdapat beberapa

kajian tentang sifat graf yang akan digunakan pada bab selanjutnya.

b. Keterhubungan Graf dan Himpunan Bebas

Pada subbab ini akan dibahas mengenai salah satu topik penting

yang berkaitan dengan bilangan Ramsey, yaitu keterhubungan graf dan

himpunan bebas. Graf 𝐺 dikatakan terhubung (connected) jika untuk

setiap dua titik 𝑢 dan 𝑣 pada graf tersebut terdapat suatu lintasan yang

memuat 𝑢 dan 𝑣. Jika 𝑒 adalah suatu sisi dalam graf 𝐺, maka 𝐺 – 𝑒 adalah

subgraf dari 𝐺 yang mempunyai banyak titik sama dengan 𝐺 dan

mempunyai banyak sisi seperti 𝐺 terkecuali sebuah sisi 𝑒 .

Jika 𝑣 adalah suatu titik dalam graf 𝐺 yang paling sedikit

mempunyai dua titik, maka 𝐺 − 𝑣 adalah subgraf dari 𝐺 yang himpunan

titiknya memuat semua titik dari 𝐺 terkecuali 𝑣 dan himpunan sisi terdiri

atas semua sisi di 𝐺 terkecuali sisi-sisi yang terkait dengan 𝑣.

Misalkan 𝐺(𝑉, 𝐸) adalah graf sebarang dan 𝑘 bilangan bulat non

negatif. Graf 𝐺 disebut terhubung-k (k-connected) jika 𝐺 > 𝑘 dan 𝐺 − 𝑋

terhubung untuk setiap 𝑋 ⊆ 𝑉 dengan 𝑋 < 𝑘.

a

b

c d

e1

e2

e3 e4

G :

a

e1

b d

G - c :

a

b

c e1

e2

e3 d

G – e4 :

Gambar II.24 Graf Terhubung 𝐺 dan Graf Tak Terhubung 𝐺 − 𝑐 dan 𝐺 − 𝑒4

28

Suatu titik 𝑣 di dalam graf terhubung 𝐺 disebut titik pemotong (cut-

vertex) jika 𝐺 – 𝑣 tak terhubung. Suatu titik pemotong dengan kardinalitas

minimum pada 𝐺 disebut titik pemotong minimum (minimum vertex-cut)

pada 𝐺 dan kardinalitasnya disebut keterhubungan titik pada 𝐺 dan

disimbolkan dengan 𝜅(𝐺).

Suatu graf komplit 𝐾𝑛 tidak dapat menjadi suatu graf tak terhubung

dengan menghilangkan titik apapun, namun suatu graf trivial dapat

dihasilkan setelah menghilangkan 𝑛 − 1 titik, sehingga keterhubungan

pada graf lengkap berorde 𝑛 didefinisikan sebagai sebagai 𝑛 − 1 atau

𝜅 𝐾𝑛 = 𝑛 − 1. Kemudian secara umum, keterhubungan 𝜅(𝐺) pada graf 𝐺

merupakan bilangan terkecil banyaknya titik yang dihilangkan sehingga

penghilangan titik – titik tersebut pada 𝐺 menghasilkan suatu graf tak

terhubung atau suatu graf trivial. Selanjutnya, untuk setiap graf 𝐺 berorde

𝑛,

0 ≤ 𝜅 𝐺 ≤ 𝑛 − 1.

Suatu graf 𝐺 memiliki keterhubungan 0 jika dan hanya jika 𝐺 = 𝐾1

atau 𝐺 tak terhubung, selanjutnya graf 𝐺 memiliki keterhubungan 1 jika

dan hanya jika 𝐺 = 𝐾2.

Sisi 𝑒 di dalam graf terhubung 𝐺 disebut suatu jembatan (bridge)

jika 𝐺 – 𝑒 tak terhubung. Sisi 𝑒4 di dalam Gambar II.24 merupakan suatu

jembatan.

Definisi II.7

Misalkan 𝐺 merupakan suatu graf terhubung, dimana 𝑢, 𝑣 ∈ 𝑉(𝐺). Jarak

29

dari 𝑢 ke 𝑣 di 𝐺, ditulis 𝑑(𝑢, 𝑣), adalah panjang lintasan terpendek dari 𝑢

ke 𝑣 di 𝐺.

Eksentrisitas 𝑒(𝑣) pada suatu titik 𝑣 adalah nilai 𝑚𝑎𝑘𝑠𝑢∈𝑉 𝐺 d(𝑢, 𝑣),

atau 𝑒(𝑣) merupakan jarak antara 𝑣 dengan sebuah titik terjauh dari 𝑣.

Radius, atau ditulis 𝑟𝑎𝑑 𝐺 pada 𝐺 merupakan eksentrisitas minimum dari

titik pada 𝐺, sementara diameter, atau ditulis 𝑑𝑖𝑎𝑚 𝐺 , merupakan

eksentrisitas maksimum. Dengan kata lain, 𝑑𝑖𝑎𝑚(𝐺) merupakan jarak

terbesar dari setiap dua titik pada 𝐺.

Definisi II.8

Sebuah titik 𝑣 dikatakan titik pusat (central vertex) jika 𝑒 𝑣 = 𝑟𝑎𝑑(𝐺).

Selain beberapa istilah tersebut, pada graf terhubung juga dikenal

istilah berat dan pusat berat (centroid). Berat pada suatu titik 𝑣 adalah

jumlah maksimum sisi dalam setiap cabang di 𝑣. (Bondy & Murty, 1976)

Pada Gambar II.25, berat titik 𝑏, 𝑕, dan 𝑓 adalah 8 karena jumlah

maksimum sisinya adalah 8. Sedangkan berat titik 𝑔 adalah 3.

Definisi II.9

Titik 𝑣 disebut pusat berat jika 𝑣 memiliki berat minimum.

Berdasarkan Definisi II.9, titik 𝑔 pada Gambar II.25 disebut pusat

berat karena memiliki berat minimum.

8

8 3 8 𝐺 :

𝑎 𝑏

𝑐 𝑑

𝑒 𝑓 𝑔 𝑕

𝑖

𝑗 𝑘

Gambar II.25 Berat titik pada graf

𝐺

30

Selanjutnya, misalkan terdapat suatu graf berorde 𝑛 yaitu 𝐺(𝑉, 𝐸)

dan 𝑋 ⊆ 𝑉. Himpunan 𝑋 disebut himpunan bebas jika untuk setiap dua titik

𝑥, 𝑦 ∈ 𝑋 berlaku 𝑥, 𝑦 ∉ 𝐸(𝐺). Misalkan 𝑌 merupakan suatu himpunan

bebas dari 𝐺. Jika untuk setiap himpunan bebas 𝑋 dari 𝐺 berlaku 𝑋 ≤

|𝑌|, maka 𝑌 disebut himpunan bebas terbesar dari 𝐺. Kardinalitas

himpunan bebas terbesar dari 𝐺 dinotasikan dengan 𝛼(𝐺). Sebagai

contoh 𝛼 𝑆𝑛 = 𝑛 − 1.

5. Bilangan Ramsey

Pada tahun 1935, perkembangan teori graf semakin pesat, hal

tersebut ditandai dengan penemuan yang dilakukan oleh Erdos dan

Szekeres yang pada saat itu mengkaji tentang teori Ramsey dan

kemudian mengaplikasikannya ke dalam teori graf. Kajian tersebut

dinamakan sebagai teori Ramsey klasik, dimana untuk kasus dua warna

dinyatakan sebagai berikut.

Definisi II.10

Diberikan sebarang dua graf 𝐺 dan 𝐻, bilangan Ramsey graf dua warna

𝑅(𝐺, 𝐻) adalah bilangan asli terkecil 𝑚 sedemikian sehingga untuk setiap

pewarnaan dengan dua warna pada setiap sisi graf lengkap 𝐾𝑚

katakanlah merah atau biru, maka 𝐾𝑚 akan selalu memuat subgraf merah

yang isomorf dengan 𝐺 atau subgraf biru yang isomorf dengan 𝐻.

Contoh II.3

Berdasarkan Baskoro dkk (2002) telah diketahui bahwa 𝑅 𝑆𝑛 , 𝑊5 = 3𝑛 −

31

2 untuk 𝑛 ≥ 4, misalkan ambil 𝑛 = 4 maka 𝑅 𝑆4, 𝑊5 = 10. Akan

ditunjukkan bilangan Ramsey untuk graf bintang berorde 4 terhadap graf

roda berorde 5 atau 𝑅(𝑆4, 𝑊5). Ambil suatu graf lengkap berorde 10 atau

sebut 𝐾10. Maka pewarnaan dengan dua warna pada setiap sisi graf

lengkap 𝐾10 katakanlah merah dan biru, maka 𝐾10 akan selalu memuat

subgraf merah yang isomorf dengan 𝑆4 atau subgraf biru yang isomorf

dengan 𝑊5.

Berdasarkan Gambar II.26, dapat dilihat bahwa setiap titik pada

subgraf merah 𝐾10 berderajat 2 sehingga tidak ditemukan 𝑆4 yang isomorf

dengan subgraf berwarna merah. Namun, pada subgraf berwarna biru

pada 𝐾10 ternyata dapat ditemukan 𝑊5 dengan 𝑢 sebagai titik pusatnya

dan 1,2,3,4, dan 5 sebagai titik pada siklus 𝐶5 yang terkait dengan 𝑢.

Pewarnaan dua warna, yaitu merah dan biru, pada semua sisi graf

lengkap 𝐾𝑚 akan menghasilkan dua subgraf, yaitu subgraf berwarna

merah dan subgraf berwarna biru. Salah satu dari subgraf tersebut,

misalkan subgraf berwarna merah, merupakan subgraf pembangun 𝐾𝑚

dan subgraf berwarna biru adalah komplemen dari subgraf pembangun

𝑢 1

2

3

4

5

Gambar II.26 Pewarnaan Pada Graf 𝐾10

𝐾10 ∶

32

tersebut. Dengan memanfaatkan konsep dekomposisi graf, maka definisi

bilangan Ramsey graf dapat dituliskan sebagai berikut.

Definisi II.11

Diberikan sebarang dua graf 𝐺 dan 𝐻, bilangan Ramsey graf

𝑅(𝐺, 𝐻) adalah bulat terkecil 𝑚 sedemikian sehingga untuk setiap graf 𝐹

berorde 𝑚 memenuhi sifat berikut: 𝐹 memuat graf 𝐺 atau 𝐹 memuat 𝐻.

Perhatikan kembali Contoh II.3. Berdasarkan Gambar II.26

sebelumnya ternyata subgraf berwarna merah merupakan graf 𝐹 yang

berorde 10 dan subgraf berwarna biru merupakan komplemen dari 𝐹 (𝐹 )

yang memuat 𝑊5.

𝐹 ⊉ 𝑆4

𝐹 ⊇ 𝑊5

𝑊5

Selanjutnya, sebelum menyajikan teorema batas bawah dari

Chvátal dan Harary, akan disajikan terlebih dahulu definisi graf kritis

(good-gaph).

Definisi II.12

Diberikan graf 𝐺 dan 𝐻. Suatu graf 𝐹 disebut graf kritis untuk 𝐺 dan 𝐻, jika

𝐹 tidak memuat 𝐺 dan 𝐹 tidak memuat 𝐻.

𝑢 1

2

3

4

5

𝑢

1

2

3 4

5

Gambar II.27 Identifikasi 𝑆4 pada 𝐹 dan 𝑊5 pada 𝐹

33

Kardinalitas graf kritis untuk sepasang graf 𝐺 dan 𝐻 merupakan

dasar untuk menemukan batas bawah bilangan Ramsey 𝑅(𝐺, 𝐻). Berikut

teorema yang diberikan oleh Chvátal dan Harary.

Teorema II.7 (Chvátal dan Harary, 1972)

Misalkan 𝜒(𝐻) adalah bilangan kromatik graf 𝐻 dan 𝐶(𝐺) adalah

banyaknya titik pada komponen terbesar graf 𝐺, maka 𝑅 𝐺, 𝐻 ≥

𝜒 𝐻 − 1 𝐶 𝐺 − 1 + 1.

Bukti

Pandang graf 𝐹 ≔ 𝜒 𝐻 − 1 𝐾𝐶 𝐺 −1. Graf 𝐹 terdiri atas 𝜒 𝐻 − 1 graf

lengkap dengan kardinalitas masing-masing 𝐶 𝐺 − 1. Dengan demikian,

𝐹 tidak memuat graf terhubung yang berorde paling sedikit 𝐶 𝐺 .

Akibatnya, 𝐹 tidak memuat 𝐺. Komplemen dari 𝐹 yaitu 𝐹 adalah graf

multipartit 𝐾 𝜒 𝐻 −1 (𝐶 𝐺 −1). Jelas 𝐾 𝜒 𝐻 −1 (𝐶 𝐺 −1) terdiri dari 𝜒 𝐻 − 1

partisi, sehingga tidak memuat graf dengan bilangan kromatik 𝜒 𝐻 . Jadi,

𝐹 tidak memuat 𝐻. Karenanya, diperoleh 𝑅 𝐺, 𝐻 ≥ 𝐹 + 1 = 𝜒 𝐻 −

1 𝐶 𝐺 − 1 + 1. ∎

Selanjutnya, definisi batas atas bilangan Ramsey 𝑅(𝐺, 𝐻) telah

diberikan sebagai berikut.

Definisi II.13

Suatu bilangan asli 𝑛 disebut batas atas bilangan Ramsey 𝑅(𝐺, 𝐻) apabila

sembarang graf dengan orde 𝑛 akan selalu memuat 𝐺 atau

komplemennya memuat 𝐻.

34

Perkembangan Bilangan Ramsey Graf

Kajian mengenai bilangan Ramsey semakin lama semakin

berkembang untuk beberapa jenis graf. Berikut tabel yang menyajikan

hasil kajian mengenai bilangan Ramsey.

Tabel 1. Hasil Penelitian Bilangan Ramsey Graf

Tahun

Peneliti

Hasil Penelitian

1967

Gerencser

dan

Gyarfas

𝑅 𝑃𝑛 , 𝑃𝑚 = 𝑛 + 𝑚

2 − 1 untuk 𝑛 ≥ 𝑚 ≥ 2

1973 Lawrence 𝑅 𝑆16 , 𝐾2,2 = 20

1974 Faudree

dkk 𝑅 𝑃𝑛 , 𝐶𝑚 =

2𝑛 − 1, untuk 𝑚 ganjil dan 𝑛 ≥ 𝑚 − 1 ≥ 2

𝑛 + 𝑚

2 − 1, untuk 𝑚 genap dan 𝑛 ≥ 𝑚 − 1 ≥ 3

1974 Burr 𝑅 𝑆𝑛+1 , 𝑇𝑚 = 𝑚 + 𝑛 − 1, untuk 𝑛 ≡ 1 (mod 𝑚 − 1)

1974 Cockayne 𝑅 𝑆𝑛+1 , 𝑇𝑚 = 𝑚 + 𝑛 − 2, untuk 𝑛 dan m ya𝑛𝑔 𝑙𝑎𝑖𝑛

1975 Parsons 𝑅 𝑆8 , 𝐾2,3 = 13

2001

Surahmat

dan

Baskoro

𝑅 𝑃𝑛 , 𝑊𝑚 = 2𝑛 − 1, untuk 𝑚 ≥ 4 genap dan 𝑛 ≥

𝑚

2 𝑚 − 2

3𝑛 − 2, untuk 𝑚 ≥ 5 ganjil dan 𝑛 ≥𝑚 − 1

2(𝑚 − 3)

2002 Baskoro

dkk

𝑅 𝑆𝑛 , 𝑊4 = 2𝑛 − 1, untuk 𝑛 ganjil 2𝑛 + 1, untuk 𝑛 genap

𝑅 𝑆𝑛 , 𝑊5 = 3𝑛 − 2

2002 Baskoro

dkk 𝑅 𝑇𝑛 , 𝑊𝑚 =

2𝑛 − 1, untuk 𝑚 = 43𝑛 − 2, untuk 𝑚 = 5

2003 Hasmawati 𝑅 𝑆𝑛 , 𝑊𝑚 = 𝑚 + 𝑛 − 2, untuk 𝑚 genap dan 𝑛 ganjil

2004 Chen dkk 𝑅 𝑆𝑛 , 𝑊6 = 2𝑛 + 1, untuk 𝑛 ≥ 3

𝑅 𝑆𝑛 , 𝑊𝑚 = 3𝑛 − 2, untuk 𝑚 ganjil dan 𝑛 ≥ 𝑚 − 1 ≥ 2

2004 Zhang 𝑅 𝑆𝑛 , 𝑊8 = 2𝑛 + 1, untuk n ganjil2𝑛 + 2, untuk n genap

2004 Rosyida

𝑅 𝑆4 , 𝐾𝑡 ,𝑚 = 𝑡 + 𝑚 + 2 untuk 𝑡, 𝑚 ≥ 2

𝑅 𝑆5 , 𝐾2,𝑚 = 𝑚 + 5, untuk 𝑚 genap𝑚 + 6, untuk 𝑚 ganjil

35

Tahun Peneliti Hasil Penelitian

2005 Korolova 𝑅 𝑆𝑛 , 𝑊𝑚 = 3𝑛 − 2, jika 𝑛 = 𝑚, 𝑚 + 1 atau 𝑚 + 2

𝑅 𝑆𝑛 , 𝑊𝑚 ≥ 2𝑛 + 1, untuk 𝑚 genap dan 𝑛 ≥ 𝑚 ≥ 6

2006

Surahmat 𝑅 𝐶𝑛 , 𝑊𝑚 = 2𝑛 − 1, untuk 𝑚 genap dan 𝑛 ≥

5𝑚

2− 1

3𝑛 − 2, untuk 𝑚 ≥ 5 ganjil dan 𝑛 >5𝑚 − 9

2

2006 Lortz 𝑅 𝐾2,2 , 𝐾3,𝑚 = 11 untuk 𝑚 = 3,4

𝑅 𝐾2,2 , 𝐾3,6 = 15, 𝑅 𝐾2,2 , 𝐾3,7 = 16, 𝑅 𝐾2,2, 𝐾3,8 = 17, 𝑅 𝐾2,2, 𝐾3,9 = 20

2007 Hasmawati 𝑅 𝑆𝑛 , 𝑊𝑚 = 3𝑛 − 2, untuk 𝑚 ganjil dan 3 ≤ 𝑚 ≤ 2𝑛 − 13𝑛 − 4, untuk 𝑚 = 2𝑛 − 4 atau 𝑚 = 2𝑛 − 23𝑛 − 6, untuk 𝑚 = 2𝑛 − 8 atau 𝑚 = 2𝑛 − 6

, n ganjil

2007 M. Salman 𝑅 𝑃𝑛 , 𝑊𝑚 =

1, untuk 𝑛 = 1 dan 𝑚 ≥ 3

𝑚 + 1, untuk 𝑛 = 2 dan 𝑚 ≥ 3, atau 𝑛 = 3 dan 𝑚 genap, 𝑚 ≥ 4 𝑚 + 2, untuk 𝑛 = 3 dan 𝑚 ganjil, 𝑚 ≥ 5

3𝑛 − 2, untuk 𝑛 = 3 dan 𝑚 = 3 atau 𝑛 ≥ 4 dan 𝑚 ganjil, 3 ≤ 𝑚 ≤ 2𝑛 − 12𝑛 − 1, untuk 𝑛 ≥ 4 dan 𝑚 genap, 4 ≤ 𝑚 ≤ 𝑛 + 1

2010 Ahsan 2𝑛 + 1 ≤ 𝑅 𝑆𝑛 , 𝑊8 ≤5(𝑛−1)

2, untuk 𝑛 ≥ 11, 𝑛 ≡ 3 (mod 4)

2010 Kondo

Korani

𝑅 𝑘𝑆𝑛 , 𝑊6 = 𝑘 + 1 𝑛 + 1 untuk 𝑛 ≥ 4 dan 𝑘 ∈ 𝑁

𝑅 𝑆𝑛𝑖 , 𝑊6𝑘𝑖=1 = 𝑅 𝑆𝑛𝑘 , 𝑊6 + 𝑛𝑖

𝑘−1𝑖=1 , untuk 𝑛𝑖 ≥ 4,

untuk setiap 𝑖 dan jika 𝑛𝑖 ≥ 𝑛𝑖+1 untuk 𝑖 = 1,2, … , 𝑘 − 1 dan 2𝑛𝑘 > 𝑛𝑘−1

2014 Hamdana 𝑅 S2n , W2n+2 = 5n − 1, untuk m = 2n + 2 dan n ≥ 4

2014 Andi

Ardhilla 𝑅 𝑆𝑛 . 𝑊𝑛+4 = 2𝑛 +

𝑛

2

(Sumber : Hasmawati, 2007)

36

B. Kerangka Pikiran

Bilangan Ramsey terbagi atas : bilangan Ramsey dua graf,

bilangan Ramsey multigraf, Ramsey minimal, dan multipartite Ramsey

number. Masalah yang akan dibahas pada penelitian ini adalah bilangan

Ramsey dua graf, yaitu antara graf bintang terhadap graf roda khususnya

yang berorde genap. Pembahasan tersebut akan dijelaskan menggunakan

konsep atau teori yang berkaitan dengan bilangan Ramsey.

Penelitian ini dibagi menjadi dua tahapan, yaitu tahap penentuan

batas bawah dan tahap penentuan batas atas. Dalam penentuan batas

bawah, teorema Chvátal dan Harary menjadi acuan untuk mengkonstruksi

graf kritis dengan orde yang lebih tinggi daripada yang diberikan oleh

Chvátal dan Harary sehingga akan didapatkan batas bawah terbesar yang

merupakan batas bawah yang lebih baik.

Selanjutnya, dalam menentukan batas atas akan digunakan

beberapa teorema dan lemma serta beberapa sifat yang terkait dengan

bilangan Ramsey graf. Teorema dan lemma tersebut antara lain : Lemma

Bondy, lemma Brandt, dan lemma Dirac.

Dalam penelitian ini, karena tidak ditemukan batas atas terkecil

yang sama dengan batas bawah terbesar, maka akan dihasilkan bilangan

Ramsey yang berada dalam suatu interval. Lebih jelasnya, tahapan

mengenai penelitian ini digambarkan dalam bentuk flowchart sebagai

berikut.

37

Bilangan

Ramsey Eksak

Gambar II.28. Flowchart Penelitian

Start

Bilangan

Ramsey

Konstruksi graf

kritis maksimal

Batas bawah terbesar

Penggunaan lemma

Bondy, lemma Brandt, lemma Dirac, dan konsep

keterhubungan

Batas atas terkecil

Batas bawah

=

batas atas

End

No Yes

Batas bawah

Chvátal – Harary

dan Korolova

Teorema, lemma, serta konsep yang

berkaitan dengan bilangan Ramsey

pada graf bintang terhadap graf roda

Studi Literatur

Interval

penentuan bilangan ramsey pada graf bintang s2n terhadap graf...

Documents