Chapter 7 Mathematics of Networks

ESSENTIAL QUESTIONS:

Section 7.1: How is a tree different from other graphs?

Section 7.2: What is a spanning tree?

Section 7.3: How do you use Kruskal’s Algorithm to find Minimum Spanning Tree (MST)?

Section 7.4: How can you find the shortest network connecting 3 points?

WORD WALL:

INTERIOR JUNCTION RULE

INTERIOR JUNCTION POINT

JUNCTION POINT

KRUSKAL’S ALGORITHM

MINIMUM NETWORK PROBLEMS

MINIMUM SPANNING TREE (MST)

NETWORK

REDUNDANCY

SHORTEST NETWORK

SHORTEST NETWORK RULE

SPANNING TREE

STEINER POINT

STEINER TREE

SUBGRAPH

TREE

HOMEWORK:

7.1: p. 259 # 1, 2, 3 – 7 (odd)

7.2: p. 260 #11 – 12 (all), 16 – 18 (all)

7.3: pp. 260 – 1 # 19 – 25 (odd)

7.4: DAY ONE: Triangle Worksheet and DAY TWO: p. 262 # 27-34

Section 7.1: Tree

What is a NETWORK? Any CONNECTED GRAPH

Vertices of networks are often called nodes or terminals and represent “objects”
cities, subway stations, computer servers, people, etc

  • Edges of networks are called links and indicated connections among objects
    airline routes, rail lines, internet connections, social connections, etc

CHAPTER THEME: Finding optimal networks that connect a set of points the cheapest

OPTIMAL NETWORK GOALS:

1)Connect all the “TERMINALS” = Vertices

  • “CONNECT” DOESN’T HAVE TO MAKE an euler/ hamilton path or circuit

2)Total cost (length) of the network as small as possible (optimal)

Example Network Problem: The weighted graph represents a system of roads connecting buildings of a company’s headquarters. The company is planning to upgrade its fiber optic cable through underground lines connecting its servers. The weights represent cost in millions of dollars to upgrade these cables between each building. The goal for the company is to find a network that utilizes the existing network of roads; connects all the buildings together; has the least cost.

Key Term Requirements of network in the example:

1)SUBGRAPH: edges come from the original graph

2)SPAN: must include all vertices of the original graph

3)MINIMAL: total weight of the network must be as small as possible “OPTIMAL”

  • Cannot have a circuit
  • Information, cars, people, etc are allowed to travel along network in both directions

EXAMPLE: Based on the original graph, draw different examples of subgraphs and spans.


SPECIFIC TYPE OF NETWORK:

TREE: a network (connected graph) with no circuits of any length

Which of the following graphs a – h represents a tree: Why or why not?

Observation Questions for Graphs that are TREES:

1)Is there a relationship between edges and vertices?

ONE MORE VERTEX THAN EDGE or EDGES ONE LESS THAN VERTICES

2)Is there a special term you can use to describe the edges used?

EVERY EDGE IS A BRIDGE

SPANNING TREE:

A subgraph of a network that connects all the vertices and has no circuits

“tree” inside of a graph using all vertices

EXAMPLE: For the given graph, find a spanning tree.

PROPERTIES # 1 – 3 OF TREES:

PROPERTY #1:

  • In a tree, there is one and only onePATH joining any two vertices.
  • If there is one and only one path joining any two vertices of a graph, the graph must be a tree.

Path joining any two vertices = connected graphone and only one = no circuits exist

PROPERTY #2: IE no circuits

  • In a tree, every edge is a BRIDGE.
  • If every edge of a graph is a bridge, then the graph must be a tree.

Every edge is bridge = no circuits because you can’t get back to any vertices to complete a circuit.

PROPERTY #3:

  • A tree with N vertices has N-1EDGES.
  • If a NETWORK has N vertices and N-1 edges, then it must be a tree.

TREE/ NETWORK = connected

“Number of Edges is one less than the number of vertices in a tree”

Practice Problems: A graph G has no loops or multiple edges. Identify if the graph (1) ALWAYS is a tree, (2) NEVER is a tree, or (3) SOMETIMES is a tree.

1)G has 4 vertices and 3 edges.

SOMETIMES

2)G is connected with 4 vertices and 3 edges

ALWAYS

3)G has 5 vertices and 5 edges.

NEVER

4)G has 5 vertices and 4 bridges.

