A day of a police officer

A Day of a Police Officer SQQM1063 GROUP (D) What police officer do How to solve the crime everyday? using graph theory? Let's use minimum spanning tree to Help us find the robber using graph find the suitable route for police officer representation!

01 Introduction The first thing that a police officer do everyday is to on their patrol. Find the shortest route to make their patrol work more efficient. 02 Spanning Tree The first thing that a police officer do everyday is to on their patrol. Find the shortest route to make their patrol work more efficient. 07 Shortest Path Suddenly, a robbery happen in a grocery store, how to reach there in the shortest time? CONTENTS CONTENTS 12 Graph Representation There are three suspects, Who are the actual robber who rob the grocery store? 18 Graph coloring On tomorrow, six activities were held at Queensbay Mall, As a leader of police officer, how many police officer should to be sent to secure these activities can finished successfully. 23 Reflection

INTRODUCTION This magazine is to apply graph theory into a day of a police officer who named Sam. By using minimum spanning tree, we can found the shortest path for police officer to patrol. Next, we can find the fastest route to reach the crime scene with the shortest path theorem. After they found three suspects at the crime scene, we will use graph representation to find the actual robber that rob a grocery store. Lastly, to find how many police officer they should send for activities that are held by tomorrow, we used graph coloring to find out the chromatic number of the graph. PAGE 01

SPANNING PAGE 02 TREE WHAT IS SPANNING TREE? Spanning Tree is a tree that contain and connect every vertex in the simple graph with the minimum number of edges. Spanning tree is consider as a subgraph of the simple graph, this is because we exclude it from the simple graph. SOURCE: TUTORIALSPOINT

SPANNING TREE The special point of spanning tree is we can have different shape of spanning tree from one simple graph as long as it connected to every vertex of the graph EXAMPLE Three different shapes of spanning tree from W5 graph SOURCE: GOOGLE PAGE 03

PAGE 04 MINIMUM SPANNING TREE SOURCE: GOOGLE MAP SCENARIO EARLY IN THE MORNING, MOST OF THE POLICE OFFICER WILL CONDUCT A PATROL OF THE LOCAL NEIGHBOURHOOD. AS A POLICE OFFICER, SAM'S JOB IS TO MONITOR THE SUNGAI NIBONG NEIGHBOURHOOD AND ENSURE THAT NOTHING ILLEGAL OCCURS WITHIN HIS AUTHORITY. THE MAP AS SHOWN ABOVE IS THE MAP OF THE NEIGHBOURHOOD NEAR THE POLICE STATION THAT SAM WORKED AT.

SOLUTION This is the map of the surrounding area near the police station that Sam worked at. There are six places where Sam must pass by and give a check: B - TechStreet X Taycon C - Restoran Goh Teo Kee D - Pak Deey’s Burger & Kueh2 E - Cizen F - Bukit Kecil Apartment G - Nasi Lemak Seri Melor. This map shown above is the graph which represent the map of neighbourhood Sungai Nibong area.To find the minimum path to arrive every destination, we can find the route by calculating the minimum spanning tree of the graph. By using spanning tree, we have to connect all vertex by using the shortest edge. (Vertices = The circles which contain alphabets) (Edge = The line connected two vertices) PAGE 05

PAGE 06 SOLUTION After finding the shortest edges, we found the minimum spanning tree of the patrol route of police officer, Sam. Minimum spanning tree = 3+1+2+3+2+1 = 12

THE The shortest path theory is SHORTEST a theory which used to PATH found the shortest path so THEORY that we can reach our destination in the What does the shortest path shortest time. A shortest means? Is it useful in our daily life? path is a path with the least distance between PAGE 07 two points in the graph. A algorithm named Dijkstra’s Algorithm is used in the shortest path theory.

PAGE 08 Dijkstra’s Algorithm Source: gitconnected Source: Physics Today In 1959, Edsger Dijkstra, a Dutch computer scientist, presented an algorithm that may be applied to a weighted graph. The graph can be directed or undirected, but it must embrace a non-negative value on every edge. This algorithm was given the name \"Dijkstra's Algorithm\" after him.

