2) The standard quota (two decimal) for State A is
A) 6.39 B) 7.14
C) 12.78 D) 63.88
E) None of above
3) Which modified divisor works for Adam’s method?
A) 500 B) 505
C) 510 D) 515
E) None of the Above
4) Who gets the surplus in Hamilton’s method?
A) State A B) State B
C) State C D) State D
E) None of the Above
5) Under a certain apportionment method, state X has a standard quota of 48.9 and receives 47 seats in the final apportionment. This is called
A) an upper quota violation B) the Alabama paradox. C) the population paradox.
D) the new states paradox. E) a lower quota violation. 6) State Y received 100 seats under a certain apportionment method. 1 more seat was added to the legislature and then under the same apportionment method Y received 99 seats. This is called
A) an upper quota violation B) the Alabama paradox. C) the population paradox.
D) the new states paradox. E) a lower quota violation.
For questions 7 - 8: A small airline operates 5 flights (NY, BOS, DC, PHI, ATL) to major cities on the east coast. There are only 20 airplanes that the airline owns. The airplanes are apportioned among the flights on the basis of average profit per flight. 7) Which of the following best represents the key terms of an apportionment
(States; Populations; Seats) to the word problem?
8) Which of following will the standard divisor represent?
A) Flights per Airplane
B) Airplanes per Flight
C) Airplanes per Average Profit
D) Flights per Average Profit
E) Average Profit per Airplane
Hon Discrete CHAPTER FOUR REVIEW: SOLUTIONS
Identify the states, populations, seats, and what would the standard divisor represents:
Mr. Smith is planning to give candy to students based on the numerical value of their quarter grades.
Standard Divisor = grade point per 1 piece of candy States = students
Populations = quarter grades Seats = candy
WSFCS has seen a rise in students and is planning to hire 100 new teachers for either elementary, middle, and high schools. WSFCS plans to apportion the teachers based on the number of students each school level.
Standard Divisor = students per 1 teacher States = Schools
Populations = Number of Students Seats = New Teachers
The subway has 5 main subway lines (Green, Red, Yellow, Orange, and Blue) and the city is considering a more efficient way to organize public transportation. The plan is to re-distribute the 60 subway trains to the different lines based on the amount of profit that each line is currently making the city.
Standard Divisor = Profit per 1 train States = Subway Lines
Populations = Profit Seats =Subway Trains
STANDARD PRACTICE PROBLEMS:
1) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.
State
A
B
C
200 SEATS
Population
4400
8300
10,300
Standard Quotas
38.26
72.17
89.57
Standard Divisor = 115
Hamilton’s
38
72
90
Jefferson’s
38
72
90
Modified Divisor = 114.4 – 113.7
Adam’s
39
72
89
Modified Divisor = 115.731 - 15.789
Webster’s
38
72
90
Modified Divisor = 115
2) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.
State
A
B
C
D
E
200 SEATS
Population
4400
8300
5300
9700
10,300
Standard Quotas
23.16
43.68
27.89
51.05
54.21
Standard Divisor =190
Hamilton’s
23
44
28
51
54
Jefferson’s
23
44
28
51
54
Modified Divisor =
188.6 – 187.3
Adam’s
23
44
28
51
54
Modified Divisor =
191.4 - 193
Webster’s
23
44
28
31
54
Modified Divisor = 190
3) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.
State
A
B
C
D
E
150 SEATS
Population
1700
2300
3100
2700
1900
Standard Quotas
21.79
29.49
39.74
34.62
24.36
Standard Divisor = 78
Hamilton’s
22
29
40
35
24
Jefferson’s
22
29
40
35
24
Modified Divisor =
77.1-76.7
Adam’s
22
29
40
35
24
Modified Divisor =
79.32 - 79.41
Webster’s
22
29
40
35
24
Modified Divisor = 78
WORD PROBLEMS:
The 6 main departments at a local college need to split the 50 scholarships that the university offers to give to incoming freshmen. The admission department decides to assign scholarships to the departments based on their current number of majors which is given in the table below.
Political Science
History
Math
Science
English
Foreign Language
112
78
45
57
68
60
Identify the seats, populations, and states in this problem.
STATES = DEPARTMENTS, SEATS = SCHOLARSHIPS, POPULATIONS = Current Majors
What is the standard divisor? 420/50 =8.4
What does the standard divisor represent in this problem? (Hint: Use part a answers)
8.4 Currents Majors per 1 Scholarship to a department
What is the standard quota for each state?
Political Science
History
Math
Science
English
Foreign Language
112/8.4 = 13.33
78/8.4 = 9.29
45/8.4 = 5.36
57/8.4 = 6.79
68/8.4 = 8.10
60/8.4 = 7.14
What is the lower quota for each state?
13
9
5
6
8
7
What is the upper quota for each state?
14
10
6
7
9
8
What are HAMILTON’S AND JEFFERSON’S APPORTIONMENT to this problem?
HAMILTON’s Method:
13
9
5 + 1 = 6
6 + 1 = 7
8
7
Jefferson’s Method: Divisor = 7.81 – 8
14
9
5
7
8
7
There are 5 main interstates in a state. The state legislature plans to assign work crews to the 5 main interstates based on the average number of cars on the interstate each day. The interstates combined have an average of 231000 cars each day. The STANDARD QUOTA for each interstate is given in the table below.
Interstate 1
Interstate 40
Interstate 85
Interstate 485
Interstate 77
165.4
220.7
285.4
180.9
197.6
Identify the seats, populations, and states in this problem.
STATES = INTERSTATES, SEATS = WORK CREWS, POPULATIONS = Car Traffic
What is the standard divisor? 231,000/1050 = 220
What does the standard divisor represent in this problem? (Hint: Use part a answers)
220 Number of Cars per 1 Work Crew
What is the average number of cars for each interstate?
Loops: AA Bridges: AB Edge Set: AI, AI, AB, BI, BC, CH, HH, HG, GD, GE, DF, EF
Multiple Edges: AI
Loops: HH Bridges: BC, CH, HG
#2: If possible, draw each of the following graphs.
The graph has 3 bridges and 4 vertices.
The graph has 4 odd vertices and 2 even vertices.
Disconnected in which each component has a bridge.
Has at least 3 multiple edges, 2 loops, 5 vertices, and 10 total edges.
Disconnected graph with 2 even vertices and 3 odd vertices.
NOT POSSIBLE TO DRAW BECAUSE YOU CAN’T HAVE AN ODD NUMBER OF ODD VERTICES
Euler Path and odd vertices are not adjacent.
#3: For each of the following graphs
Graph #1
Graph #2
Graph #3
Components: ABED and CF
Components: None
Components: None
Circuit: A, B, D, E, A
Circuit: A, D, B, A
Circuit: A, D, E, A
Path: Not possible
Path: A, B, F
Path: A, D, C, F
#4: Does the Graph have an Euler Path, Euler Circuit, or Neither?
Determine by degree of vertices if an Euler Circuit or Path Exists a
If one exists, then find it from a starting vertex.
Graph #1: EP
Graph #2: EC
Graph #3: EC
Graph #4: Neither
#5: For the below graph,
Find a circuit of length 1
II
Find a circuit of length 4
DFGHD
Find a circuit of length 5
EDFHDE
Find a circuit of length 6
EDFGHDE
Find a path of length 3
BACD
Find a path of length 8
IIHGFDCAB
Find a path of length 11
CBACDEDFGHDE
Multiple Choice Practice Problems CHAPTER 6 - HAMILTON CIRCUITS:
1) The number of edges in K_{25} is
A) 24 B) 25 C) 276 D) 300 E) 325
2) The number of Hamilton Circuits in K_{16} is
A) 15 B) 120 C) 15! D) 16! E) 17!
3) If a complete graph has degree 8 for each vertex, then how many edges are in the graph?
A) 36 B) 8! C) 9! D) 8 E) 9
4) A complete graph has 465 edges. How many vertices does the graph have?
A) 29 B) 30 C) 31 D) 107,880 E) 108,345
5) A complete graph has 40,320 distinct Hamilton’s circuits. How many vertices are there?
A) 6 B) 7 C) 8 D) 9 E) 10
A
B
C
6) The graph in Figure #1 …
A) has no Hamilton circuit.
B
G ) has a single Hamilton circuit (and its mirror-image circuit).
C) has multiple Hamilton circuits, none contain the edge BD.
D
FIGURE #1
F
E
D ) has multiple Hamilton circuits, all contain the edge BE.
E) none of the above
For questions 7 - 9 refer figure #2:
7) The Nearest Neighbor Algorithm applied to the graph finds the solution:
A) D, C, A, B, E, D
B) D, E, A, B, C, D
C
FIGURE #2
) D, A, B, E, C, D
D) D, B, E, C, A, D
E) none of the above
8) The Cheapest Link Algorithm applied to the graph finds the solution:
A) D, C, A, B, E, D
B) D, E, A, B, C, D
C) D, A, B, E, C, D
D) D, B, E, C, A, D
E) none of the above
9) How many different Hamilton circuits would we have to find to use the Brute Force Algorithm starting at D?
A) 4
B) 5
C) 10
D) 24
E) 120
HONORS DISCRETE CHAPTER SIX REVIEW: SOLUTIONS
#1: For each of the following situations: Be able to find how many vertices, edges, degree of vertex, and number of distinct circuits exist in the complete graph.
1) 12 vertices
Edges: 66
Degree: 11
Distinct Circuits: 11!
2) degree of each vertex is 5
Vertices: 6
Edges: 15
Distinct Circuits: 5!
3) 18 vertices
Edges: 123
Degree: 17
Distinct Circuits: 17!
4) 21edges
Vertices: 7
Degree: 6
Distinct Circuits: 6!
5) Distinct Hamilton circuits = 720
Vertices: 7
Edges: 21
Degree: 6
6) 4 vertices
Edges: 6
Degree: 3
Distinct Circuits: 3!
7) 78 edges
Vertices: 13
Degree: 12
Distinct Circuits: 12!
#2: Determine if the graph has a Hamilton Path and/or circuit. If so, find one.
Graph #1
Graph #2
Graph #3
H. Circuit: A, B, F, C, E, D, A
H. Path: A, B, F, C, E, D
H. Circuit: A, C, B, F, E, D, A
H. Path: A, C, B, F, E, D
H. Circuit: Not Possible
H. Path: E, D, A, C, B, F
#3:For the weighted complete graphs/tables below: find the shortest Hamilton circuit for