SECTION 13A HIGHLIGHTS
Assignment: Read about Network Analysis in Section 13A of the text. Do
pp.713-716
RQ(1,4,6,7,8,9), BSC(17,18,20-22,24-32,35-37,42).
Vocabulary: Network, edge, vertex, path, order, degree of a vertex, tree, complete network, Euler Circuit, Burning Bridges Rule, Spanning Network, Kruskal's Algorithm
Notes:
In this section you are introduced to the concept of a Network. A Network
is defined to be a collection of points that are interconnected in some
way. A point in the network will be called a vertex and the connectors
will be called edges. To move from vertex to vertex along edges in a
network you follow a path.
An Euler Circuit is a path that starts and ends at the same vertex and traverses every edge exactly once.
The Burning Bridges Rule can be used to test if a network has an Euler Circuit. To use the rule begin from any vertex and move along a path. As you choose edges to follow, avoid using an edge that is the only connection to a part of the network that you have not already visited. In this way you will find an Euler Circuit if it exists.
The network terminology is defined clearly on pages 708-709of the text. Be sure to read these pages carefully.
A minimum cost panning network is a network that reaches each vertex point
and the edges, which each have an associated cost, are chosen so that the total
cost is a minimum.
Konigsberg Bridge Links
This link gives some info about the Konigsberg Bridge problem and includes
an activity.
KONIGSBERG
BRIDGE INFO AND ACTIVITY
Kruskal's Algorithm can be used to find a minimum cost network. The steps for using Kruskal's Algorithm are outlines on page 712 of the text. Nice practice exercises can be found at KRUSKAL PRACTICE
Skills to be mastered:
1. Create a network to represent a map or diagram.
2. Find Euler Circuits in a network using the Burning Bridges Rule.
3. Find the minimum cost spanning tree in a network using Kruskal's Algorithm.