Discrete Mathematics(Group D) - Individual Assignment (complete set)

DECEMBER 14, 2021 HO HO HOO~~ Paradigm Mall: Are You Ready for The Preparation of Christmas? VIA GRAPH THEORY Prepared by: Chee Suet Yan 285701 Lecture Name: Prof. Dr. Haslinda Bt Ibrahim

Contents Introduction Graph Representation Shortest Path Graph Coloring Spanning Tree Reflection References

Introduction

ARE YOU TROUBLED Come!! Let's us visit HOW TO CELEBRATE Paradigm CHRISTMAS? PARADIGM MALL Mall A shopping mall where located in Petaling Jaya, Selangor, Malaysia or the shopping mall where near by Kelana Jaya. This mall is owned by the WCT Group which started operations in 2012. For the past few years, it was a popular place where many people shop there. The flow of people who like to shop in this mall has dropped a lot compared with the past. Maybe because of the pandemic COVID-19 or [Decoration of the Mall] other reasons. Since Christmas Day is coming soon, there are many shops have started to sell the christmas clothes, cookies, materials that decorate our Christmas Day. For instance, the shops such as Kaison, Brand Outlet, Marks & Spencer and other. [Overview of Paradigm Mall] pg 1

A Short about GRAPH~ There is a form can represent the graph, which is \" G= (V, E) \" V a nonempty set of vertices (nodes/dots) E a set of edges Each edge has either one or more than one vertices connected with it. It is called \"endpoints\". While an edge is said to join its endpoints There are Simple graph many types of Simple graph Multigraph graphs. Pseudograph For example: Simple directed graph Directed multigraph Mixed graph pg 2

Graph Representation

Graph Representation An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph. There are three important components in graph representation which are : Adjacency Lists Adjacency Matrices Incidence Matrices pg 3

1. What is \"Adjacency Lists\"? Answer : a Adjacency List e b Vertex Adjacent vertices c d a b,c,e a,c,d b a,b b,e c a,d d e 2. What is \"Adjacency Matrices\" & \"Incidence Matrices? b a 0 1 00 1 c e 1 01 10 1 1 000 d 0 1 00 1 1 00 1 0 0 111 1 010 ab 1 1 00 1 000 cd pg 4

