Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
16 Cards in this Set
- Front
- Back
|
interior junction point
|
point that is not native- not one of the original vertices
|
|
|
interior junction rule
|
In shortest network, interior junction points are all steiner points
|
|
|
junction point
|
anywhere 2 or more segments come together
|
|
|
Kruskal's algorithm
|
1) Pick the cheapest edge available
2) pick the next cheapest edge 3) continue picking cheapest edge available that does not create a circuit EFFICIENT AND OPTIMAL |
|
|
minimum network problem
|
problem looking for optimal (meaning cheapest or shortest) network connecting set points
|
|
|
minimum spanning tree
|
spanning tree of lowest cost (weight) by Kruskal's algorithm
|
|
|
network
|
a connected graph
|
|
|
redundancy
|
zero of this in a tree and positive if not a tree
|
|
|
shortest network
|
designing a network that is as short as possible (Cheap)
|
|
|
shortest network rule
|
1) the shortest network consisting of a set of points is either:
a) a minimum spanning tree (no interior junction points) b) a steiner tree (tree such that all interior junction points are steiner points) |
|
|
spanning tree
|
a subgraph that connects all the vertices of the network and has no circuits
|
|
|
steiner point
|
interior junction point consisting of 3 line segments coming together to form equal 120 degree angles
|
|
|
steiner tree
|
a network with no circuits, such that all interior junction points are steiner points
|
|
|
subgraph
|
uses just some of the edges of a graph; has to be connected (a network)
|
|
|
Torricelli's construction
|
suppose A, B, C form a triangle such that all three angles of the triangle are less than 120 degrees
1) choose any of three sides of triangle (BC)and construct an equilateral triangle 2)circumscribe a circle around equilateral triangle (BCX) 3) joint X to A with a straight line. the point of intersection of the line segment XA with the circle is the steiner point! |
|
|
tree
|
network without any circuits
|
