Archive for the ‘Discrete Mathematics’ Category

Problem 1080

Determine whether the following statement makes sense or does not make sense, and explain your reasoning.

 

Starting from my home, I need to go to the post office, the bank, the medical clinic, and the dry cleaners. Because my goal is to run errands and return home using the shortest route, I need to determine the minimum spanning tree.

 

Solution:-

 

The statement does not make sense, because a route that visits every vertex once and returns to the starting point is a Hamilton circuit.

Problem 1079

Use Kruskal’s Algorithm to find the minimum spanning tree for the weighted graph. Give the total weight of the minimum spanning tree.

D5

Solution:-

 

Step 1. Find the edge with the smallest weight.

Select edge AB (weight: 72)

 

Step. Find the next-smallest edge in the graph.

Select edge CD (weight : 77).

 

Step 3. Find the next-smallest edge in the graph that does not create a circuit.

Select edge AC (weight: 81).

 

There three edges create a subgraph that contains all of the graph’s four vertices, is connected, and contains no circuits. Furthermore, since the edges with the smallest weights were chosen, the resulting spanning tree should be the minimum spanning tree for the weighted graph.

The following tree matches the shape of the minimum spanning tree.

D6

From the figure, we see that the total weight of the minimum spanning tree is

72 + 77 +81 = 230

 

Problem 1078

Find a spanning tree for the connected graph.

D3

Solution:-

 

Given a graph, a sub graph is a set vertices and edges chosen from those of the original graph. A graph can have many subgraphs. A subgraph that contains all of a connected graph’s vertices, is connected, and contain no circuits is called a spanning tree. A graph can have many spanning trees.

The original graph is a connected graph with 6 vertices and 8 edges.

The spanning tree of a graph with n vertices has n – 1 edges.

 

Therefore , the spanning tree of the original graph must have 6 – 1 = 5 edges. Since the original graph has 8 edges, 3 edges will need to be removed to create the spanning tree.

 

Remove three edges to create one possible spanning tree, as shown to the right. Notice that each edge is a bridge and no circuits are present.

D4

Problem 1077

Determine whether the graph is a tree. If the graph is not a tree, given the reason why.

D2

Solution:-

 

Definition and Properties of a Tree

A tree is  a graph that is connected and has no circuits. All trees have the following properties:

a. There is one and only one path joining any two vertices.

b. Every edge is a bridge.

c. A tree with n vertices must have n -1 edges.

 

First, determine whether the graph is connected. Since each of the five vertices, A, B, C, D, and E, can be reached from all other vertices, the given graph is connected.

 

Next, determine whether there are any circuits. Since there is one and only one path joining any two of the graph’s vertices, there are no circuits.

 

The graph is connected and has no circuits. Therefore, the graph is a tree. There is one and only one path joining any two vertices. Every edge is a bridge. It has 5 vertices and 5 -1, or 4, edges.

 

 

 

Problem 1076

Determine whether the graph is a tree. If the graph is not a tree, give the reason why.

D1

Solution:-

 

A tree is a graph that is connected and has no circuit. All trees have the properties listed below.

a. There is no one and only one path joining any two vertices.

b.Every edge is a bridge.

c.A tree with n vertices must have n – 1 edges.

 

First, determine whether the given graph is connected. All vertices A, B, C, and D can be reached from all other vertices, so the graph is connected.

Next, determine whether the graph has circuits. The graph contains the circuit A, B, C, D.

There is more than one path connecting each vertex to the other vertices.

 

The graph is connected, but it has a circuit. Therefore, the graph is not a tree. Note that is any one of the edges were removed, the circuit would be broken and the graph would be a tree.

 

 

Problem 1075

Determine whether the following statement is true or false.

A tree is a complete graph.

 

Solution:-

 

The statement is false. A tree does not have an edge between each pair of its vertices.

 

 

 

Problem 1074

Fill in the blank so the resulting statement is true.

A tree that is created from another connected graph and that contains all of the connected graph’s vertices, is connected, and contains no circuits is called a/an……………………….tree.

 

Solution:-

 

Spanning .

 

 

Problem 718

Find the eccentricity of the ellipse   \frac{x^{2}}{25}+\frac{(y-7)^{2}}{5}=1

 

Solution:-

 

eccentricity of the ellipse = \frac{c}{a}

c =   \sqrt{a^{2}-b^{2}}

c =  \sqrt{25-5}

c= \sqrt{20}

c =   2\sqrt{5}

eccentricity = \frac{2\sqrt{5}}{5}

 

Problem 713

Find  (x3 – 5x2 -2) ÷ (x-1) using synthetic division.

 

Solution:-

 

x – 1 │  1  -5  0  -2

│  0 1 -4 -4

——————-

1  -4 -4 -6

 

x2 – 4x -4 +\frac{-6}{(x-1)}

 

Problem 594

Find the four geometric means between 4 and 972

 

Solution:-

 

4r^{5} = 972

r^{5}  = 243

r = 3

So the  four geometric means are 12, 36, 108 and 324.