Perpustakaan Digital ITB

Abstrak: Teori Ramsey (1928) pertama kali dikaji dalam konteks permasalahan mencari prosedur untuk menentukan benar-tidaknya (konsistensi) suatu formula logika yang diberikan. Kemudian, teori tersebut menjadi terkenal setelah Erdös dan Szekeres (1935) mengaplikasikannya ke dalam Teori Graf. Ide dasar bilangan Ramsey klasik adalah sebagai berikut. Untuk sembarang bilangan bulat positif a dan b, tentukan bilangan bulat terkecil R = R(a, b) sedemikian sehingga setiap graf F dengan R titik akan memenuhi kondisi berikut ini: F memuat graf lengkap Ka dengan a titik sebagai subgraf atau komplemen dari F memuat graf lengkap Kb dengan b titik sebagai subgraf. Penelitian tentang penentuan bilangan Ramsey klasik R(a, b) telah memperoleh banyak perhatian. Namun demikian, hasilnya masih jauh dari yang diharapkan. Semenjak pertama kali diperkenalkan (1928), hanya sembilan bilangan Ramsey klasik R(a, b) yang baru diketahui. Selanjutnya, perumumuan dari bilangan Ramsey klasik telah banyak dikaji orang dalam berbagai bentuk. Salah satunya adalah yang disebut dengan bilangan Ramsey graf. Bilangan Ramsey graf ini telah tumbuh dan berkembang dalam empat dekade belakangan ini dan menjadi salah satu area yang paling aktif dalam teori Ramsey. Harapan dari dikembangkannya studi bilangan Ramsey graf ini adalah sebagai jembatan untuk menentukan bilangan Ramsey klasik yang lebih besar. Misalkan G dan H dua graf yang diberikan. Bilangan Ramsey graf R(G, H) didefinisikan sebagai bilangan bulat terkecil N sedemikian sehingga setiap graf F dengan order N akan memenuhi kondisi sebagai berikut: F memuat G sebagai subgraf atau komplemen dari F memuat H sebagai subgraf. Penelitian disertasi ini akan mengkaji tentang penentuan bilangan Ramsey graf R(G, Wm) untuk suatu graf G yang diberikan dan graf Wm adalah roda dengan (m + 1) titik. Secara khusus, graf G yang akan dikaji adalah lintasan Pn, bintang Sn, pohon Tm, komet-gurita Yn,l1,...,lk, hutan linier Lp atau lingkaran Cn. Untuk mendapatkan bilangan Ramsey graf R(G, Wm) di atas, terlebih dahulu ditentukan batas bawah dengan memperhatikan Teorema Chvátal dan Harary (1972). Untuk beberapa kasus, Teorema Chvátal dan Harary tidak cukup baik digunakan untuk mendapatkan batas bawah bilangan Ramsey graf, sehingga diperlukan pencarian graf (G, Wm)—elok yang sesuai. Setelah diperoleh batas bawahnya, bilangan Ramsey graf R(G, Wm) tersebut dibuktikan dengan menunjukkan bahwa batas atasnya sama dengan batas bawahnya. Secara umum, metode pembuktian dalam penelitian disertasi ini menggunakan metode standar dalam matematika, antara lain induksi matematika. Hasil utama dari penelitian disertasi ini adalah sebagai berikut. Bilangan Ramsey graf R(G, Wm) dengan G merupakan graf lintasan Pn adalah: R(Pn, Wm) = 2n — 1 untuk m genap dan n≥ m≥ 4; dan R(Pn, Wm) = 3n — 2 untuk m ganjil dan n≥ m≥ 3. Untuk G sebagai graf bintang Sn, penelitian disertasi ini mendapatkan bilangan Ramsey graf R(Sn, W4) = 2n—1 untuk n ganjil dan n≥ 3; R(Sn, W4) = 2n + 1 untuk n genap dan n≥ 4; dan R(Sn, W5) = 3n — 2 untuk n≥ 3. Secara umum, dapat diperlihatkan bahwa R(Sn, Wm) = 3n — 2 untuk m ganjil, m≥ 5 dan n≥ 2m — 4. Untuk G merupakan graf pohon Tn selain graf bintang, penelitian disertasi ini telah mendapatkan bilangan Ramsey graf R(Tn, W4) = 2n—1 untuk n≥ 4, dan R(Tn, W5) = 3n — 2 untuk n≥ 3. Khusus untuk m ganjil, m≥ 5 dan n≥ 2m — 4, bilangan Ramsey graf R(Tn, Wm) juga telah diperoleh untuk Tn yang berbentuk komet-gurita. Di samping itu, penelitian disertasi ini juga mendapatkan bilangan Ramsey graf R(Lp, Wm) dengan Lp hutan linier, m ganjil, m≥ 5 dan n≥ 2m — 4. Penentuan bilangan Ramsey graf untuk kombinasi antara lingkaran dan roda Wm juga telah dikerjakan pada penelitian disertasi ini. Sebagai hasilnya adalah R(C4, W4) = 9, R(C4, W5) = 10, R(C4, W6) = 9, R(Cn, W4) = 2n — 1 untuk n≥ 5, dan R(Cn, W5) = 3n — 2 untuk n≥ 5.