Oregon State University, CorvallisCS 225 Final. Questions and Answers

Document Content and Description Below

A circuit is a closed walk with at least one edge, with no repeated edges. A graph G has a Euler circuit if it is connected, and if every vertex in said graph has an even positive integer degree. T... he graph here is not a Euler circuit because it does not fit the first criteria of being connected, and the second of having every vertex with an even positive integer degree. Vertices v4 and v5, for example, each have a degree of 3; thus, this graph is not a Euler circuit. Can there be a simple graph that has n vertices all of different degrees? Why or why not? A simple graph is a graph with a simple circuit, and a simple circuit is a circuit (which is a closed walk with at least one edge and no repeating edges) with no repeated vertices besides the first and last vertex (which is the same since it is a circuit). Then suppose graph G is a simple circuit with all different degrees; then that means that for every vertex there must be a degree of n>1. So if graph G has 4 vertices, then the degrees must be n1=1, n2=2, n3=3, n4=4. But following the definition of simple circuit, n1 cannot be 1 because it must have at least n≥2 because it needs to connect to a different vertex to complete the circuit. Since there are only 4 vertices, there cannot be a degree of 5, so that n1 must have a degree of at least two but less than 4, which means it will share a degree with either n2, or n3, or n4, thus proving that all the degrees cannot be different. Which shows that for a simple graph with n vertices, all the vertices cannot have differing degrees for the graph to remain simple. A large pile of coins consists of pennies, nickels, dimes, and quarters. If the pile contains only 6 quarters but at least 20 of each other kind of coin, how many collections of 20 coins can be chosen? Here, need to select 20 coins out of a set of 4 (pennies, nickels, dimes, and quarters), with at most 6 of the 20 being quarters: calculating the overall number of selecting 20 coins out of a set of 4: C(20+4-1, 20) = C(23, 20) = C(23, 3) = 23!/(23!(23-20)!) Then suppose all 6 quarters were selected out of the 20 coins, then: 6!/20! And then the remaining 14 coins were selected from the other 3 coins, so that: C(14+3-1, 14) = C(16,14) = C(16, 2) = 16!/(16!(16-14)!) So that by the inclusion/exclusion principle, finding the selection of 20 coins out of a set of 4 with at most 6 being quarters equals to the overall number of selectionsselecting all 6 – selecting for the remaining set of 3: How many distinguishable orderings of the letters of MILLIMICRON begin with M and end with N? Here, there are 11 letters, but if M and N are already in place, then need to select the order of the 9 remaining letters (set of 9); 3 I 2 L 1 M 1 C 1 R 1 O so the possible orderings are: 9! / (3!*2!*1!*1!*1!*1!) Answer the following questions - a) According to the Inclusion/Exclusion Rule for Two Sets "If A and B are finite sets, then N(A ∪ B) = N(A) + N(B) − N(A ∩ B)" Now, how many integers from 1 through 100 are neither multiples of 3 nor multiples of 4? b) Let S = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Suppose six integers are chosen from S. Must there be two integers whose sum is 15? Why? a. according to the pigeonhole principle- k/n so A= 100/3 = 33 and B= 100/4 = 25 and (A ∩ B) is 4*3 = 12 ; then by k/n: 100/12= so that the number of integers from 1 through 100 are neither multiples of 3 nor multiples of 4 is equal to: 100 – 33 – 25 – 100/12 b. partition the set into 5 subsets: {3,12} {4, 11} {5, 10} {6, 9} {7, 8} where each subset’s sum is equal to 15. Then choosing any 3 of the above subsets (six numbers), will guarantee that at least two numbers will equal to 15; similarly, if choosing 5 of the smallest numbers from the above subsets (3,4,5,6,7) then choosing the 6th to be the smallest of the second pairs (8), 7+8 will equal 15, hence out of any 6 integers chosen, at least 2 pairs will sum up to 15 [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages