Article Details

GRAF RAMSEY MINIMAL UNTUK PASANGAN GRAF YANG MEMUAT SIKLUS

Oleh   Maya Nabila [20119019]
Kontributor / Dosen Pembimbing : Prof. Dr. Edy Tri Baskoro;
Jenis Koleksi : S2 - Tesis
Penerbit : FMIPA - Matematika
Fakultas : Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA)
Subjek :
Kata Kunci : Graf Siklus, Graf Bintang, Graf Lintasan, Graf Ramsey Minimal.
Sumber :
Staf Input/Edit : Dwi Ary Fuziastuti  
File : 1 file
Tanggal Input : 2021-02-18 13:28:40

Seorang ilmuwan bernama Frank Plumpton Ramsey mengemukakan suatu teori mengenai pencarian prosedur untuk menemukan benar-salahnya suatu formula logika yang diberikan, teori tersebut dikenal sebagai Teori Ramsey [24]. Kemudian, teori Ramsey berkembang hingga ditemukannya teori graf Ramsey minimal oleh Burr pada tahun 1970. Menurut Burr [7], teori graf Ramsey minimal didefinisikan sebagai berikut. Misalkan graf G dan graf H merupakan graf sederhana sebarang, yaitu graf yang tidak memuat sisi ganda dan loop. Notasi F ! (G,H) berarti bahwa sebarang pewarnaan merah-biru terhadap semua sisi di graf F selalu menyebabkan salinan subgraf G merah atau salinan subgraf H biru termuat di dalam graf F. Kemudian, 8e 2 F notasi F ? e 9 (G,H) menyatakan bahwa terdapat pewarnaan terhadap sisi-sisi F ? e sehingga graf tersebut tidak memuat salinan G merah dan salinan H biru. Kelas R(G,H) menyatakan himpunan graf yang memenuhi syarat: 1. F ! (G,H) dan 2. 8e 2 F, F ? e 9 (G,H). Pasangan (G,H) disebut Ramsey hingga jika kelas R(G,H)memiliki anggota berhingga, sedangkan pasangan (G,H) disebut Ramsey tak hingga jika kelas R(G,H) memiliki anggota tak berhingga. Dalam tesis ini akan dibahas graf yang termasuk ke dalam kelas R(G,H) dengan graf G suatu graf siklus dan graf H suatu graf bintang. Masalah mengenai karakterisasi dan penentuan semua graf Ramsey (G,H)?minimal untuk sebarang graf G dan H bukanlah hal yang sederhana atau mudah untuk dikerjakan. Diperoleh beberapa graf anggota kelas khusus kelas Ramsey (Cn,K1,2)-minimal untuk n 2 [5, 9] i dan kelas Ramsey (C4,K1,m)-minimal untuk m % 3. Kemudian sudah diperoleh karakterisasi graf Ramsey untuk pasangan (C2n,K1,2) untuk n % 7 ganjil.