APPLICATIONS OF CHINESE POSTMAN PROBLEM, DOMINATING SET, AND SPECTRAL GRAPH PARTITION IN GRAPH THEORY FOR SECURITY SURVEILLANCE PROBLEM

• Main Author: Permadani, Bayu
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/49877
• Institution: Institut Teknologi Bandung

Safety issues are quite crucial currently. Cases of motor vehicle and treasure thefts are quite common due to victim or security carelessness. In the residential complex, security officer usually patrols at any time to monitor the people movements around them that could potentially interfere regional security. Therefore, final project entitled “Applications of Chinese Postman Problem, Dominating Set, and Spectral Graph Partition in Graph Theory for Security Surveillance Problem” discusses about security officer patrol routes in a residential complex and placement of security post which are optimal so that security surveillance activities by security officer can run more effectively and efficiently. The final project method is a literature study using secondary data sources from Google Earth, namely coordinate data for points of intersection, turn, and boundary. The final project takes Bukit Cimindi Raya Residential Complex, Cimahi City, West Java, as a studied area. The theoretical basis used is a graph theory, consisting of Chinese postman problem, vertex cover, dominating set, and spectral graph partition. The final project result consist of three parts, i.e. minimum security patrol route taken to surround the residential complex overall and partially with Chinese postman problem and vertex cover concept, simulation of security post placement with dominating set concept, and route partition for each security officer (there are two security officer in this final project) by spectral graph partition concept. The software used in this final project is MATLAB R2020a and Google Earth Pro 7.3.3.7699 (64-bit) 2020.