Chapter 7
Honors Discrete 7.1 – 7.3 Review Worksheet:
Notes and Helpful Tips are provided. Use a separate paper!!!
TREE: Connected Graph (Network) with NO Circuits
• Property #1: Any two vertices have exactly ONE path between them
• Property #2: All edges in a tree are called bridges.
• Property #3: Number of Vertices is One More Than Number of Edges
• REDUDANCY: R = EDGES – VERTICES + 1
o Redundancy = 0: the original graph is a tree
o Redundancy > 0 : the original graph is not a tree and need to remove R edges to create a spanning tree
1) Determine if the following graph descriptions will (1) ALWAYS, (2) NEVER, or (3) SOMETIMES be a tree. If the graph is SOMETIMES, then provide an example of the graph as a tree and another not as a tree.
a. 9 vertices and exactly one path between any two different vertices.
b. 12 edges and 10 vertices.
c. 5 vertices and 4 edges.
d. 7 vertices and 6 bridges.
e. 8 vertices and no circuits.
2) Which of the following graphs is a tree?
I. Calculate the REDUNDANCY for each graph.
II. Find one SPANNING TREE by highlighting/tracing edges.
3) Draw a tree for each of the following descriptions on the back of this sheet.
• HINT: Start with the number of vertices you need, and then try to make degree statements work to create a CONNECTED graph with NO CIRCUITS.
a. 8 Vertices
b. 6 vertices and one vertex of degree 2.
c. 5 vertices and one vertex of degree 3.
d. 7 vertices and one vertex of degree 4 and one of degree 3.
4) Find the total number of spanning trees in each of the below graphs.
I. Find the length of all the primary circuits in the graph.
II. BORDER EDGE Case: Multiply the two bordering circuits and then subtract one from that product.
III. Multiply the lengths of all remaining circuits and special case values.
5) Find the MINIMUM SPANNING TREE in each of the graphs below:
• Number of Edges in Spanning Tree = Vertices – 1
• Pick the smallest weights for edges as long as no circuits are created
• Degree can be any number greater than 0 (NO Degree 2 requirement)
Honors Discrete 7.1 – 7.3 Review Worksheet: SOLUTIONS
1) Determine if the following graph descriptions will (1) ALWAYS, (2) NEVER, or (3) SOMETIMES be a tree. If the graph is SOMETIMES, then provide an example of the graph as a tree and another not as a tree.
a. 9 vertices and exactly one path between any two different vertices.
ALWAYS
b. 12 edges and 10 vertices.
NEVER
c. 5 vertices and 4 edges.
SOMETIMES
d. 7 vertices and 6 bridges.
ALWAYS
e. 8 vertices and no circuits.
SOMETIMES
2) Which of the following graphs is a tree?
III. Calculate the REDUNDANCY for each graph.
IV. Find one SPANNING TREE by highlighting/tracing edges.
3) Draw a tree for each of the following descriptions on the back of this sheet.
e. 8 Vertices
a. 6 vertices and one vertex of degree 2.
b. 5 vertices and one vertex of degree 3.
c. 7 vertices and one vertex of degree 4 and one of degree 3.
4) Find the total number of spanning trees in each of the below graphs.
5) Find the MINIMUM SPANNING TREE in each of the graphs below:
-----------------------
GRAPH #2
GRAPH #3
GRAPH #1
GRAPH #6
GRAPH #4
GRAPH #5
GRAPH #3
GRAPH #1
GRAPH #2
GRAPH #5
GRAPH #6
GRAPH #4
12
9
10
5
11
15
19
7
13
17
31
23
7
5
13
16
9
17
8
11
16
12
15
13
6
45
40
47
21
33
37
37
39
41
44
24
27
GRAPH #2
GRAPH #3
R = 2: 11 – 10 + 1 Not a Tree
R = 5: 10 – 6 + 1 Not a Tree
R = 0: 11 – 12 + 1 Tree
GRAPH #1
GRAPH #6
GRAPH #4
GRAPH #5
R = 3: 10 – 8 + 1 Not a Tree
R = 0: 7 – 8 + 1 Tree
R = 6: 16 – 11 + 1 Tree
GRAPH #3: 5*3-1 = 14 trees
GRAPH #2: 5*4 = 20 trees
GRAPH #1: 6 trees
GRAPH #5:
3*(5*7-1) = 102 trees
GRAPH #6:
(6*4-1)(3*4-1) = 253
GRAPH #4
4*(4*3-1) = 44 trees
45
40
47
21
33
37
37
39
41
44
24
27
31
23
7
5
13
16
9
17
8
11
16
12
15
13
6
Either 37 would work
12
9
10
5
11
15
19
7
13
17
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- chapter 7 learning psychology quizlet
- chapter 7 financial management course
- chapter 7 connect
- chapter 7 connect finance
- chapter 7 photosynthesis quizlet
- chapter 7 psychology quizlet
- psychology chapter 7 quiz quizlet
- chapter 7 psychology quizlet test
- chapter 7 learning quizlet
- psychology chapter 7 quizlet exam
- psychology chapter 7 learning
- psychology chapter 7 test questions