New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
mathematics
linear algebra

Discrete and Combinatorial Mathematics An Applied Introduction 5th edition Ralph P. Grimaldi - Solutions

Let T = (V, E) be a rooted tree with root r. Define the relation R on V by x R y, for x, y ∈ V, if x = y or if x is on the path from r to y. Prove that R is a partial order.
Let T = (V, E) be a tree with V = {v1, v2, ..., vn}, for n ‰¥ 2. Prove that the number of pendant vertices in T is equal to
Let G = (V, E) be a loop-free undirected graph. Define the relation R on E as follows: If e1, e2 ∈ E, then e1 R e2 if e1 = e2 or if e1 and e2 are edges of a cycle C in G. (a) Verify that R is an equivalence relation on E. (b) Describe the partition of E induced by R.
If G = (V, E) is a loop-free connected undirected graph and a, b ˆˆ V, then we define the distance from a to b (or from b to a), denoted d(a, b), as the length of a shortest path (in G) connecting a and b. (This is the number of edges in a shortest path connecting a and b and is 0 when a
Let G = (V, E) be a weighted graph, where for each edge e = (a, b) in E, wt(a, b) equals the distance from a to b along edge e. If (a, b) ∉ E, then wt(a, b) = ∞.Fix v0 ∈ V and let S ⊂ V, with v0 ∈ S. Then for S- = V - S we define d(v0, S-) = minves. [d(v0.v) .If vm+1 ∈ S- and d(v0, S) =
(a) Apply Dijkstra's algorithm to the weighted graph G = (V, E) in Fig. 13.4, and determine the shortest distance from vertex a to each of the other six vertices in G. Here wt(e) = wt(x, y) = wt(y, jc) for each edge e = {x, y} in E.(b) Determine a shortest path from vertex a to each of the vertices
(a) Apply Dijkstra's algorithm to the graph shown in Fig. 13.1 and determine the shortest distance from vertex a to each of the other vertices in the graph.(b) Find a shortest path from vertex a to each of the vertices f, g, and h.
Use the ideas developed at the end of the section to confirm the result obtained in (a) Example 13.2; and (b) part (a) of Exercise 2.
Prove or disprove the following for a weighted graph G = (V, E), where V = {v0, v1, v2, .. . , vn] and e1 ∈ E with wt(e1) < wt(e) for all e ∈ E, e ≠ e1. If Dijkstra's algorithm is applied to G, and the shortest distance d(v0, vt) is computed for each vertex vt, 1 < i < n, then there exists a
Apply Kruskal's and Prim's algorithms to determine minimal spanning trees for the graph shown in Fig. 13.8.
Let G = W4, the wheel on four spokes. Assign the weights 1, 1, 2, 2, 3, 3, 4, 4 to the edges of G so that (a) G has a unique minimal spanning tree; (b) G has more than one minimal spanning tree.
Let G = (V, E) be a loop-free weighted connected undirected graph with T = (V, E'), a minimal spanning tree for G. For v, w ∈ V, is the path from v to w in T a path of minimum weight in G?
Table 13.1 provides information on the distance (in miles) between pairs of cities in the state of Indiana.A system of highways connecting these seven cities is to be constructed. Determine which highways should be constructed so that the cost of construction is minimal. (Assume that the cost of
(a) Answer Exercise 4 under the additional requirement that the system includes a highway directly linking Evansville and Indianapolis.(b) If there must be a direct link between Fort Wayne and Gary in addition to the one connecting Evansville and Indianapolis, find the minimum number of miles of
Let G = (V, E) be a loop-free weighted connected undirected graph. For n ∈ Z+, let [e1, e2, . . . , en] be a set of edges (from E) that includes no cycle in G. Modify Kruskal's algorithm in order to obtain a spanning tree of G that is minimal among all the spanning trees of G that include the
(a) Modify Kruskal's algorithm to determine an optimal tree of maximal weight.(b) Interpret the information of Exercise 4 in terms of the number of calls that can be placed between pairs of cities via the adoption of certain new telephone transmission lines. (Cities that are not directly linked
Prove Theorem 13.2.
(a) For the network shown in Fig. 13.20, let the capacity of each edge be 10. If each edge e in the figure is labeled by a function f, as shown, determine the values of s,t,w,x, and y so that f is a flow in the network.(b) What is the value of this flow?(c) Find three cuts (P, P) in this network
Prove Corollaries 13.3 and 13.4.
Find a maximum flow and the corresponding minimum cut for each transport network shown in Fig. 13.21.
Apply the Edmonds-Karp and Ford-Fulkerson algorithms to find a maximum flow in Examples 13.12, 13.13, and 13.14.
Prove Corollary 13.5.
In each of the following "transport networks" two companies, ci and C2, produce a certain product that is used by two manufacturers, mi and m2. For the network shown in part (a) of Fig. 13.22, company c1 can produce 8 units and company c2 can produce 7 units; manufacturer m1 requires 7 units and
Find a maximum flow for the network shown in Fig. 13.23. The capacities on the undirected edges indicate that the capacity is the same in either direction. [However, for an undirected edge a flow can go in only one direction at a time as opposed to the situation for vertices b, g in Fig. 13.18(a).]
Let A1, A2, . . ., An be a collection of sets, where A1 = A2 = ..... = An and | At | = k > 0 for all 1 < i < n. (a) Prove that the given collection has a system of distinct representatives if and only if n < k. (b) When n < k, how many different systems exist for the collection?
Let G = (V, E) be a bipartite graph, where V is partitioned as X ∪ Y. If deg(x) > 4 for all x ∈ X and deg(y) < 5 for all y ∈ F, prove that if |X| < 10 then 8(G) < 2.
Let G = (V, E) be bipartite with V partitioned as X ∪ Y. For all x ∈ X, deg(x) > 3, and for all y ∈ Y, deg(y) < 7. If |X| < 50, find an upper bound (that is as small as possible) on δ(G).
(a) Let G = (V, E) be the bipartite graph shown in Fig. 13.32, with V partitioned as X ˆª Y. Determine 8(G) and a maximal matching of X into Y.b) For any bipartite graph G = (V, E), with V partitioned as X ˆª T, if f(G) denotes the independence number of G, show that |F| = Î²(G) - Î´(G).
For n > 2, prove that the hypercube Qn has at least 2(2n- 2) tion 11.5.) perfect matchings (as defined above in Exercise 5).
Cathy is liked by Albert, Joseph, and Robert; Janice by Joseph and Dennis; Theresa by Albert and Joseph; Nettie by Dennis, Joseph, and Frank; and Karen by Albert, Joseph, and Robert, (a) Set up a bipartite graph to model the matching problem where each man is paired with a woman he likes, (b) Draw
At Rydell High School the senior class is represented on six school committees by Annemarie (A), Gary (G), Jill (J), Kenneth (K), Michael (M), Norma (N), Paul (P), and Rosemary (R). The senior members of these committees are {A, G, J, P}, {G, J, K, R}, {A, M, N, P}, {A, G, M, N, P}, {A, G, K, N,
Let G = (V, E) be a bipartite graph with V partitioned as X ∪ Y, where X = {x1, x2, . . ., xm] and Y = {x1, x2, . . . , xn}- How many complete matchings of X into Y are there if (a) m = 2, n = 4, and G = Km n? (b) m = 4, n = 4, and G = Km,n? (c) m = 5, n = 9, and G = Km,n? (d) m < n and G = Km,n?
If G = (V, E) is an undirected graph, a spanning subgraph H of G in which each vertex has degree 1 is called a one-factor (or perfect matching) for G.a) If G has a one-factor, prove that |V| is even.b) Does the Petersen graph have a one-factor? (The Petersen graph was first introduced in Example
Prove Corollary 13.6.
Fritz is in charge of assigning students to part-time jobs at the college where he works. He has 25 student applications, and there are 25 different part-time jobs available on the campus. Each applicant is qualified for at least four of the jobs, but each job can be performed by at most four of
For each of the following collections of sets, determine, if possible, a system of distinct representatives. If no such system exists, explain why. (a) A1 = {2, 3, 4}, A2 = {3, 4}, A3 = {1}, A4 = {2, 3} (b) A1, = A2 = A3 = {2, 4, 5}, A4 = A5 = {1, 2, 3, 4, 5} c) A1 = {1, 2}, A2 = {2, 3, 4}, A3 =
(a) Determine all systems of distinct representatives for the collection of sets A1 = {1, 2}, A2 = {2, 3}, A3 = {3, 4}, A4 = {4, 1}. b) Given the collection of sets A1 = {1, 2}, A2 = {2, 3}, . . . , An = {n, 1}, determine how many different systems of distinct representatives exist for the
Apply Dijkstra's algorithm to the weighted directed multigraph shown in Fig. 13.33, and find the shortest distance from vertex a to the other seven vertices in the graph.
For her class in the analysis of algorithms, Stacy writes the following algorithm to determine the shortest distance from a vertex a to a vertex b in a weighted directed graph G = (V, E). Step 1 : Set Distance equal to 0, assign vertex a to the variable v, and let T = V. Step 2: If v = b, the value
(a) Let G = (V, E) be a loop-free weighted connected undirected graph. If e1 ∈ E with wt(ei) < wt(e) for all other edges e1 ∈ E, prove that edge e1 is part of every minimal spanning tree for G.(b) With G as in part (a), suppose that there are edges e1, e2 ∈ E with wt(e1) < wt(e2) <
(a) LetG = (V, E) be a loop-free weighted connected undirected graph where each edge e of G is part of a cycle. Prove that if e1 ∈ E with wt(e1) > wt(e) for all other edges e e E, then no spanning tree for G that contains e1 can be minimal.(b) With G as in part (a), suppose that e1, e2 ∈ E
Using the concept of flow in a transport network, construct a directed multigraph G = (V, E), with V = {u, v, w, x, y} and id(u) = 1, od(u) = 3; id(v) = 3, od(v) = 3; id(w) = 3, od(w) = 4; id(x) = 5, od(x) = 4; and id(y) = 4, od(y) = 2.
A set of words {qs, tq, ut, pqr, srt] is to be transmitted using a binary code for each letter, (a) Show that it is possible to select one letter from each word as a system of distinct representatives for these words, (b) If a letter is selected at random from each of the five words, what is the
This exercise outlines a proof of the Birkhoff-von Neumann Theorem.(a) For n ˆˆ Z+, an n Ã— n matrix is called a permutation matrix if there is exactly one 1 in each row and column, and all other entries are 0. How many 5 Ã— 5 permutation matrices are there? How many n Ã— n?b) An n Ã—
Find the additive inverse for each element in the rings of Examples 14.5 and 14.6.
Let (Q, ⊕, ⊙) denote the field where 0 and O are defined byA ⊕ b = a + b - k, a ⊙ b = a + b + (ab/m),for fixed elements k, m (≠ 0) of Q. Determine the value for k and the value for m in each of the following.(a) The zero element for the field is 3.(b) The additive inverse of the element 6
Let R = {a + bi|a, b ∈ Z, i2 = -1}, with addition and multiplication defined by (a + bi) + (c + di) = (a + c) + (b + d)i and (a + bi)(c + di) = (ac - bd) + (be + ad)i, respectively. (a) Verify that R is an integral domain, (b) Determine all units in R.
a. Determine the multiplicative inverse of the matrixin the ring ^{2)- that is, find a, b, c, d so that b. Show that s a unit in the ring M2(Q) but not a unit in M2 (Z).
Ifis a unit of this ring if and only if ad - be ‰ 0.
Give an example of a ring with eight elements. How about one with 16 elements? Generalize.
For R = {s, t, x, y}, define + and , making R into a ring, by Table 14.5(a) for + and by the partial table for + in Table 14.5(b).(a) Using the associative and distributive laws, determine the entries for the missing spaces in the multiplication table. (b) Is this ring commutative? (c) Does it have
Determine whether or not each of the following sets of numbers is a ring under ordinary addition and multiplication. a) R = the set of positive integers and zero b) R = {kn|n ∈ Z, k a fixed positive integer} c) R = (a + b√2 |a,b ∈ Z) d) R = {a + b √2 + c√3|a ∈ Z, b,c ∈ Q
Let (R, 4-, •) be a ring with a, b, c, d elements of R. State the conditions (from the definition of a ring) that are needed to prove each of the following results. a) (a + b) + c) = b + (c +a) b) d + a (b + c) - ab + (d + ac) c) c{d + b) + ab = (a + c)b + cd d) a(bc) + (ab)d = (ab)(d + c)
Consider the set Z together with the binary operations ⊕ and ⊙ given in Example 14.3. (a) Verify the associative laws for ⊕ and ⊙ and the distributive laws in order to complete the work started in part (a) of Example 14.3. [This now establishes that (Z, ⊕, ⊙) is a ring.] (b) Is this
Define the binary operations ⊕ and ⊙ on Z by x ⊕ y = x + y - 7,x ⊙ y = x + y - 3xy, for all x, y ∈ Z. Explain why (Z, ⊕, ⊙) is not a ring
Let k, m be fixed integers. Find all values for k, m for which (Z, ⊕, ⊙) is a ring under the binary operations x ⊕ y = x + y - k, x ⊙ y = x + y - mxy, where x, y ∈ Z.
Tables 14.4(a) and (b) make (R, +, •) into a ring, where R = {s, t, x, y}. (a) What is the zero for this ring? (b) What is the additive inverse of each element? (c) What is t(s + xy)? (d) Is R a commutative ring? (e) Does R have a unity? (f) Find a pair of zero divisors.
Define addition and multiplication, denoted by Š• and Š™, respectively, on the set Q as follows. For a, b ˆˆ Q, a Š• b=a + b + 7, a Š™ b = a + b + (ab/1). (a) Prove that (Q, Š•, Š™) is a ring, (b) Is this ring commutative? (c) Does the ring have a unity? What about units? (d) Is
Complete the proofs of Theorems 14.2, 14.4, 14.5, and 14.10.
(a) Let (R, +, •) be a finite commutative ring with unity u. If r ∈ R and r is not the zero element of R, prove that r is either a unit or a proper divisor of zero.(b) Does the result in part (a) remain valid when R is infinite?
(a) For R = M2(Z), prove thatis a subring of R. (b) What is the unity of R? (c) Does S have a unjty ? (d) Does S have any properties that R does not have? (e) Is S an ideal of R?
Let S and T be the following subsets of the ring R = M2 (Z) :(a) Verify that S is a subring of R. Is it an ideal?(b) Verify that T is a subring of R. Is it an ideal?
Let (R, +, •) be a commutative ring, and let z denote the zero element of R. For a fixed element a ∈ R, define N(a) = [r ∈ R | ra = z}. Prove that N(a) is an ideal of R.
Let R be a commutative ring with unity u, and let I be an ideal of R. (a) If u ∈ 1, prove that I = R. (b) If I contains a unit of R, prove that I = R.
Let (R, +, €¢) be the (finite) commutative ring with unity given by Tables 14.6(a) and (b).(a) Verify that R is a field.(b) Find a subring of R that is not an ideal.(c) Let x and y be unknowns. Solve the following system of linear equations in R: bx + y = u; x + by = z.
Let R be a commutative ring with unity u.a) For any (fixed) a ∈ R, prove that aR = {ar| r ∈ R] is an ideal of R.b) If the only ideals of R are {z} and R, prove that R is a field.
Let (S, +, •) and (T, +', •') be two rings. For R = S × T, define addition "⊕" and multiplication "⊙" by(s1, t1) ⊕ (s2, t2) = (S1 + S2, t1 +' t2),(s1 t1) ⊙ (s2, t2) = (S1 • s2, t1. t2).(a) Prove that under these closed binary operations, R is a ring.(b) If both S and T are
Let (R, +, •) be a ring with unity u, and |R| = 8. On R4 = R × R × R × R, define + and • as suggested by Exercise 18. In the ring R4, (a) How many elements have exactly two nonzero components? (b) How many elements have all nonzero components? (c) Is there a unity? (d) How many units are
If a, b, and c are any elements in a ring (R, +, •), prove that (a) a(b - c) = ab - (ac) = ab - ac and (b) (b - c)a = ba - (ca) = ba - ca.
Let (R, +, •) be a ring, with a ∈ R. Define 0a = z, la = a, and (n + 1)a = na + a, for all n ∈ Z+. (Here we are multiplying elements of R by elements of Z, so we have yet another operation that is different from the multiplications in either of Z or R.) For n > 0, we define (-n)a = n(-a),
(a) For ring (R, +, •) and each d e R, we define al = a, and dn+l = and, for all n ∈ Z+. Prove that for all m, n ∈ Z+, (am)(an) = am+n and (am)n = amn.(b) Can you suggest how we might define a° or a-n, n ∈ Z+, including any necessary conditions that R must satisfy for these definitions to
a. If R is a ring with unity and a, b are units of R, prove that ab is a unit of R and that (ab)-l = b-la-l.b. For the ring M2(Z), find A-1 B-1 (AB)-1 (BA)-1and B-1A-1 if
Prove that a unit in a ring R cannot be a proper divisor of zero.
(a) Verify that the subsets S = {s, w] and T = {s, v, x] are subrings of the ring R in Example 14.6. (The binary operations for the elements of S, T are those given in Table 14.3.)b) Are the subrings in part (a) ideals of R?
Let S and T be subrings of a ring R. Prove that S ∩ T is a subring of R.
Let R = M2(Z) and let S be the subset of R whereProve that S is a subring of R.
Let (R, +, •) be a ring. If S, T1 and T2 are subrings of R, and S ⊂ T1 ∪ T2, prove that S ⊂ T1 or S ⊂ T2.
(a) Determine whether each of the following pairs of integers is congruent modulo 8.(i) 62,118 (ii) -43,-237 (iii) -90, 230(b) Determine whether each of the following pairs of integers is congruent modulo 9.i) 76,243 (ii) -137,700 (iii) -56,-1199
Complete the proofs of Theorems 14.11 and 14.12.
Define relation R on Z+ by a R b, if r (a) = x(b), where x (a) = the number of positive (integer) divisors of a. For example, 2 R 3 and 4 R 25 but 5R9.a) Verify that 2ft is an equivalence relation on Z+.b) For the equivalence classes [a] and [b] induced by R, define operations of addition and
Find the multiplicative inverse of each element in Z11, Z13, and Z17.
Find [a]-1 in Z1009 for (a) a = 17, (b) a = 100, and (c) a = 111
(a) Find all subrings of Z12, Z18, and Z24. (b) Construct the Hasse diagram for each of these collections of subrings, where the partial order arises from set inclusion. Compare these diagrams with those for the set of positive divisors of n (n = 12; 18; 24), where the partial order now comes from
How many units and how many (proper) zero divisors are there in (a) Z17 (b) Zn117? (c) Z1117?
Prove that in any list of n consecutive integers, one of the integers is divisible by n.
If three distinct integers are randomly selected from the set {1, 2, 3, . . . , 1000}, what is the probability that their sum is divisible by 3?
(a) For c, d, n, m ∈ Z, with n > 1 and m > 0, prove that if c = d (mod n), then me = md (mod n) and cm = dm (mod n).b) If xnxn-1 ∙∙∙∙∙∙∙ x1\x0 = xn • 10 + ∙∙∙∙∙∙ + x\ • 10 + x0 denotes an (n + 1)-digit integer, then prove thatxnxn-i ∙∙∙∙∙∙∙∙
(a) Prove that for all n ∈ N, 10" = (-1)" (mod 11).(b) Consider the result for mod 9 in part (b) of Exercise 18. State and prove a comparable result for mod 11.
For each of the following determine the value(s) of the integer n > 1 for which the given congruence is true.(a) 28 = 6 (mod n) (b) 68 = 37 (mod n)(c) 301 ee 233 (mod n) (d) 49 = 2 (mod n)
For p a prime determine all elements a ∈ Zp where a2 = a.
For a, b, n ∈ Z+ and n > 1, prove that a = b (mod n) => gcd(a, n) = ged(b, n).
(a) Show that for all [a] ∈ Z7, if [a] ≠ [0], then[a]6 = [1],(b) Let n ≠ Z+ with ged(n, 7) = 1. Prove that 7|(n6 - 1).
Use the Caesar cipher to encrypt the plaintext: "All Gaul is divided into three parts."
The ciphertext FTQIMKIQIQDQ was encrypted using the encryption function E: Z26 → Z26 where E(θ) = (θ + k) mod 26. Considering the frequencies of occurrence for the letters in the ciphertext, determine (a) the key k for this cipher shift; (b) the decryption function D; and (c) the original
Determine the total number of affine ciphers for an alphabet of (a) 24 letters; (b) 25 letters; (c) 27 letters; and (d) 30 letters.
The ciphertext RWJWQTOOMYHKUXGOEMYP was encrypted with an affine cipher. Given that the plaintext letters e, t are encrypted as the ciphertext letters W, X, respectively, determine (a) the encryption function E; (b) the decryption function D\ and (c) the original (plaintext) message.
(a) How many distinct terms does the linear congruential generator with a = 5, c = 3, m = 19, and x0 = 10, produce? (b) What is the sequence of pseudorandom members generated?
Given the modulus m and the two seeds x0, x1, with 0 < x0,x1 < m, a sequence of pseudorandom numbers can be generated recursively from xn = (xn-1 + xn-2) mod m, n > 2. This generator is called the Fibonacci generator. Find the first ten pseudorandom numbers generated when m = 37 and x0 = 1, x1 = 28.
Let xn+1 = (axn + c) mod m, where 2 < a < m, 0 < c < m, 0 < x0 < m, 0 < xn+i < m, and n > 0. Prove that xn = (anx0 + c[(an - 1)/(a - 1)]) mod m, 0 < xn < m.
Consider the linear congruential generator with a = 7, c = 4, and m = 9. If x4 = 1, determine the seed x0.

Showing 11500 - 11600 of 11883

First
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved