KAJIAN PEWARNAAN TITIK PADA OPERASI GRAF LINTASAN, GRAF LINGKARAN DAN GRAF BINTANG

Abstract

Kajian Pewarnaan Titik pada Pengoperasian Graf Lintasan, Graf Ling karan dan Graf Bintang; Alfian Yulia Harsya, 101810101008; 2015: 95 hala man; Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember. Teori graf adalah bagian dari matematika diskrit yang banyak digunakan se bagai alat bantu untuk menggambarkan suatu persoalan agar lebih mudah dime ngerti dan diselesaikan. Teori graf pertama kali diperkenalkan oleh Leonhard Euler, seorang matematikawan berkebangsaan Swiss pada tahun 1736 melalui tulisannya yang berisi upaya pemecahan masalah Jembatan Konigsberg yang sa ngat sulit dipecahkan pada masa itu. Meskipun pada awalnya graf diciptakan un tuk diterapkan dalam penyelesaian kasus, namun graf telah mengalami perkem bangan yang sangat luas didalam teori graf itu sendiri. Salah satu teori yang dikembangkan dalam teori graf adalah pewarnaan (colouring). Terdapat tiga macam pewarnaan dalam teori graf, yaitu pewarnaan titik (vertex colouring), pewarnaan sisi (face colouring), dan pewarnaan wilayah (region colouring). Pewarnaan titik (vertex colouring) adalah pemberian warna pada titik-titik graf dimana dua titik yang bertetangga diberi warna yang berbeda. Jumlah warna paling sedikit yang digunakan untuk mewarnai titik pada graf G disebut bilangan kromatik yang dilambangkan dengan χ(G). Pewarnaan titik da pat diterapkan pada graf yang merupakan hasil operasi dari beberapa graf khusus. Adapun macam-macam pengoperasian graf yaitu operasi Joint (G + H), Carte sian Product (G H), Crown Product (G ⊙ H), Tensor Product (G ⊗ H), Com position (G[F]), Shackel, dan Amalgamation. Pada penelitian ini menggunakan metode penelitian eksploaratif dan terapan. Penelitian eksploratif adalah jenis penelitian yang bertujuan menggali hal-hal yang ingin diketahui oleh peneliti dan hasil penelitian dapat digunakan sebagai dasar penelitian selanjutnya. Penelitian terapan (applied research) merupakan penyelidikan yang hati-hati, sistematik dan terus-menerus terhadap suatu masalah dengan tujuan untuk digunakan dengan viii segera untuk keperluan tertentu. Penelitian ini bertujuan untuk mencari batas atas bilangan kromatik dan fungsi pewarnaan titik pada graf yang dioperasikan. Graf yang digunakan adalah graf lintasan (path), graf lingkaran (cycle) dan graf bintang (star). Pada penelitian ini menghasilkan 10 teorema dan 4 akibat dari teorema sebelumnya, antara lain: 1. Teorema 4.1.1 Misal G adalah joint dari graf lintasan dan graf lingkaran. Untuk n ≥ 2 dan m ≥ 3, bilangan kromatik G = (P χ(P n + C m ) = ( n 4, untuk m genap 5, untuk m ganjil + C m ) adalah 2. Teorema 4.1.2 Misal G adalah joint dari graf lingkaran dan graf bintang. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik G = (C χ(C n + S m ) = ( 4, untuk n genap 5, untuk n ganjil n + S m ) adalah 3. Akibat 4.1.1 Misal G adalah cartesian product dari graf lintasan dan graf lingkaran. Untuk n ≥ 2 dan m ≥ 3, bilangan kromatik G = (P χ(P n C m ) = ( 2, untuk m genap 3, untuk m ganjil 4. Akibat 4.1.2 Misal G adalah cartesian product dari graf lingkaran dan graf bintang. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik G = (C adalah χ(C n S m ) = ( 2, untuk n genap 3, untuk n ganjil 5. Akibat 4.1.3 Misal G adalah tensor product dari graf lintasan dan graf lingkaran. Untuk n ≥ 2 dan m ≥ 3, bilangan kromatik G = (P ix n C m ) adalah n n S ⊗ C m m ) )