ALWAYS

5)G has 10 vertices and 9 edges.

SOMETIMES

6)G has 10 vertices and 11 edges.

NEVER

7)G has 12 vertices and 11 bridges.

ALWAYS

8)G is connected with 8 vertices and every vertex has degree 7.

NEVER


Section 7.2: Spanning Tree

SPANNING TREE: a subgraph of a network that connects all the vertices and has no circuits

1A. Is the following graph a tree? Why?

1b. Find a spanning tree in the graph.

2A. Is the following graph a tree? Why?

2b. Find a spanning tree in the graph.

The graph itself is a spanning tree because it is a tree

PROPERTY #4 of Trees:

  • If a network (CONNECTED GRAPH) has V vertices and E edges, then E ≥ V -1.

In a connected graph, number of edges is greater than or equal to number of vertices minus 1.

REDUNDANCY = Difference of EDGES and VERTICESplusONE
R = E – V + 1

Number of edges to remove from network to create tree

  • If E = V -1, then the network is a tree; if M V -1, the network has circuits and is not a tree.

If R = 0;network is tree

If R > 0;network is not a tree

If Redundancy is positive, (R > 0), then many SPANNING TREES exist in network

However, It doesn’t identify which edges must be removed.

How do you find spanning trees?.

1) Your goal is to remove R edges to create a tree.
(Break Up Circuits)

2) DO NOT remove edges that are Bridges.

EXAMPLE #1:

1)How many edges do you need to remove?

R=1 = 8 – (8 – 1) Circuit = CDHC; CD, HC, HD

2)How many possible spanning trees exist in this graph?
3 remove one edge from circuit of 3 lines

EXAMPLE #2: How many edges do you need to remove?R = 2 = 9 – 8 + 1

2 EDGES TO REMOVE

Notice there are two separate circuits to break up CDHC and DEFGD which you need to remove one edge from each to make R =0

METHOD #1: FIND BY DRAWING

REMOVE CD / REMOVE CH / REMOVE HD
CD, DE / CH, DE / HD, DE
CD, EF / CH, EF / HD, EF
CD, FG / CH, FG / HD, FG
CD, GD / CH, GD / HD, GD

METHOD #2: How might we know when we’ve found all spanning trees?

Circuit #1 = 3 edges Circuit #2 = 4 edges
Multiplication Rule: Remove 1 edge from Circuit #1 and Remove 1 edge from Circuit #2

= 3 * 4 = 12

EXAMPLE #3:How many edges do you need to remove? R = 2 = 9 – 8 + 1

2 EDGES TO REMOVE

Notice there are two separate circuits to break up CDHC and DEFGHD which you need to remove one edge from each of those circuits to make R =0
PROBLEM: HD is shared by both circuits

METHOD #1: FIND BY DRAWING

REMOVE CD / REMOVE CH / REMOVE HD
CD, DE / CH, DE / HD, DE
CD, EF / CH, EF / HD, EF
CD, FG / CH, FG / HD, FG
CD, GD / CH, GD / HD, GD
CD, DH / CH, HD

METHOD 2: How might we know when we’ve reached finding all spanning trees?

METHOD 2A: REMOVE THE ONE CASE OF HD CHOSEN TWICE: 3 * 5 – 1 = 14

METHOD 2B: Break it Into Cases:

Case #1: Exclude HD and then can exclude any of other 6 edges from circuits = 1 *6 = 6

Case #2: Must Keep HD; Circuit #1 has 2 edges and Circuit #2 has 4 edges = 2 * 4 = 8

SPANNING TREE PRACTICE

For each of the below graphs, find the total number of possible spanning trees.


Section 7.3: Kruskal’s Algorithm

MINIMUM SPANNING TREE (MST):

a spanning tree of a weighted network with the least total weight

How many spanning trees exist in each of the given networks?

Network #1:Network #2:Network #3:

(3*5 – 1) = 14 (3*3 – 1) (4) = 32(3*4-1)(3*4-1) = 121

How can we find the minimum spanning tree without checking all of the possible spanning trees?

Kruskal’s Algorithm for N vertices on a Network.

Step #1: Pick the cheapest edge available.

  • In case of a tie, randomly pick one edge.
  • Mark it or somehow identify you chose it.

