Individual Assignment

MY DAILY ROUTINE : APPLICATION OF GRAPH THEORY IN MY DAY prepared by : SEOW XIN YONG (285400) lectured by : PROF. DR. HASLINDA BT IBRAHIM

INTRODUCTION BIODATA OF MYSELF Start from the basic things, my name is Seow Xin Yong. Many people around me often call me Hannah which is my christian name. I am 20 years old, going to be 21 years old. I born in Ipoh, Perak. One special thing of me is that I like to sing and I have an experience of participating in a singing competition. Improve my singing skills is one of the favourite things I like to do. @REALLYGREATPERSON

INTRODUCTION TO GRAPH History of graph theory Once upon a time, there was a man called Leonhard Euler, who lived in Königsberg. There were seven bridges in this city at that time, a question came up to Euler's mind, \"How to cross all the seven bridges without crossing the same bridge?\" This is the start of the graph theory. Graph is a figure which consists of dots (vertices) and lines (edges/loops). Types Simple graph - There is only one edge exists between a pair of of vertices and no loops. graph Multigraph - There are more than one edge exist between a pair of vertices but still no loop(s) exists. Pseudograph - There are multiple edges with no direction and loop(s) exist between a pair of vertices/vertex. Simple directed graph - There may be two edges with opposite directions or one edge with direction exist between a pair of vertices, and no loop(s) exist. Mixed graph - There are multiple edges with and without direction exist in a graph, while loop(s) may also exist. Directed multigraph - There are multiple edges with same direction exist between a pair of vertices and loop(s) exist.

Graph representation The blueprint on the left is my house's blueprint. There are so many things in our lives can be transformed into a graph, such as my house's blueprint. Each and every section of my house can be represented as a dot, which we called vertex in a graph. These vertices can be linked by a line, called edge. Home Sweet Home The blueprint of the house has formed a simple graph which consists of nine vertices and 14 edges. e fg Now, there is a simple graph with ad nine vertices and b ci h 14 edges, yet the vertices are layered. This leads us to another section of graph representation, which is adjacency matrix.

To create an adjacency matrix, we need to put a number which indicates the number of edges exist between a pair of vertices which are labelled. The adjacency matrix of this simple graph is shown below: Meanwhile, a complete graph representation has been done. The adjacency matrix and the graph drawn has represent the graph of the blueprint of my house.

Isomorphism When a graph is having a same structure as another graph, isomorphism of a graph occurs. The vertices of the two graphs are not having the same label and sequence. While the graph which is having the same structure as another graph, called isomorphic graph. There exists an one-to-one correspondence of the vertices of the two graphs. This is a condition for the isomorphism of a graph to occur.

This Simple graph to w v u That x p t q s r Isomorphic graph

Adjacency matrix of Isomorphic graph The adjacency matrix of the isomorphic graph of the blueprint of my house.

HELLO! THE SHORTEST PATH A shortest path is a way travel from one starting point to an ending point by using the value of the weighted edges taken in the calculation. A weighted graph which is a graph with valued edges, is needed to calculate the shortest path.

My day will start off with a wonderful breakfast. To do that, I often go to my favorite Chinese restaurant, which named \"Restaurant Kim Hwa\", to get my breakfast by car. 5 p 5r4 t b 75 6 3 5 4 32 4 3q s 1 c 4 d a 2 The google map above shows the graph of the paths which I can take to reach at restaurant Kim Hwa. In order to reduce the time taken for travel and save time for other routines of the day, I need to identify the shortest path from the graph. The edges in the graph are also weighted with the time taken (minutes) to travel within the pair of vertices.

Road Trip to Kim Hwa In this situation, the value of the edges indicates the time taken in minutes to travel the distance of the corresponding edge. The most common way to find a shortest path is to use Dijkstra's Algorithm. First of all, plot all the points on the map which involves the paths to Restaurant Kim Hwa. Next, draw the paths which connect the vertices, and label the value of time taken in minutes to the paths Create a table which consists of the name of the vertices in the first row, and first column. The travel start from point a, thus we need to put the value of time taken as zero. Since the travel start at point a, the other points which we have not reached yet, will be marked as infinity at this point.

Road Trip to Kim Hwa After that, we need to find edges which has point a as one of the end points. Then, put in the value of the edges to the corresponding point that the edges connected with point a. Hence, choose the point with the least value, and label at the first column at the correspond row. Continue and find the value for the rest of pthoeinw tsayb.y using The shortest path is the value for each points that ends with. Since Restaurant Kim Hwa is point t, the shortest path for it is 13, while the sequence of the points in the path is a-c-p-r-t.

