Aplikasi Dimensi Metrik Untuk Meminimalkan Pemasangan Sensor Kebakaran Sebuah Gedung

Abstract

Diberikan himpunan terurut W = {w₁, w₂, . . ., w_k} dari vertex-vertex dalam graf terhubung G dan untuk setiap vertex  v elemen V(G), representasi dari v terhadap W adalah k – tuple r(v|W) = (d(v, w₁),  d(v, w₂), . . ., d(v, w_k)). Jika  untuk setiap vertex  v elemen V(G) berbeda, maka W disebut himpunan resolving dari . Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut dinamakan dimensi metrik dari G dinotasikan dengan dim(G).

Pada penelitian ini dibahas salah satu aplikasi dimensi metrik graf yaitu untuk meminimalkan pemasangan sensor kebakaran sebuah gedung. Dalam suatu gedung, ruangan dapat direpresentasikan sebagai vertex dan dinding atau lantai antara ruangan yang satu dengan lainnya sebagai edge dari suatu graf G sehingga dapat dibuat graf terhubung yang mewakili gedung tersebut.