REPEAT: Pick the next cheapest link or edge available and mark it.

  • RULE #1: Cannot make a Circuit by choice
  • RULE #2: Stop once you’ve chosen N-1 Edges
  • RULE #3: Vertices are allowed to have any degree > 0

Example: The following graph represents roads connecting seven towns in a developing jungle region that is planning to lay fiber-optic cable. The cost of laying the fiber optic cable is represented by the weights of graph. Let’s find the minimum spanning tree (MST) using Kruskal’s Algorithm.

GF = 42, BD = 45, AD = 49, DG = 51, CAN’T USE AB, CD = 53, CE = 59

Positives of Kruskal’s Algorithm:

It’s easy to implement – it doesn’t require a lot of complex steps

It’s an efficient algorithm – it doesn’t take long to complete.

It’s an optimal algorithm – will always find a minimum spanning tree

EXAMPLE PROBLEMS:


7.4 Introduction Triangles

GEOMETRY - TRIANGLES REVIEW:

BASIC TRIANGLE RELATIONSHIPS: ANGLES v. SIDE LENGTHS

LONGEST Side of a triangle is opposite(across from) the BIGGESTangle

SHORTEST Side of a triangle is opposite(across from) the SMALLESTangle

MIDDLESide of triangle is opposite (across from) the MIDDLE angle.

Triangles are Not Drawn to Scale!!

RIGHT TRIANGLES:

State the Pythagorean Theorem

Label the Right Triangle based on your statement.

a2 + b2 = c2

PRACTICE: Find the value of the missing sidex. (Triangles not drawn to scale)

SPEICAL RIGHT TRIANGLES: 300 – 600 – 900

ALL 300 – 600 – 900 triangles are SIMILAR and the relationship of the sides are proportional.

Hint: Place a 1 and 2 on a triangle and use Pythagorean Theorem

Hypotenuse = Opposite the 900 = 2

Short Leg = Opposite the 300 = √3 = Pythagorean Theorem

Long Leg = Opposite the 600 = 1

To move between sides because sides are always proportional.

Bigger to Smaller = DivideSmaller to Bigger = Multiply

Always go through the “1” side otherwise 2 to √3 requires using a fraction value.

PRACTICE: Use your knowledge of 300 – 600 – 900 to find all side lengths.


GENERAL TRIANGLE PRACTICE

IDENTIFY missing information as largest, smallest, or middle angles and lengths.

  • If possible, provide an exact value for missing measurement.
  • If not possible, then provide approximate angle or side values with inequalities.


Section 7.4: The Shortest Network Connecting Three Points

Minimum Spanning Tree (MST): The spanning tree of a given network that has the least weight

  • Subgraph
  • No Circuits
  • Connected Graph

MST is the OPTIMAL(shortest) way to connect a set of vertices based on the assumption that all CONNECTIONS(EDGES) should belong to the links of the ORIGINALNETWORK. .

  • SPANNING part of the definition

Example: Consider the network (right) that describes 3 isolated towns (A, B, C) which are equidistant from each other and located in the heart of the Australian outback. The towns are connected by three unpaved straight roads as described by the edges. What is the minimum spanning tree solution to this network?

Pick any 2 sides and they add up to be 1000 miles.

Could there be a shorter network than the Minimum Spanning Tree (MST) in a graph?

What would we need to do to the graph to check for shorter answer?

  • You must be able to create new vertices and new edges to use.
  • You need to be able to measure these new edges.
  • This new network must have less weight than the MST. (Shorter than 1000)

SHORTEST NETWORK= the network of all vertices that has the SMALLESTtotal weight without RESTRICTION on the edges you can use or create.

  • Example: Do power cables have to follow a roads OR highways?

It might be possible to do this in the outback because of the flat land and not necessary to follow along the current road system. Or in other situations where construction might not be limited by existing systems.

EXAMPLE #1 OF ADDING NEW VERTEX, T, AND EDGE: Vertex T is at the midpoint of the edge BC and creates edge TA.. (T-NETWORK)

What is the length of TA?

AC = 500

TC = 250 = 500/2

TA = 250(√3) = 433

What is the total weight of the T-Network (AT, BT, CT)?

Total Weight = 250 + 250 + 433 = 933

Is this T-Network shorter than the MST?

T-network is shorter than the MST (933 v. 1000)

EXAMPLE #2 OF ADDING NEW VERTEX, Y, AND EDGES: Put a new vertex, Y, in the exact middle of the triangle and create edges YA, YB, and YC. (Y-NETWORK).

