AMS 301 Test 1 Solutions
AMS 301 Test1 Solutions
AMS 301 Test 1 Fall 2010 SOLUTIONS
1. (8pt) Isomorphic: Test A: a-2, b-5, c-9, d-1, e-6, f-8, g-3, h-4, i-7; Test B: a-3, b-2, c-9, d-4, e-6, f-8, g-1, h-5, i-7
2. (7 pt) Branch on (1,2) or (4,3)Test A: LB =17 Use (1,2) LB =18, Donbt Use (1,2) LB 22; Test B: LB =16, Use (1,2) LB = 17, Donbt Use (1,2) LB = 21.
3. (5 pt) Not connected. Test A: (a,g) separate; Test B: (f,g) separate.
4. (5 pt) Test A: Vertices = salespeople, Edge= overlapping sets of colleges, Colors = days; Test B: Vertices = managers, Edges = overlapping sets of rich people, Colors = days.
5. a) (3 pt) Not possible, one too many edges for e <= 3v-6.
b) (4 pt) Possible. Test A: r=6, v=5; Test B: r = 8, v=6.
c) (4 pt) Possible, e.g., circuit of length 9 (Test A) or 7 (Test B).
6. (15 pt) Quick answer: graph is bipartite with an odd no. of vertices.
Standard case-by-case answer. Consider 3 cases at k.
Case 1: Use e-k-f and delete (k,h)&(k,i); at h & i, use g-h-c-i-j; at c, delete (c,b)&(c,d); at b use a-b-g and at d use j-d-a. Subcircuit a-b-g-h-c-i-j-d-a.
Case 2: Use f-k-h and delete (k,e)&(k,i); at e & i, use a-e-j-i-c; at j, delete (j,d); at d use a-d-c. Subcircuit: a-d-c-i-j-e-a.
Case 3: Use e-k-h and delete (k,f)&(k,i); at f and i, use a-f-g & c-i-j; 2 subcases at e:
Subcase 3i: use e-a; at a, delete (a,d)&(a,b); at d, use c-d-j => subcircuit j-i-c-d-j. A symmetric situation exists at h with h-c, and so we can assume:
Subcase 3ii: use e-j and h-g; at j, delete(j,d); at g delete (g,b): at d and b, create subcircuit a-b-c-d-a.
7. (12 pt) Edge coloring (3 pt) assigns colors to edges so that no two edges with a common vertex have the same color. Minimal 4-person tournamentb3 days (4 pt): day 1: AB, CD, day 2: AC,BD, day 3: AD,BC; Minimal 5-person tournament --5 days {this is tricky] (5 pt): day 1: AB, CE, day 2: BC, DA, day 3: CD, EB, day 4: DE, AC, day 5: EA, BD.
AMS 301.1 First Test, Fall 2009, SOLUTIONS
1. Graphs are isomorphic.See Figure 1.19 in text.
2. Test A: LB = 18 (subtracting first from rows). Don't use (1,3), LB=22; use (1.3) (deleting row 1 & col 3 and setting (entry (3,1) = infinity), LB = 19.
Test B: LB = 14 (subtracting first from rows). Don't use (1,3), LB = 19; use (1,3) (deleting row 1 & col 3 and setting entru (3,1) = infinity), LB= 16
3. Test A: connected; test B: not connected
4. Test A and 5. Test B: vertices equal actuaries/statisticians, edges = personaly conflicts, colors = hotels; does 6 colors suffice?
5. Test A and 4. Test B: a) not possible, violates e <=3v-6; b) possible, v = (Test A, 12), (Test B, 10)-- remember that all vertices musst have deg 3; c) many possibilities, e.g., triangle with trailing path (like a kite),
6. As explained in class, by symmetry and need to use at least one vertical edge, you can assume you start with edge (c,h), at c by symmetry choose b-c & delete c-d, forcing at d, e-d-i. Two cases at b or h or e or i. We consider cases at h
Case 1. Use h-f, delete h-j => at j use e-j-g, at e delete e-a, => at a use b-a-f, subcricuit a-b-c-h-f-a.
Case 2. Use h-j, delete h-f => at f, use a-f-i, at i delete i-g => at g use b-g-j, subcircuit b-c-h-j-g-b.
7. a) Many possibilities.
b) If a cutset K did not intersect a tree T, then G-K would still be connected since G-K would contain a spanning tree.
c) If G1 and G2 are the two components of G-K, and if circuit C starts in G1, then any time C uses an edge of K, it moves over to G2. It must eventually return to G1, using a second edge of K. Thus crossing to G2 and returning to G1 cna occur many times, but each time the circuit uses 2 edges of K.
AMS301.1 First Test Fall, 2008 SOLUTIONS
1. Test A: a,d = 4,6, b=7,c=5,e=2,f=3,g=1, Text B: a,d = 4,7, b=3, c=5,e=1,f=2,g=6
2. Test A: LB = 16, branch on (4,2), don't use LB = 21, use LB = 18
Test B: LB = 12, branch on (4,2), don't use LB = 18, use LB = 14.
3. Test A: not connected, Test B: a-b-g-f-d-c-e
4. Vertices=ships, edges= overlappig time in port, colors=piers, min = 2.
5. Test A: a) v= 6, not possible, b) v = 8, many possibilities, c) circuit of length 10,
Test B: a) v = 7, not possible, b) v = 6, many possibilities, c) circuit of length 8.
6./7. Ham circuit problem, Must use d-i-m, b-k-n. 3 cases a j: i) e-j-f, ii) e-j-e, iii) e-j-g
i) delete h-j-g, use m-h-c-g-n, forces at n delete n-f and at m delete m-e, at e and f forces, e-a and f-a => subcircuit a-e-j-f-a.
ii) delete f-j-g, use a-f-n-g-c. 3 edges now used at n
iii) delete h-j-f, use a-f-n and m-h-c, at n delete n-g and use g-c, at m delete m-e and use e-a. Delete remaining 2 edges at a and c, isolating d and b.
6./7. Independent set question: a) if a,b same color, then they cannot be adj.
b) 5-circuit has max indep set of 2, n-circuit has size n/2 rounded down size.
c) a tree with one vertex as root and all other vertices as leaves of the root.