Analisis Koneksi Pelangi Pada Graf Khusus dalam Mengasah Keter- ampilan Berpikir Tingkat Tinggi;

Abstract

Saat ini, kajian mengenai teori graf terus berkembang, salah satunya yaitu koneksi pelangi pada graf khusus dan kaitannnya dalam aplikasinya pada analisis sintaksis ruang serta keterampilan berpikir tingkat tinggi dalam analisis koneksi pelangi. Sintaksis ruang mempergunkan konsep jarak yang disebut kedalaman (depth) yang diukur dalam langkah (step) yang disebut jarak topologis atau topo- logical distance (Hillier et al: 1987). Keterampilan berpikir tingkat tinggi dalam Taksonomi Bloom diklasi¯kasikan mulai tahap mengingat, memahami, menerap- kan, menganalisis, mengevaluasi, dan mencipta. Graf khusus adalah graf yang mempunyai keunikan dan karakteristik bentuk khusus. Ada 12 graf khusus dalam penelitian ini. terdiri dari Graf Bipartit, Graf Prisma, 2 Graf Amalgamasi, dan 8 Graf Shack. Konsep koneksi pelangi diterapkan pada graf khusus. Konsep koneksi pelangi pada graf pertama kali diperkenalkan pada tahun 2006 oleh Chartrand dkk. Misalkan G = (V (G);E(G)) sebuah graf terhubung tidak trivial. Suatu pewarnaan terhadap sisi-sisi di G dide¯nisikan sebagai f : E(G) ! f1; 2; 3; :::; kg; k 2 N; dimana dua sisi yang bertetangga boleh berwarnai sama. Suatu lintasan u ¡ v P di G merupakan lintasan pelangi (rainbow path) jika tidak ada dua sisi di lintasan yang berwarna sama. Graf G disebut rainbow connected atau koneksi pelangi dengan pewarnaan f jika G memuat suatu rainbow u-v path untuk setiap dua titik u; v 2 G. Dalam hal ini, pewarnaan f dikatakan rainbow coloring atau pewarnaan pelangi di G. Jika terdapat k warna di G maka f dikatakan pewarnaan k pelangi minimum k sehingga terdapat pewarnaan k pelangi di G disebut rainbow connection number atau koneksi pelangi, ditulis rc(G). Suatu pewarnaan pelangi yang menggunakan rc(G) warna dikatakan nilai koneksi pelangi minimal di G. vii viii Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik yaitu dengan menurunkan teorema yang telah ada tentang nilai batas bawah dan batas atas, kemudian diterapkan dalam penentuan warna pada setiap sisi graf dengan fungsi f : E(G) ! 1; 2; 3; :::; n. Hasil penelitian ini berupa teorema baru mengenai koneksi pelangi pada graf khusus. Teorema yang dihasilkan adalah sebagai berikut: 1. Untuk n ¸ 2, nilai koneksi pelangi dari graf Bipartit Kn;n adalah 2. 2. Untuk n ¸ 4, nilai koneksi pelangi dari graf Amal (W4;C4) adalah 2. 3. Untuk n ¸ 2, nilai koneksi pelangi dari graf Prisma D3;n adalah n. 4. Untuk n ¸ 2, nilai koneksi pelangi dari graf Amalgamasi Prisma (D4;2; e; n) adalah n+3. 5. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (TB3; v; n) adalah n. 6. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (K1 +K4; v; n) adalah n. 7. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (F4; v; n) adalah 3n. 8. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (CL6; v; n) adalah 3n. 9. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (W6; P2; n) adalah 2n. 10. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (TC3; v; n) adalah 2n. 11. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (KC; v; n) adalah 3n. 12. Untuk n ¸ 2, nilai koneksi pelangi dari graf Shack (CW5; v; n) adalah 3n. Dari kajian diatas ada beberapa yang belum ditemukan sehingga dalam penelitian ini diajukan open problem yaitu bagaimana mengaplikasikan koneksi pelangi pada graf sebarang dan implementasi line graph pada J-graph.