Perpustakaan Digital ITB

Kajian tentang teori Ramsey semakin diminati sejak Erd¨os dan Szekeres mengaplikasikan teori Ramsey ke dalam teori graf. Beberapa permasalahan yang muncul dari pengembangan teori Ramsey, diantaranya adalah pencarian bilangan Ramsey, bilangan Ramsey sisi, dan penentuan graf Ramsey-minimal. Misalkan diberikan graf-graf G dan H. Notasi F ! (G;H) menyatakan bahwa setiap pewarnaan merah-biru terhadap semua sisi graf F mengakibatkan F memuat subgraf G merah atau subgraf H biru. Graf F dikatakan graf Ramsey untuk pasangan (G;H) jika F ! (G;H). Graf F disebut graf Ramsey (G;H)-minimal jika memenuhi F ! (G;H) dan untuk setiap e 2 E(F) berlaku F ???? e 9 (G;H). Kelas dari semua graf Ramsey (G;H)-minimal dinotasikan dengan R(G;H). Kelas Ramsey (G;H)-minimal dikatakan Ramsey berhingga atau tak berhingga, berturut-turut, jika R(G;H) berhingga atau tak berhingga. Penelitian pada disertasi ini adalah mengkaji kelas tak berhingga R(G;H), dengan G dan H adalah graf-graf lintasan. Masalah penentuan dan karakterisasi semua graf Ramsey (G;H)-minimal untuk sebarang graf G dan H merupakan masalah yang sangat menarik untuk dikaji, walaupun secara umum tidak mudah mencari atau mengkarakterisasi graf-graf yang termasuk dalam kelas R(G;H) sekalipun G dan H adalah graf-graf kecil dan berstruktur sederhana. Khususnya, karena kelas Ramsey minimal untuk pasangan lintasan R(Pm; Pn), untuk setiap 3 m n adalah tak berhingga maka karakterisasinya adalah pekerjaan yang sulit. Karakterisasi graf Ramsey minimal untuk pasangan (P3; P3) sudah diperoleh. Tetapi karakterisasi graf dalam kelas R(Pm; Pn), untuk setiap 3 m < n masih terbuka. Pada disertasi ini diberikan syarat cukup untuk graf Ramsey dan syarat perlu graf Ramsey-minimal untuk pasangan (P3; Pn), untuk setiap n 4. Salah satu dari syarat perlu tersebut menyatakan bahwa semua graf dalam kelas R(Pm; Pn) adalah graf terhubung. Selain itu, diberikan sifat-sifat dari pohon dan graf unisiklik di R(P3; Pn), untuk setiap n 4. Kemudian dikonstruksi dan diberikan secara eksplisit suatu keluarga tak berhingga dari pohon dan graf unisiklik yang memuat siklus dengan panjang tiga sampai tak berhingga di R(P3; Pn), untuk beberapa n 4. Sedangkan untuk n 4 lainnya, keluarga tak berhingga pohon dan graf i unisiklik di R(P3; Pn) ditentukan dengan menggunakan suatu algoritma rekursif. Lebih jauh lagi, diberikan hasil-hasil observasi untuk menentukan keluarga tak berhingga graf unisiklik yang dikonstruksi dari pohon-pohon di R(P3; Pn) yang telah diperoleh dengan cara menempelkan dua titik tertentu pada pohon tersebut. Pada disertasi ini juga dibahas tentang beberapa sifat graf Ramsey (P4; Pn)- minimal, untuk n 4. Pertama, ditunjukkan bahwa semua graf anggota kelas R(P4; Pn) adalah terhubung dan memuat siklus. Dengan sifat ini, dikonstruksi suatu keluarga tak berhingga dari graf unisiklik anggota R(P4; P4) dan dibuktikan ketunggalan dari keluarga graf ini. Selanjutnya, diberikan beberapa keluarga tak berhingga dari graf anggota R(P4; P4) yang memuat lebih dari satu siklus. Pada kelas R(P4; P4), diberikan juga karakterisasi semua graf orde lima dan enam anggota kelas tersebut. Kemudian ditunjukkan bahwa semua graf anggota R(P4; Pn) untuk n 5 harus memuat lebih dari dua siklus tetapi pencarian graf Ramsey minimalnya masih terbuka. Hal ini dikarenakan penentuan anggota R(P4; Pn), untuk n > m 4 lebih sukar dilakukan karena terdapat banyak kemungkinan pewarnaan yang tidak memuat P4 merah atau Pn biru, untuk suatu n 5.