Application [Map of Level LG, Paradigm Mall] on Representing Graph Based on the scenario below Suet's father is in charge of buying the kitchen stuff especially the ingredients as the preparation for Christmas. Therefore, he went to the Lotus's which located at the Level LG, Paradigm Mall. List of Ingredients & other Flour, sugar, salt, pepper, yeast, coco powder, icing sugar, vanilla extract, egg, butter, milk Chocolate(chips, bar), Topping (cherries, pineapple, candy cane, truffles, Hershey's Kisses....) Drinks(wine, cocktails, soda drinks, fruit juice) pg 5

Figure 1.0 ab Let's fc Adjacent ListSEE HOW WE USE THE h d g e Figure 1.1 Table below shows the adjacent list based on figure 1.1. Vertex Adjacent vertices a b, f, g, h b a, c, f c b, d, f d c, e, f ed f a,b,c,d,g g a, f,h h a, g pg 6

ab fc h d g e Adjacency Matrices ab c de fgh a 0 1 0001 1 1 b 1 0 1 001 00 c 0 1 0 1 01 00 d 0 0 1 0 1 1 00 e 0 0 0 1 00 0 0 f 1 1 1 1 00 1 0 g 1 00001 0 1 h 1 0 0 0 00 1 0 pg 7

Shortest Path

SHORTEST Definition: Path To find a path of minimum/the least length between two vertices of a connected weighted graph. Notes: Procedure applying Dijkstra’s Algorithm(shortest-path) pg 8

Steps to calculate the \"Shortest Initialize the shortest Path\" by using Dijkstra’s Algorithm path from our start node to another node. After choosing the start node, select one of the nodes that has the shortest distance. Evaluate them by choosing the lowest number(weight/ distance). Repeat the steps 3 to the end to figure out the minimum length(path). pg 9

Suet's Mum is shopping on the floor of Level CC, Paradigm Mall. She uses around 2 hours and 15 minutes to buy clothes as Christmas gifts for her relatives and friends. The shops below are those places she will shop for : pg 10

In order to finish shopping, Suet's Mum has decides the fastest way which can easy for her to buy all the clothes. Hence, she applies the shortest-path using Dijkstra’s algorithm. Figure 2.0 below illustrates the map of Level CC, Paradigm Mall. Paradigm Mall Floor: Level CC MC VOGUE Hush Puppies Footwear Voir 5 6 1 12 8 3 10 10 3 QQ Outlet Figure 2.0 Based on figure 2.0, there are six vertices connected by those edges. Each vertex represents the shops Suet's Mum visit for while the edges represent the distance. pg 11

a b 5 f6 1 12 c 10 83 3 e 10 d a : Voir b : MC VOGUE c : PADINI Concept Store d : Brand Outlet e : QQ Outlet f : Hush Puppies Footwear Working of \"How to find the shortest-path\".... v abcde f a 05∞∞8 6 b 5 17 ∞ 8 6 ef 1177 1166 8 6 8 d 17 16 Shortest Path=AC c 17 Shortest Distance=5+12 =17 pg 12

Graph Coloring

Graph χ (K4)=4 CCoolloorriinngg A coloring of the vertices where the vertices joined by an edge have different colors so that two adjacent vertices are assigned the same color will not happen. *The chromatic The chromatic number number of a of a graph is the least graph G is number of colors denoted by χ (G). needed to make a coloring. χ (G) =4 pg 13

Steps to apply the Choose the vertex with \"Graph Coloring\" the highest degree & select a color on it. Use the same color to color as many vertices as we can without coloring vertices joined an edge of the same color. Select a new color & repeat the previous step for vertices which not already colored. Repeat the step 1 until all the vertices are colored. pg 14

Decorating Your \"popular\" \"Daiso\" \"mr diy\" \"kaison\" Get your \"yubiso\" ideas Here!! pg 15

Notice Started from 6pm otinmweawrdh,etrheistriasftfhice hiasjptahpmeentcimusirnercepenettolhpyelree finish work.... DON'T WORRY, LET ME SCHEDULING THE TIME FOR YOU TO AVOID THIS PROBLEM. Based on the upcoming traffic jam, given that Suet's family are going to end the shopping section but they still left the buying section for decorating their house. Therefore, why not scheduling them which each of them can completely buy all the decoration stuff in the same time but from different shops. Table 1 shows the shops for Suet and her family where can buy the christmas decorating stuff and the person(s) will be responsible going for: Shop(s) Person(s) to in charge to shop for NOTE: S-Suet Kaison B,I D-Suet's Daddy M-Suet's Mummy Popular S B-Suet's Brother I-Suet's Sister-In-Law Daiso M Y-Suet's Younger Brother Mr.DIY D pg 16 YUBISO Y

Map Going to those shops YUBISO Figure 3.0 Figure 3.0 illustrates five vertices & 8 edges that represent the shops and the route, respectively. pg 17

How to transform c this graph into graph d coloring form??? e a b Solution: Represent Vertex : the shops the shops for Suet and her family where can buy the christmas decor ating stuff c Edge : the route Suet's family th at going to shop a d **Each shop is represen ted by a different color** The chromatic number of the graph(C 5) is 3, because the vertices a, b & c must be assigned different colors. To b e see if the graph can be colored with 3 colors, assign blue to a, χ (C 5 ) =3 purple to b & pink to c. Next, d can be colored purple because it is adjacent to c and e. Finally, e can be colored pink again because there is no any edge(s) adjacent to c. This produces a coloring of graph using exactly 4 colors. pg 18

Spanning Tree

What is Spanning Tree?? A subgraph which contains the vertices of the original simple graph. Those vertex connected without forming any simple circuit. Example: Example: The numbers(1,3,4,5,6 & 7) show the weight of each edge. 7 4 spanning tree 5 without any 1 35 circuit 61 5 What is MST = 4+5+3+5+6 distthiamonucecra(esmn)(ci&bnmeso,,itnmshee,ckr,m), Minimum = 23 Spanning The sum of the Tree(MST)?? weights of all the edges in the tree is minimized pg 19

Steps to find the \"Minimum Choose any edge with Spanning Tress\" the minimum weight. Choose a remaining edge with the minimum weight from those edge that is not selected before. Make sure \"NO\" any circuit form during selecting the edge in the subgraph. Based on the original graph, repeat the steps 3 until the subgraph connects the vertices. pg 20

Hey!! Let's see what we share to our neighbors. CMoaorkkises& aSnpdenccaenrdy Homemade cake Self DICYarCdhsristmas irteCjhworiiitcshitnmogau.srSinose!iagLhesbteo'arssotenonojo!of!y pg 21

How to Apply \"Spanning Tree\" method based on the scenario given below ??? Give surprise to those neighbor who live near our house by giving them gifts(e.g Christmas candy, cookies & cards) 53 12 2 46 15 3 8 - My house - Neighbour house pg 22 - Neighbour house - Neighbour house - Neighbour house - Neighbour house - Neighbour house - Neighbour house

53 53 12 12 2 2 56 15 56 15 3 3 8 8 Figure 4.0 Figure 4.1 Figure 4.0 illustrate the map This is the spanning tree going to the neighbor houses where transformed from and the distance(km) from a Figure 4.0. house to another houses. Figure 4.2 The total minimum weight of the spanning tree(MST) Figure 4.2 shows the minimum = 5+1+2+1+3+2+3 spanning tree after choosing the edge with the minimum = 17# weight from those edge that is not selected before. pg 23

Reflection The first thing I would like to say when I know this project is \"Oh my god!! Not again!\". I say that because before that I wasn't know why study Mathematics subject have to do this kind of assignment while not solving the maths questions based on the questions given only. But after I’ve been in contact for a period of time, I found that it’s actually quite interesting. Rather than memorizing the formula and solving questions, the way how we present the knowledges about discrete mathematics in magazine form is more easier for me to understand what am I doing now. The first person I would like to thank for is Prof. Dr. Haslinda Bt Ibrahim because she is the one who gives opportunities to me about an easy way to understand Discrete Mathematics by the application those topics in magazine form. In this project, it let me learn more about how we apply the graph theory in our daily life by using the real life situation and it has a relationship between the things we did daily and theory we learn from this subject.

References Paradigm Mall Official Website, PJ. (January 2012). https://www.paradigmmall.com.my/floor_listing.aspx?fl=g Rosen, Kenneth H.. (2019). Discrete Mathematics and Its Applications (Eighth Edition). Published by McGraw-Hill Education, 2 Penn Plaza, New York, NY 10121. Computing Fundamentals II. (2017, November 16). Section 3b Adjacency Matrix and Incidence Matrix. [Video]. You Tube. https://www.youtube.com/watch?v=BwdtxE9XK6g Power Of Mathematics. (2018, May 19). Shortest Path Problem Using Dijkstra's Algorithm. [Video]. You Tube. https://www.youtube.com/watch?v=cPFgfAjIREk Beena Ballal. (2020, April 13). Dijkstra's Algorithm with example of undirected graph. [Video]. You Tube. https://www.youtube.com/watch?v=U5W8- gGblXs&t=633s EducateYourself. (2016, June 22). Kruskal's Algorithm: Minimum Spanning Tree (MST). [Video]. You Tube. https://www.youtube.com/watch?v=Yo7sddEVONg&t=5s Ms. Hearn. (2017, June 21). Coloring Graphs Part 1: Coloring and Identifying Chromatic Number . [Video]. You Tube. https://www.youtube.com/watch?v=- gOh1aG0_zQ&t=141s