DIJKSTRA’S ALGORITHM There are four main steps in Dijkstra's Algorithm: 1.Mark a ending vertex which having a distance 0 and choose it as current. 2. Find all vertices that linked to the current vertex and calculate the distance. 3.After we found the vertex which having the least distance that represent by the edge and mark it. We will never look back again to this vertex. 4. Repeat from step 2 and the shortest path are found after we find the least distance to the last ending vertex. Example of Dijkstra's Algorithm represented in table form Source: Youtube PAGE 09

APPLICATION OF THE SHORTEST PATH PROBLEM Sam had just arrived at his police station after finishing the patrol when he received a call that a robbery had occurred at the 7-eleven grocery shop. He must locate the shortest route to his destination. This is the distance between his location and the 7-eleven grocery store where happening a robbery. Source: Google Map How to find the fastest route to the crime scene? PAGE 10

SCENARIO 7-eleven Grocery Store Police Station Sungai Nibong The graph shown above is the map of police station to the grocery store in graph form. A is the vertices which represent Police Station Sungai Nibong while G represent the 7-eleven Grocery Store. By using Dijkstra's Algorithm in table form, we found the shortest path to reach the 7- eleven grocery store from the police station where Sam are. THE SHORTEST PATH TO 7-ELEVEN IS A-B-E-G PAGE 11

GRAPH REPRESENTATION Many items in our daily lives, such as transit maps, software design applications, and social networks, are represented by graphs. In our immediate environment, we may observe graph representations. Mary, for example, must travel to her office every morning by LRT and must consult the LRT map to determine which line she will take and when she must depart. A graph with simply vertices and edges may also be used to depict a person's social circle. PAGE 12

EXAMPLE OF GRAPH REPRESENTATION Adjacency Lists, Adjacency Matrices, Incidence Matrices The three ways to represent a graph are adjacency lists, adjacency matrices, and incidence matrices. An Adjacency List for a Simple Graph To begin, an adjacency list may be used to describe a network without any edges by defining the vertices that are near to each other. An Adjacency Matrices for a Simple Graph Next, we'll look into adjacency matrices, which are matrices that may be used to describe directed and undirected graphs with loops and multiple edges. PAGE 13

PAGE 14 EXAMPLE OF GRAPH REPRESENTATION Adjacency Lists, Adjacency Matrices, Incidence Matrices An Incidence Matrices for a Pseudograph WHEN A GRAPH IS SPARSE WHICH MEANS IT HAS FEW EDGES RELATIVELY TO THE TOTAL NUMBER OF POSSIBLE EDGES, IT IS MUCH MORE PRODUCTIVE TO REPRESENT THE GRAPH USING AN ADJACENCY LIST THAN AN ADJACENCY MATRIX. AN ADJACENCY MATRIX, ON THE OTHER HAND, IS SUITABLE FOR A DENSE GRAPH WITH A LARGE NUMBER OF POTENTIAL EDGES. FINALLY, THE N X M MATRIX ARE USED TO REPRESENT THE NUMBER OF VERTICES, N, AND THE NUMBER OF EDGES, M, IN INCIDENCE MATRICES. NEXT PAGE

PAGE 15 Application of Graph Representation WHO IS THE actual ROBBER? After Sam arrive the crime scene, police officer have founded three suspects which are suspect A, suspect B and suspect C. After taking these three suspects back to police station make investigation, each of them give their own statement. In this case, we know that among these three suspects, only one of them are telling the truth. Suspect A : I'm not the robber Suspect B: Suspect A is the robber Suspect C: I'm not the robber

PAGE 16 Application of Graph Representation Using graph that contain vertices which represent to the three suspects and edges that they assume who is the robber according to their statement. The graph is shown below. the graph in Incidences Matrices form

PAGE 17 Application of Graph Representation To find out who are the real robber, we have to separate the graph into three cases by assuming one of them is the robber who rob the grocery mart First of all, we assume if suspect A is the robber. From the case 1, we can see that there are two person which are suspect B and C thinks that suspect A is the real robber from their statement. But in this case, there are only one person who are telling the truth, so it is impossible for suspect A to be the real robber. For case 2, it is the same situation as case 1, because there are two person assuming B are the robber, so B are not the robber. Now, let's see case C. We assume that suspect C is the real robber in this case. As the graph shown, there are only suspect A assuming suspect C is the robber and we also know that only one person among these three are telling the truth. So, we can found out that suspect C is the actual robber and suspect A is the only one who telling the truth.

