Deck 7: The Cost of Being Connected

Question 1

Consider the network shown below; draw two different spanning trees for the network.

Answer 1

Here are two possible choices. There
are many more!

Question 2

Consider the network shown below; what is the redundancy of the network?

Answer 2

2

Question 3

A city consists of three boroughs, and each borough has five neighborhoods and each neighborhood consists of ten houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $100 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses in the city together so that there are
no redundancies? Hint: Think of each house as a vertex.

Answer 3

$14900

Question 4

Consider the network shown in below; how many edges are bridges?

Question 5

How many different spanning trees can be found in the following network?

Question 6

Consider the network shown below; draw the minimum spanning tree for this network by applying Kruskal's algorithm.

Question 7

Consider the network shown below; draw the minimum spanning tree for this network by applying Kruskal's algorithm.

Question 8

Is it possible to have a tree in which every vertex has even degree? Explain.

Question 9

What number of edges will be bridges in a tree which has fifteen vertices?

Question 10

A local telecommunications company is planning on placing fiber-optic cables along existing roads to network together several towns in a remote area of upstate Vermont. The table below gives the distance in kilometers between each of the towns via these roads. If it costs the company $800 per kilometer to lay down the cable, then find the cost of the cheapest network connecting all of the towns.

Question 11

Consider the network shown below; draw two different spanning trees for the network.

Question 12

Which of the graphs shown below are not trees?

Question 13

Is every graph with 8 vertices and 7 edges a tree? Explain.

Question 14

What is the redundancy of the complete graph K5 ?

Question 15

A local telecommunications company is planning on placing fiber-optic cables along existing roads to network together several towns in a remote area of upstate Vermont. The table below gives the distance in miles between each of the towns via these roads. If it costs the company $1000 per mile to lay down the cable, then find the cost of the cheapest network connecting all of the towns.

Question 16

A connected graph contains 25 edges and every edge in the graph is a bridge. How many vertices does
the graph contain?

Question 17

Which of the graphs shown below are trees?

Question 18

How many different spanning trees can be found in the following network?

Question 19

Consider the network shown in problem 4; how many edges are not bridges?

Question 20

A city consists of four boroughs, and each borough has six neighborhoods and each neighborhood consists of twenty houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $75 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses together so that there are no
redundancies? Hint: Think of each house as a vertex.

Question 21

Which of the following scenarios results in a graph which is a tree?

A) A connected graph with 5 vertices and 4 edges.
B) A graph in which every edge is a bridge.
C) A graph in which every pair of vertices has one unique path which connects them.
D) All of the above.
E) None of the above.

Question 22

Consider the Graph K shown below; which of the figures shown below are spanning trees of Graph K?

A) figure 1
B) figure 2
C) figure 3
D) All of the figures.
E) None of the above.

Question 23

A city consists of five boroughs, and each borough has four neighborhoods and each neighborhood consists of ten houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $50 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses together so that there are no redundancies? Hint: Think of each house as a vertex.

A) $9950
B) $10500
C) $12500
D) $13500
E) None of the above.

Question 24

What is the redundancy of the graph shown below?

A) 6
B) 7
C) 8
D) 9
E) None of the above.

Question 25

Consider the graph shown below; what is the weight of the minimum spanning tree of the graph?

A) 61
B) 68
C) 72
D) 76
E) None of the above.

Question 26

In the graph shown below, how many edges are bridges?

A) 3
B) 4
C) 5
D) 6
E) None of the above.

Question 27

What is the redundancy of the complete graph K25 ?

A) 275
B) 276
C) 300
D) 25! - 1
E) None of the above.

Question 28

Every tree must have at least two vertices of degree one.

A) This statement is always true.
B) This statement is always false.
C) This statement is only true if there are more than four vertices.
D) This statement is only false if there are more than four vertices.
E) None of the above.

Question 29

How many different spanning trees are found in the network shown below?

A) 1
B) 2
C) 3
D) 4
E) None of the above.

Question 30

Which of the following scenarios results in a graph which is not a tree?

A) A graph with 5 vertices and 6 edges.
B) A graph in which every edge is a bridge.
C) A graph in which every pair of vertices has one unique path which connects them.
D) All of the above.
E) None of the above.

Question 31

Which of the graphs below are not trees?

A) Graph I
B) Graph 2
C) Graph 4
D) Both Graph 1 and Graph 4
E) None of the above.

Question 32

How many different spanning trees are found in the network shown below?

A) 4
B) 8
C) 12
D) 16
E) None of the above.

Question 33

Consider a connected graph with n vertices; if n - 1 of the vertices have degree 1, then the graph is a tree.

A) This statement is always true.
B) This statement is always false.
C) This statement is always true if and only if one vertex has degree n - 1.
D) This statement is only false if and only if one vertex has degree n - 1.
E) None of the above.

Question 34

Which of the graphs below are trees?

A) Graph 1
B) Graph 2
C) Graph 3
D) Graph 2 and Graph 3
E) None of the above.

Question 35

A city consists of five boroughs, and each borough has three neighborhoods and each neighborhood consists of ten houses. You have been hired to run a fiber-optic cable, networking all of the houses to each other. No matter the length, it costs $50 to connect any one house to any other house. Based on all of this information, what will it cost to network all of the houses together so that there are no redundancies? Hint: Think of each house as a vertex.
(a) $7450
(b) $7500
(c) $8000
(d) $8500
(e) None of the above.

Question 36

Consider Graph K shown below; which of the figures shown below are not spanning trees of Graph K?

A) figure 1
B) figure 2
C) figure 3
D) Both figure 2 and figure 3 .
E) None of the above.

Question 37

The local town board has authorized the creation of a new sub-division of five houses. The public works department is given the duty of installing underground electric wires which will network together the houses with the nearby electric sub-station. The table below gives the cost in hundreds dollars of installing wires between each of the houses and the sub-station. Find the cost of the cheapest network connecting the five houses with the sub-station.

A) $7100
B) $7200
C) $8800
D) $9600
E) None of the above.

Question 38

Consider the graph shown below; what is the weight of the minimum spanning tree of the graph?

A) 8.3
B) 9.2
C) 11.2
D) 11.6
E) None of the above.

Question 39

In the graph shown below, how many edges are bridges?

A) 1
B) 2
C) 3
D) 4
E) None of the above.

Question 40

The local town board has authorized the creation of a new sub-division consisting of five houses. The public works department is given the duty of installing underground electric wires which will network together the houses with a nearby electric sub-station . The table below gives the coast in hundreds dollars of installing wires between each of the houses and sub-station . Find the coast og the cheapest network connecting the five houses with the sub-station.

A) $3200
B) $3800
C) $4300
D) $5700
E) None of the above.