METRIC DIMENSION OF A GRAPH: AN APPROACH TO OBTAIN THE MINIMUM NUMBER AND LOCATION OF THE PLACEMENT OF FIRE SENSORS IN A BUILDING Desrianti L. Susanti (a), Rapmaida M. Pangaribuan (b), Farly O. Haning (c*)
a,b) Mathematics Department, Universitas Nusa Cendana,
Jalan Adisucipto-Penfui, Kupang 85000, Indonesia
c) Mathematics Department, Universitas Nusa Cendana,
Jalan Adisucipto-Penfui, Kupang 85000, Indonesia
*farly_haning[at]staf.undana.ac.id
Abstract
A fire disaster is a small or large flame that occurs in an unwanted place. The damage caused by a disastrous fire in a public buildings or facilities will increase if it is not addressed promptly. The installation of fire sensors is one of the solutions needed. Fire sensors will detect the location of the fire and send a warning so that everyone immediately leaves the site or extinguishes the flames that appear around the fire site. The study aims to obtain the minimum number of fire sensors installed on a building using the metric dimension concept on the graph. This concept allows fire sensors to accurately detect the location of a fire so that it can be dealt with immediately. The research method used is the study of literature. Initially, the building was depicted in the form of a graph. Literary studies are conducted to find the metric dimensions of graphs that are similar to the graphs of a building. Graph G is formed with its set of vertex -(V(G))- indicating the rooms in the building and the set of sides -(E(G))- that connect two points on the graph if a door connects the two rooms. The graph image obtained on each floor of the Universitas Nusa Cendana Postgraduate Building forms the Bridge graph that connects the Star graphs -K_(1,s)- and -K_(1,t)-. This graph is a simple connected graph. A metric dimension is the cardinality of a metric base on a connected and simple graph. The metric base is the resolving set -W \subseteq V(G)- with the smallest cardinality. A set W is called a resolving set if it can make each vertex on the graph -G- have a different representation or coordinate. The representation of a vertex -v\in V- on the graph G notated by -\( r(v|W)=(d(v,w_1),d (v,w_2),d( v,w_k ))\)- which -d(v,w_i ), 1≤-i≤-k - is the shortest path length that connects vertex -v \in V- and -w_i \in W-. The vertex on -W-, which are the metric base, are the reference vertex for the placement of the fire sensor. Then the metric dimension of the graph is the minimum number of fire sensors needed on each floor. The study^s results found the bridge graph^s metric dimensions that connect the star graphs -K_(1,s)- and -K_(1,t)- is -s+t-2-. By applying this result obtained on the 1st floor, 2nd floor, and 3rd floor of the graduate building, respectively, as many as 14,12, and 8 fire sensors can be installed. It means that 15 rooms out of 49 do not need fire sensors.
Keywords: Fire sensors, Graph of a building, Metric Dimension