What is the length of YA, YB, and YC?

YA = YB = YC each one Is the same value

XC = 250

YX = 250 ÷ (√3) = 144.34

YC = 2•YX = 288.68

What is the total weight of the Y-Network (YA, YB, and YC)?3•288.68 = 866.04

Is this Y-Network shorter than the MST and the T-Network? Y-network is shorter than both

What is important about the angles the edges of the Y-network form? __1200______

Shortest Network Key Terms:

  • Junction Point:any point where two or more edges of the network come together

MST = AT-NETWORK = TY-NETWORK =Y

  • Native Junction Point: a junction point that is located at an original vertices of the network

A

  • Interior Junction Point: a nonnative junction point located somewhere other than at one of the original vertices of the network

T, Y; INTERIOR = MUST BE CREATED OR ADDED TO NETWORK BY YOU

  • Steiner Point: A specific interior junction point consisting of three line segments (edges) coming together forming equal 1200 angles (a y-network)

Y

7.4 Continued

TRUE STORY EXAMPLE: in 1989, a consortium of several of the world’s biggest telephone companies (AT&T, MCI, Spring, and British Telephone) completed the Third Trans-Pacific Cable (TPC-3) line, a network of submarine fiber-optic lines linking Japan and Guam to the US (via Hawaii). The approximate straight line distances between the three locations was 1620 Japan to Guam, 3910 Japan to Hawaii, and 3820 Guam to Hawaii (in miles). The solution to these companies problem was to find the SHORTEST NETWORK between the Japan-Guam-Hawaii Triangle.

The SOLUTION: use a Steiner Point of the Triangle to create the network of actual length 5690 miles.

Note that 5690 miles is longer than the MST but that is a result of uneven contour of the ocean floor. The MST would have increased length besides the projected 5440 miles straight distance.

TEACHER NOTE: Students will need to calculate the steiner point for simple triangle involving 30-60-90

Is the SHORTEST NETWORK for THREE POINTS always a STEINER POINT?

GEOMETER’S SKETCHPAD INVESTIGATION???

Not every triangle has a steiner point. Any angle is 1200 or more => no more steiner points

Therefore the shortest Network can involve either a Steiner Point or the MST.

Use the transparency of 120o angles to check if a Steiner Point Exists in each triangle.

SHORTEST NETWORK CONNECTING THREE POINTS:

  • If the LARGEST angle of the triangle is greater than or equal to 1200, the shortest network linking the three vertices consists of the two shortest sides of the triangle. In this situation, the shortest network is the minimum spanning tree.
  • If LARGESTangle of the triangle isless than 1200, the shortest network is obtained by finding a STEINER POINTS inside the triangle and joining S to each of the vertices.

7.4 Continued

INTERIOR JUNCTION RULE for Shortest Networks:

In a shortest network the interior junction points are all Steiner Points.

Any other junction point in a triangle when the largest angle is less than 1200 will create a longer network than the Steiner Point network.

Consider the triangle ABC with interior junction points of P, Q, and R. We know that triangle ABC has no angle larger than 120o. The table below gives the lengths of all the created edges from each junction point to the vertices of the triangle. In each table, which junction point must be the STEINER POINT?

P / Q / R
A / 54 / 72 / 41
B / 61 / 94 / 87
C / 125 / 77 / 104
Total / 240 / 243 / 232
P / Q / R
A / 380 / 390 / 700
B / 620 / 680 / 260
C / 300 / 190 / 550
Total / 1300 / 1260 / 1510

SUMMARY OF TYPE OF SHORTEST NETWORK

Angles

/

Largest Angle ≥ 120

/

Largest Angle < 120

Shortest Network

/

Minimum Spanning Tree (MST)

/ STEINER POINT (Y – NETWORK)

Weight of Network

/

Pick the two smallest sides of the original triangle.

/ Draw the y-network and find the 3 weight of the edges drawn. (Normally requires trig)
Special Case: For an equilateral triangle, use the 30-60-90 triangle knowledge.

Example

Apply the Shortest Network for Connecting Three Points

For each triangle, identify the shortest network as a Minimum Spanning Tree (MST) or a Steiner Point.

Hint: Determine exact or approximate size of all angles in the triangle.

TRIANGLES ARE NOT DRAWN TO SCALE!!