PENERAPAN TEKNIK KONSTRUKSI GRAF, RAINBOW CONNECTION, DOMINATING SET DALAM ANALISIS MORFOLOGI JALAN

Abstract

Penerapan Teknik Konstruksi Graf, Rainbow Connection, dan Dominating Set Dalam Analisis Morfologi Jalan;Ridho Alfarisi, 110210101043; 2014: 104 halaman; Program Studi Pendidikan Matematika, Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Jember. Saat ini, kajian mengenai penerapan teori graf terus berkembang, fokus kaitannnya dengan perkembangan IPTEK terutama dalam analisis morfologi jalan. Morfologi jalan sangat erat dengan mobilitas masyarakat sehingga perlu ada kajian yang mendalam. Objek yang diteliti adalah jalan sehingga peta jalan direpresentasikan ke dalam J-graph menggunakan teknik konstruksi line graph, dan masalah aplikasi yang dapat dikaitkan dengan teori graf misalkan penempatan pos pantau dengan teori dominating set, penentuan jalur terpendek dikaitkan dengan teori rainbow connection. Selain itu fokus penelitian ini yaitu mengembangkan teori dominating set dan rainbow connection pada sebarang graf khusus. Line graph dengan sebuah graf G, L(G) = (A; N) adalah sebuah graf sedemikian hingga himpunan dari titik dari L(G) merupakan himpunan dari sisi di G dan himpunan titik dari L(G) yaitu jika (u; v) 2 G maka (uv) = (vu) 2 E(G) jadi V (L(G)) = E(G). L(G) merupakan Line graph yang memiliki D = 2(4(G)) ¡ 2 dan D(L(G)) = D(G) + 1. De¯nisi rainbow connection pada sebarang graf khusus merupakan pewarnaan sisi yang dide¯nisikan f : E(G) ! f1; 2; 3; :::; ng atau mewarnai setiap sisi dengan fungsi f. De¯nisi dominating set merupakan subset S µ V dari titik di G sedemikian sehingga untuk semua titik v 2 V , salah satu dari v 2 S atau sebuah tetangga u dari v ada di S. Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik yaitu 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) ! f1; 2; 3; :::; ng dan penentuan titik-titik sebagai dominating set. Hasil penelitian ini berupa teorema baru mengenai rainbow connection, dan viii dominating set pada sebarang graf khusus. Teorema yang dihasilkan sebagai berikut: a. Teorema 4.4.1 Untuk n ¸ 2, rainbow connection number dari graf buku segitiga Bt n adalah rc(Bt n ) = ( 2; jika 2 · n · 4 3; jika n ¸ 5 b. Teorema 4.4.2 Untuk n ¸ 2, rainbow connection number dari graf kipas tangkai Kt n adalah rc(Kt n ) = ( 2; jika n = 2; 3 3; jika n ¸ 4 c. Teorema 4.4.3 Untuk n ¸ 2, rainbow connection number dari graf bunga Fl n adalah 3. d. Teorema 4.4.4 Untuk n ¸ 3, rainbow connection number dari graf jaring laba-laba Wb n adalah rc(Kt n ) = 8 > > < > > : 3; jika 3 · n · 6 4; jika n = 7 5; jika n ¸ 8 e. Teorema 4.4.5 Untuk n ¸ 2, rainbow connection number dari graf tangga permata Dl n adalah n + 1 f. Teorema 4.4.6 Untuk n ¸ 2, rainbow connection number dari graf parasut Pc n adalah n + 1 g. Teorema 4.4.7 Untuk n ¸ 2, rainbow connection number dari graf windmill W n 4 adalah 3 h. Teorema 4.5.1 Untuk n ¸ 3 dan m ¸ 2, dominating number berjarak satu dari graf rem cakram Db n;m adalah ix °(Db m;n ) = d 3nm¡2n 5 e i. Teorema 4.5.2 Untuk n ¸ 2 dan m ¸ 1, dominating number berjarak satu dari graf lampion $ n;m adalah °($ n;m ) = n + 1 j. Teorema 4.5.3 Untuk n ¸ 3 dan m ¸ 2, dominating number berjarak satu dari graf prisma D n;m adalah °(D n;m ) = d nm 4 e k. Teorema 4.5.4 Untuk n ¸ 2 dan m ¸ 1, dominating number berjarak satu dari graf tingkat tangga prisma Dt °(Dt n;m ) = ( n;m adalah n; jika m = 1 dan n ¸ 3 nb m 2 c; jika n ¸ 3 dan m ¸ 2 l. Teorema 4.5.5 Untuk n ¸ 2 dan m ¸ 1, dominating number berjarak dua dari graf lampion $ n;m adalah b 2nm+n+1 4m+3 c m. Teorema 4.5.6 Untuk n ¸ 3 dan m = 2, dominating number berjarak dua dari graf rem cakram Db ° 2 (Db 2;n ) = n;2 8 > > < > > : adalah 2; jika n = 3 d n 3 e; jika 4 · n · 6 dan n ¸ 10 d n 3 e + 1; jika 7 · n · 9 n. Teorema 4.5.7 Untuk n ¸ 3 dan m ¸ 3, dominating number berjarak dua dari graf amalgamasi cycle Amal(C n ; 1; m) adalah md n 5 e + 1 Kajian diatas ada beberapa yang belum ditemukan sehingga dalam penelitian ini diajukan masalah terbuka yaitu pengaplikasi greedy algorithm dalam meminimalkan dominating set pada graf sebarang (P-graph).