Things to take note The value chosen for each points must be the least value among the values of the paths which can be used to reach at the corresponding point. The paths should consists of an endpoint that has been chosen before.

Graph colouring Graph colouring is a method which assigns two different colours to two points/parts that is adjacent to each other only. This can prevent any two adjacent vertices to have the same colour.

IT'S CLEANING TIME!! Since Christmas is around the corner, it is time to have a clean up time for each corner in the house, in order to celebrate Christmas. I plan to start cleaning after I finish my breakfast. I need to spend my time more wisely to prevent time wasting, since it is a heavy process to clean up each part in the house. There is a way which is useful for me to arrange my clean up schedule, which is \"graph colouring\" method.

I would like to know the least Chromatic Number number of time slots that I need A chromatic number to use for the cleaning process, is the least number so that I can understand clearly of colours used to on how much time I need to assign the spend on. In this case, the least vertices/parts in a number of time slots used is graph. represented by the chromatic number. By using the simple graph that have drawn for the blueprint of my house, the \"graph colouring\" method can be used.

Now, the parts which is adjacent to each other are assigned to different colour. The number of different colours used in the graph of the blueprint of the house is three. Hence, it indicates that at least three time slots should be used for the cleaning process. d f c be a

As a result, I should divide my cleaning time slots into three as shown in the table on the right. Assume that one time slot is using one and a half hour, I can finish my cleaning process in four and a half hour!!

Spanning Tree A SPANNING TREE IS A TREE GRAPH WHICH ALL THE VERTICES EXIST ARE CONNECTED IN A GRAPH. ONE IMPORTANT THING TO TAKE NOTE IS THE VERTICES ARE CONNECTED WITHOUT FORMING A CIRCUIT.

Christmas Carole Via spanning tree In this situation, my family will join the Christmas Carol team in this Christmas. There are nine families we need to visit at the Christmas Eve. Hence, to be able to finish visit these nine families at Christmas Eve, we need to avoid time taken in travelling. By using a 'spanning tree' graph, we could find out a way which travels all the nine families in the shortest time taken.

There nine families 4 which act as the nine vertices in the graph. To find the shortest time to travel these places, we need to put in the value of the time taken in minutes for the edges which connects the vertices in the graph. The weighted graph is formed from the paths which can connect the corresponding pair of vertices. The spanning tree with the minimum weight can be found by using two algorithms, which are Prim's Algorithm and Kruskal's Algorithm

Kruskal's Algorithm First, choose the edges which b 1g has the minimum value of time 1 taken. Be aware of not forming a 1i a circuit. In this case, one minute is the least value among the values of the edges. Hence, the edges with the value one is drawn out. c Next, the second least value is two minutes. The 2 h edges with a value of two 2 and do not form a circuit b g 1 e is drawn out. i 1 1 a cd 2f Last, the edge with value b 2 34 three and do not form a 1 h circuit is drawn out. While g the point which has not been 2 connected is point d. The e least value of edge which 1 connects point d is drawn. 1i a f 2

Prim's Algorithm By using Prim's Algorithm, the edge 1i which connects any of the points which a have been connected is being considered. In this case, point a is the starting point. Among the edges which has point a as one of the endpoint is being considered. The edge with the least value is being chosen, which is the edge connects point a and point i. g Now, the edges which has any points that have drew out as 1 one of the endpoints are being 1i considered. The least value of edge is being chosen, which is a point g. The other edges is being chose by cd using the same method. A minimum 34 spanning tree is being drawn. b2 h The value of the minimum spanning 1g 1 2e tree is the same for both algorithm, 1i which is a 1+1+1+2+2+2+3+4=13. 2f

Reference Bukit kledang indah · 31450 menglembu, perak, malaysia. (n.d.). Bukit Kledang Indah · 31450 Menglembu, Perak, Malaysia. Retrieved December 24, 2021, from https://www.google.com.my/maps/place/Bukit+Kledang+Indah, +31450+Menglembu,+Perak/@4.5713149,101.0232537,15z/d ata=!3m1!4b1!4m5!3m4!1s0x31caebce71404529:0x582729d9 a76fe099!8m2!3d4.5712937!4d101.0320085 Rosen, K. H. (2018). Discrete mathematics and its applications.

Reflection SEOW XIN YONG (285400) When I was doing this assignment, I feel that the most struggling part is brainstorming on how and what i want to do in this assignment. After the brainstorming process, there always will be another struggling thing came out. But when I came to the end, I feel very excited that I climbed another mountain (maybe a small knoll) in my university life. However, I feel really grateful to my lecturer, Prof. Dr. Haslinda who always let us to have these kind of challenging tasks. It maybe suffering sometimes, but after all these are all precious experiences.

THANK YOU !!