Details of this Paper

Final Exam combinatorics problems-Let G = (V, E) be a graph and let H1 = (V1, E1) and H2 = (V2, E2)




Question;Final Examcombinatorics problems.1 Let G = (V, E) be a graph and let H1 = (V1, E1) and H2 = (V2, E2) betwo connected subgraphs of G that have at least one node in common.Prove that the graph H = H1? H2 = (V1? V2, E1? E2) is connected.2. Prove that if all edge-costs are different, then there is only one cheapesttree. (Hint: Do a proof by contradiction, following the proof of Kruskal?stheorem (p. 159)). (Make sure to keep track of the costs of the differenttrees involved!)3. Let X = {x0, x1, ? ? ?, xm} be a subset of {1, 2, ? ? ?, n}, where m > n/2,and x0 is the smallest number in X.Use the pigeonhole principle to show that X contains two numbers b andc such that x0 + b = c.Hint: Consider x1? x0, x2? x0, ? ? ?, xm? x04. Let G = (V, E) be a bipartite graph with n nodes on each side. Showthat if the degree of each vertex is greater than n/2, then G has a perfectmatching.5. (a) Let Cn denote the number of ways of writing a valid list of open andclosed parentheses of length 2n (valid means that at any point along thelist, the number of open parentheses must be greater than or equal thenumber of closed parentheses). In the case of n = 3, there are 5 validconfigurations:((())),(())(),()()(),(()()),()(())With C0 = 1, provide a combinatorial proof thatCn+1 = C0Cn + C1Cn?1 + ? ? ? + CkCn?k + ? ? ? CnC0(b) Show that Cn also determines the number of paths in the plane from(0, 0) to (n, n)? N?N, that don?t cross the main diagonal (y = x) if eachstep in the path is of the form (1, 0), or (0, 1) (i.e., unit distance due eastor due north).


Paper#60270 | Written in 18-Jul-2015

Price : $57