Fluent Essays

Its a Discrete mathematics Question Sheet.. you have to solve it in the “MS WORD FILE I HAVE ATTACHED”Read the questions from there and write answers in the solution part below the questions. I am also attaching some helping material like two ppt slides and a picture.. you can also use it.. quiz is from those parts..it includes graph theories and trees.. please make it easy to understand and clear to read. Questions are on “quiz 3” file and answer on the same file plz quiz3__questions_bbd5c8644c0c9830c3cbcbbc5b14526c.docx week_11_efb7948ba77d99e9f5d3e66ad2d86e3e.pptx week8_lecture_slides_with_examples_8c1dd929286af3868b0497e4407fa989.pdf Unformatted Attachment Preview Mathematics for computing ICT101_Tri1 2020_Test 3 Test3 Weight Test date The Lecture topics Due date Total Question 20\% 29/05/2020 starts Friday 8:00 a.m Chapters 9 and 10.1 30/5/2020 8:00 a.m 5 Please complete below table: 1 2 3 4 First Name: Family Name: Student ID: Email address: Question1 4 Marks In a competition between players X and Y, the first player to win three games in a row or a total of four games wins. How many ways can the competition be played if X wins the first game and Y wins the second and third games? (Draw a tree.) Answer here: Question2 4 Marks Evaluate the following quantities. a. P(6, 6) b. P(6, 3) c. P(6, 1) Solution: Question 3 4 Marks a. How many integers are there from 1000 through 9999? b. How many odd integers are there from 1000 through 9999? c. How many integers from 1000 through 9999 have distinct digits? d. How many odd integers from 1000 through 9999 have distinct digits? e. What is the probability that a randomly chosen four-digit integer has distinct digits? has distinct digits and is odd? Answer here: Question 4 4 Marks An urn contains two blue balls (denoted B1 and B2) and three white balls (denoted W1, W2, and W3). One ball is drawn, its color is recorded, and it is replaced in the urn. Then another ball is drawn and its color is recorded. a. Let B1W2 denote the outcome that the first ball drawn is B1 and the second ball drawn is W2. Because the first ball is replaced before the second ball is drawn, the outcomes of the experiment are equally likely. List all 25 possible outcomes of the experiment. b. Consider the event that the first ball that is drawn is blue. List all outcomes in the event. What is the probability of the event? c. Consider the event that only white balls are drawn. List all outcomes in the event. What is the probability of the event? Solution here: Question5 4 Marks In the graph below, determine whether the following walks are trails, paths, closed walks, circuits, simple circuits, or just walks. a. v1e2v2e3v3e4v4e5v2e2v1e1v0 b. v2v3v4v5v2 c. v4v2v3v4v5v2v4 d. v2v1v5v2v3v4v2 e. v0v5v2v3v4v2v1 f. v5v4v2v1 Solution: ICT101_ Math For Computing THEORY OF GRAPHS AND TREES Theory of Graph I Week 11 Lecture Reference: Chapter 10 of prescribed book: Susanna S. Epp (2020).Discrete Mathematics with Applications, 5th Edition, Cengage CHAPTER 10 THEORY OF GRAPHS AND TREES 2 10.1 Trails, Paths, and Circuits 3 Trails, Paths, and Circuits The subject of graph theory began in the year 1736 when the great mathematician Leonhard Euler published a paper giving the solution to the following puzzle: The town of Königsberg in Prussia (now Kaliningrad in Russia) was built at a point where two branches of the Pregel River came together. It consisted of an island and some land along the river banks. 4 Trails, Paths, and Circuits These were connected by seven bridges as shown in Figure 10.1.1. The Seven Bridges of Königsberg Figure 10.1.1 5 Trails, Paths, and Circuits The question is this: Is it possible for a person to take a walk around town, starting and ending at the same location and crossing each of the seven bridges exactly once? To solve this puzzle, Euler translated it into a graph theory problem. He noticed that all points of a given land mass can be identified with each other since a person can travel from any one point to any other point of the same land mass without crossing a bridge. 6 Trails, Paths, and Circuits Thus for the purpose of solving the puzzle, the map of Königsberg can be identified with the graph shown in Figure 10.1.2, in which the vertices A, B, C, and D represent land masses and the seven edges represent the seven bridges. Graph Version of Königsberg Map Figure 10.1.2 7 Trails, Paths, and Circuits 8 Trails, Paths, and Circuits For ease of reference, these definitions are summarized in the following table: 9 Example 10.1.1 – Notation for Walks a. In the graph below, the notation e1e2e4e3 refers unambiguously to the following walk: v1e1v2e2v3e4v3e3v2. On the other hand, the notation e1 is ambiguous if used by itself to refer to a walk. It could mean either v1e1v2 or v2e1v1. 10 Example 10.1.1 – Notation for Walks continued b. In the graph of part (a), the notation v2v3 is ambiguous if used to refer to a walk. It could mean v2e2v3 or v2e3v3. On the other hand, in the graph below, the notation v1v2v2v3 refers unambiguously to the walk v1e1v2e2v2e3v3. 11 Example 10.1.2 – Walks, Trails, Paths, and Circuits In the graph below, determine which of the following walks are trails, paths, circuits, or simple circuits. a. v1e1v2e3v3e4v3e5v4 c. v2v3v4v5v3v6v2 e. v1e1v2e1v1 b. e1e3e5e5e6 d. v2v3v4v5v6v2 f . v1 12 Example 10.1.2 – Solution a. This walk has a repeated vertex but does not have a repeated edge, so it is a trail from v1 to v4 but not a path. a. v1e1v2e3v3e4v3e5v4 13 Example 10.1.2 – Solution b. This is just a walk from v1 to v5. It is not a trail because it has a repeated edge. c. This walk starts and ends at v2, contains at least one edge, and does not have a repeated edge, so it is a circuit. Since the vertex v3 is repeated in the middle, it is not a simple circuit. 14 Example 10.1.2 – Solution continued d. This walk starts and ends at v2, contains at least one edge, does not have a repeated edge, and does not have a repeated vertex. Thus it is a simple circuit. e. This is just a closed walk starting and ending at v1. It is not a circuit because edge e1 is repeated. f. The first vertex of this walk is the same as its last vertex, but it does not contain an edge, and so it is not a circuit. It is a closed walk from v1 to v1. (It is also a trail from v1 to v1.) 15 Subgraphs 16 Subgraphs 17 Example 10.1.3 – Subgraphs List all subgraphs of the graph G with vertex set {v1, v2} and edge set {e1, e2, e3}, where the endpoints of e1 are v1 and v2, the endpoints of e2 are v1 and v2, and e3 is a loop at v1. 18 Example 10.1.3 – Solution G can be drawn as shown below. There are 11 subgraphs of G, which can be grouped according to those that do not have any edges, those that have one edge, those that have two edges, and those that have three edges. 19 Example 10.1.3 – Solution continued The 11 subgraphs are shown in Figure 10.1.3. Figure 10.1.3 20 Connectedness 21 Connectedness It is easy to understand the concept of connectedness on an intuitive level. Roughly speaking, a graph is connected if it is possible to travel from any vertex to any other vertex along a sequence of adjacent edges of the graph. The formal definition of connectedness is stated in terms of walks. 22 Connectedness If you take the negation of this definition, you will see that a graph G is not connected if, and only if, there exist two vertices of G that are not connected by any walk. 23 Example 10.1.4 – Connected and Disconnected Graphs Which of the following graphs are connected? 24 Example 10.1.4 – Solution The graph represented in (a) is connected, whereas those of (b) and (c) are not. To understand why (c) is not connected, recall that in a drawing of a graph, two edges may cross at a point that is not a vertex. Thus the graph in (c) can be redrawn as follows: 25 Connectedness Some useful facts relating circuits and connectedness are collected in the following lemma. 26 Connectedness A connected component of a graph is a connected subgraph of largest possible size. 27 Example 10.1.5 – Connected Components Find all connected components of the following graph G. 28 Example 10.1.5 – Solution G has three connected components: H1, H2, and H3 with vertex sets V1, V2, and V3 and edge sets E1, E2, and E3, where V1 = {v1, v2, v3}, V2 = {v4}, E1 = {e1, e2}, E2 = V3 = {v5, v6, v7, v8}, E3 = {e3, e4, e5}. 29 Euler Circuits_ we will discuss it next week 30 ICT101_ Math For Computing Theory of Graph I Week 8 Lecture_ Make up class 6/5/2020 Reference: Chapter 1,9 of prescribed book: Susanna S. Epp (2020).Discrete Mathematics with Applications, 5th Edition, Cengage CHAPTER 9 COUNTING AND PROBABILITY CHAPTER 1 SPEAKING MATHEMATICALLY Copyright © Cengage Learning. All rights reserved. 3 1.4 The Language of Graphs Copyright © Cengage Learning. All rights reserved. 4 The Language of Graphs Imagine an organization that wants to set up teams of three to work on some projects. In order to maximize the number of people on each team who had previous experience working together successfully, the director asked the members to provide names of their previous partners. 5 The Language of Graphs This information is displayed below both in a table and in a diagram. 6 The Language of Graphs From the diagram, it is easy to see that Bev, Cai, and Flo are a group of three previous partners, and so it would be reasonable for them to form one of these teams. The drawing below shows the result when these three names are removed from the diagram. 7 The Language of Graphs This drawing shows that placing Hal on the same team as Ed would leave Gia and Ira on a team where they would not have a previous partner. However, if Hal is placed on a team with Gia and Ira, then the remaining team would consist of Ana, Dan, and Ed, and everyone on both teams would be working with a previous partner. 8 The Language of Graphs Drawings such as these are illustrations of a structure known as a graph. The dots are called vertices (plural of vertex) and the line segments joining vertices are called edges. As you can see from the first drawing, it is possible for two edges to cross at a point that is not a vertex. Note also that the type of graph described here is quite different from the “graph of an equation” or the “graph of a function.” 9 The Language of Graphs In general, a graph consists of a set of vertices and a set of edges connecting various pairs of vertices. The edges may be straight or curved and should either connect one vertex to another or a vertex to itself, as shown below. 10 The Language of Graphs In this drawing, the vertices are labeled with v’s and the edges with e’s. When an edge connects a vertex to itself (as e5 does), it is called a loop. When two edges connect the same pair of vertices (as e2 and e3 do), they are said to be parallel. It is quite possible for a vertex to be unconnected by an edge to any other vertex in the graph (as v5 is), and in that case the vertex is said to be isolated. 11 The Language of Graphs The formal definition of a graph follows. 12 Example 1.4.1 – Terminology Consider the following graph: a. Write the vertex set and the edge set, and give a table showing the edge-endpoint function. 13 Example 1.4.1 – Terminology continued b. Find all edges that are incident on v1, all vertices that are adjacent to ν1, all edges that are adjacent to e1, all loops, all parallel edges, all vertices that are adjacent to themselves, and all isolated vertices. 14 Example 1.4.1 – Solution a. vertex set = {v1, v2, v3, v4, v5, v6} edge set = {e1, e2, e3, e4, e5, e6, e7} edge-endpoint function: 15 Example 1.4.1 – Solution continued b. e1, e2, and e3 are incident on v1. v2 and v3 are adjacent to v1. e2, e3, and e4 are adjacent to e1. e6 and e7 are loops. e2 and e3 are parallel. v5 and v6 are adjacent to themselves. v4 is an isolated vertex. 16 Example 1.4.2 – Drawing More Than One Picture for a Graph Consider the graph specified as follows: vertex set = {v1, v2, v3, v4} edge set = {e1, e2, e3, e4} edge-endpoint function: 17 Example 1.4.2 – Drawing More Than One Picture for a Graph continued Both drawings (a) and (b) shown below are pictorial representations of this graph. 18 Example 1.4.3 – Labeling Drawings to Show They Represent the Same Graph Consider the two drawings shown in Figure 1.4.1. Label vertices and edges in such a way that both drawings represent the same graph. Figure 1.4.1 19 Example 1.4.3 – Solution Imagine putting one end of a piece of string at the top vertex of Figure 1.4.1(a) (call this vertex v1), then laying the string to the next adjacent vertex on the lower right (call this vertex v2), then laying it to the next adjacent vertex on the upper left (v3), and so forth, returning finally to the top vertex v1. Call the first edge e1, the second e2, and so forth, as shown below. 20 Example 1.4.3 – Solution continued Now imagine picking up the piece of string, together with its labels, and repositioning it as follows: 21 Example 1.4.3 – Solution continued This is the same as Figure 1.4.1(b), so both drawings represent the graph with vertex set {v1, v2, v3, v4, v5}, edge set {e1, e2, e3, e4, e5}, and edge-endpoint function as follows: 22 Examples of Graphs 23 Example 1.4.4 – Using a Graph to Represent a Network Telephone, electric power, gas pipeline, and air transport systems can all be represented by graphs, as can computer networks—from small local area networks to the global Internet system that connects millions of computers worldwide. Questions that arise in the design of such systems involve choosing connecting edges to minimize cost, optimize a certain type of service, and so forth. 24 Example 1.4.4 – Using a Graph to Represent a Network continued A typical network, called a hub-and-spoke model, is shown below. 25 Examples of Graphs A directed graph is like an (undirected) graph except that each edge is associated with an ordered pair of vertices rather than a set of vertices. Thus each edge of a directed graph can be drawn as an arrow going from the first vertex to the second vertex of the ordered pair. 26 Example 1.4.6 – Using a Graph to Represent Knowledge In many applications of artificial intelligence, a knowledge base of information is collected and represented inside a computer. Because of the way the knowledge is represented and because of the properties that govern the artificial intelligence program, the computer is not limited to retrieving data in the same form as it was entered; it can also derive new facts from the knowledge base by using certain built-in rules of inference. For example, from the knowledge that the Los Angeles Times is a big-city daily and that a big-city daily contains national news, an artificial intelligence program could infer that the Los Angeles Times contains national news. 27 Example 1.4.6 – Using a Graph to Represent Knowledge continued The directed graph shown in Figure 1.4.2 is a pictorial representation for a simplified knowledge base about periodical publications. Figure 1.4.2 28 Example 1.4.6 – Using a Graph to Represent Knowledge continued According to this knowledge base, what paper finish does the New York Times use? Meaning of Finish: complete the manufacture or decoration of (a material, object, or place) by giving it an attractive surface appearance. 29 Example 1.4.6 – Solution The arrow going from New York Times to big-city daily (labeled “instanceof”) shows that the New York Times is a big-city daily. The arrow going from big-city daily to newspaper (labeled “is-a”) shows that a big-city daily is a newspaper. The arrow going from newspaper to matte (labeled “paperfinish”) indicates that the paper finish on a newspaper is matte. Hence it can be inferred that the paper finish on the New York Times is matte. 30 Examples of Graphs 31 Example 1.4.8 – Degree of a Vertex Find the degree of each vertex of the graph G shown below. 32 Example 1.4.8 – Solution deg(v1) = 0 since no edge is incident on v1 (v1 is isolated). deg(v2) = 2 since both e1 and e2 are incident on v2. deg(v3) = 4 since e1 and e2 are incident on v3 and the loop e3 is also incident on v3 (and contributes 2 to the degree of v3). 33 Example 1.4.9 – Using a Graph to Color a Map Imagine that the diagram shown below is a map with countries labeled A–J. Show that you can color the map so that no two adjacent countries have the same color. 34 Example 1.4.9 – Solution Notice that coloring the map does not depend on the sizes or shapes of the countries, but only on which countries are adjacent to which. So, to figure out a coloring, you can draw a graph, as shown below, where vertices represent countries and where edges are drawn between pairs of vertices that represent adjacent countries. 35 Example 1.4.9 – Solution continued Coloring the vertices of the graph will translate to coloring the countries on the map. As you assign colors to vertices, a relatively efficient strategy is, at each stage, to focus on an uncolored vertex that has maximum degree, in other words that is connected to a maximum number of other uncolored vertices. 36 Example 1.4.9 – Solution continued If there is more than one such vertex, it does not matter which you choose because there are often several acceptable colorings for a given graph. 37 Example 1.4.9 – Solution continued For this graph, both C and H have maximum degree so you can choose one, say, C, and color it, say, blue. Now since A, F, I, and J are not connected to C, some of them may also be colored blue, and, because J is connected to a maximum number of others, you could start by coloring it blue. 38 Example 1.4.9 – Solution continued Then F is the only remaining vertex not connected to either C or J, so you can also color F blue. The drawing below shows the graph with vertices C, J, and F colored blue. 39 Example 1.4.9 – Solution continued Since the vertices adjacent to C, J, and F cannot be colored blue, you can simplify the job of choosing additional colors by removing C, J, and F and the edges connecting them to adjacent vertices. The result is shown in Figure 1.4.4a. Figure 1.4.4(a) 40 Example 1.4.9 – Solution continued In the simplified graph again choose a vertex that has a maximum degree, namely H, and give it a second color, say, gray. Since A, D, and E are not connected to H, some of them may also be colored gray, and, because E is connected to a maximum number of these vertices, you could start by coloring E gray. 41 Example 1.4.9 – Solution continued Then A is not connected to E, and so you can also color A gray. This is shown in Figure 1.4.4b. Figure 1.4.4(b) 42 Example 1.4.9 – Solution continued The drawing below shows the original graph with vertices C, J, and F colored blue, vertices H, A, and E, colored gray, and the remaining vertices colored black. You can check that no two adjacent vertices have the same color. 43 Example 1.4.9 – Solution continued Translating the graph coloring back to the original map gives the following picture in which no two adjacent countries have the same color. 44 ... Purchase answer to see full attachment