DESRIANTI LYDIA SUSANTI Pengarang RAPMAIDA MEGAWATY PANGARIBUAN Dosen Pembimbing 2 Farly Oktriany Haning Dosen Pembimbing 1 Ariyanto Ketua Penguji Rapmaida M. Pangaribuan Penguji 2 Farly Oktriany Haning Penguji 1

Untuk menangani masalah bencana kebakaran pemasangan sensor kebakaran merupakan salah satu solusi yang dibutuhkan. Sensor kebakaran akan mendeteksi lokasi terjadinya kebakaran dan mengirimkan peringatan agar semua orang segera meninggalkan lokasi atau mematikan nyala api yang muncul di sekitar lokasi kebakaran. Penelitian ini bertujuan untuk memperoleh jumlah minimal sensor kebakaran yang harus dipasang pada suatu gedung dengan menggunakan konsep dimensi metrik pada graf. Konsep ini memungkinkan sensor kebakaran mendeteksi dengan tepat lokasi terjadi kebakaran sehingga kebakaran dapat segera ditangani. Metode penelitian yang digunakan adalah kajian literatur. Pada mulanya denah gedung digambarkan dalam bentuk graf G. Graf G dibentuk dengan himpunan titik-titiknya (V (G)) menyatakan ruangan-ruangan yang ada pada gedung tersebut dan himpunan sisi (E(G)) yang menghubungkan dua titik pada graf jika kedua ruangan tersebut dihubungkan dengan sebuah pintu. Selanjutnya, studi literatur dilakukan untuk menemukan dimensi metrik graf yang sama dengan graf G yang telah dihasilkan. Gambar graf G yang diperoleh pada tiap lantai gedung Pascasarjana Universitas Nusa Cendana (Undana) membentuk graf Jembatan yang menghubungkan graf bintang K1,m dan K1,n. Dimensi metrik merupakan kardinalitas dari suatu basis metrik pada graf terhubung dan sederhana. Basis metrik adalah himpunan pembeda W V (G) dengan kardinalitas terkecil. Himpunan W disebut himpunan pembeda jika dapat membuat setiap titik pada graf G memiliki representasi atau koordinat yang berbeda. Representasi suatu titik v V pada graf G dinotasikan dengan r(v W ) = (d(v, w1), d(v, w2), . . . , d(v, wk)). Titik-titik pada W adalah basis metrik merupakan titik rujukan letak sensor kebakaran yang dipasang. Kemudian dimensi metrik dari graf merupakan jumlah minimal sensor kebakaran yang dibutuhkan pada tiap lantai. Hasil kajian menemukan dimensi metrik dari graf jembatan yang menghubungkan graf bintang K1,m dan K1,n sebesar m + n 2. Dengan menerapkan hasil ini diperoleh pada lantai 1, lantai 2 dan lantai 3 gedung pascasarjana Undana masing-masing dapat dipasang sebanyak 14,12, dan 8 sensor kebakaran. Ini artinya sebanyak 15 ruangan dari total 49 ruangan tidak perlu dipasang sensor kebakaran. Kata Kunci : basis, graf, dimensi metrik.