GRAPH COLOURING SOURCE: GOOGLE PAGE 18

\"WHAT IS GRAPH COLORING?\" Graph coloring is the assignment of a color to each vertex of the graph to make sure there are no two adjacent vertices are assigned the same color. Secondly, the chromatic number of a graph is defined as the least number of color needed for a coloring of this graph. CHROMATIC NUMBER OF THE GRAPH, G IS DENOTED AS X(G) GRAPH COLOURING Application of graph coloring Graph coloring is used to solve the problem when we have limited of resources or having some restriction. Graph coloring can be used in schedulling, exam timetable and designing the seating. Bonus: We can use graph coloring to solve SUDOKU puzzles ! PAGE 19

GRAPH COLOURING Scenario As a captain, Sam must set aside time to prepare for tomorrow's activities in Queensbay Mall, which is close by. There are six activities going having on at the same time duration which is 3 hours and same venue, Sam realise that the number of activities are many, so they have to send some police officer to secure it. To decide how many police officer he should send, Sam must utilise graph colouring to determine how many people he should let go in order to safeguard the disorder. PAGE 20

PAGE 21 APPLICATION OF GRAPH COLOURING As we mentioned just now, these six activities are going to hold at venue that are near and the time some are crashed with others. So, Sam has to find the chromatic number of the graph to decide how many groups of police officer he has to send. One group include of two police officer.

PAGE 22 SOLUTION After that, we make a graph that consists of six activity which are vertices. Next, we start colouring the graph and avoid there have same colour between two adjacent vertices. One colour represent to one group which contain of two police officer. By using graph coloring, we found that Sam only need let three group of police officer attend security activity on tomorrow. CHROMATIC NUMBER OF THE GRAPH, X(G) = 3 COLOURS

Reflection After doing this individual project, I discovered that I am learning a lot while doing so. For instance, I'm learning how to use graph theory in everyday situations. Because I believe this will be an intriguing topic for me to apply on, I have chosen the day of the police officer as the theme of my individual project. In this assignment, we could learn how to apply the graph representation and the statements they provide in particular to figure out who the true robber is among the suspects. At first, I thought this project would be difficult for me because it is the first individual project of this semester, but after completing it, I found it to be a lot of fun. I think a lot simply to come up with a fun topic so that others may learn more about graph theory via these fun themes. Finally, I'd want to express my gratitude to Prof Dr Haslinda Ibrahim for helping me in completing this unique research. This assignment allowed me to discover the most enjoyable aspect of discrete mathematics. KH'NG WEI XIN 285602 PAGE 23

FEB 2017ReferenceA DAY OF A POLICE OFFICER 1.H.ROSEN.K. (2019). IN DISCRETE MATHEMATICS AND ITS APPLICATION, 8TH EDITION. NEW YORK: MC GRAW HILL EDUCATION. 2.PHYSICSTODAY.(N.D.). RETRIEVED FROM THE GRAPH COLORING: HTTPS://PHYSICSTODAY.SCITATION.ORG/DOI/10.1063/1.1570789 3.ANALYTIC STEPS.(N.D.). RETRIEVED FROM DIJKSTRA’S ALGORITHM: THE SHORTEST PATH ALGORITHM: HTTPS://WWW.ANALYTICSSTEPS.COM/BLOGS/DIJKSTRAS-ALGORITHM- SHORTEST-PATH-ALGORITHM 4.WIKIPEDIA.(N.D.). RETRIEVED FROM GRAPH COLORING HTTPS://EN.WIKIPEDIA.ORG/WIKI/GRAPH_COLORING#APPLICATIONS 5.LUMEN.(N.D.). RETRIEVED FROM EULER AND HAMILTONIAN PATHS AND CIRCUITS: HTTPS://COURSES.LUMENLEARNING.COM/WMOPEN- MATHFORLIBERALARTS/CHAPTER/INTRODUCTION-EULER-PATHS/ 6.JESSICA. B. (2020). RETRIEVED FROM HOW TO SOLVE A CRIME WITH GRAPH THEORY: HTTPS://NEO4J.COM/BLOG/GRAPHCAST-HOW-TO- SOLVE-A-CRIME-WITH-GRAPH-THEORY/ Thank you for watching! A DAY OF A POLICE OFFICER PAGE 24