 10.SE.7E: How many vertices and how many edges does the complete mpartite gr...
 10.SE.8E: Prove or disprove that there are always two vertices of the same de...
 10.SE.9E: Let G = (V,E) be an undirected graph and let A ? V and B ? V. Show ...
 10.SE.10E: Let G=(V.E)be an undirected graph.Show thata) N(v)?deg(v)for all ...
 10.SE.12E: Use Hall’s marriage theorem to show that a collection of finite sub...
 10.SE.11E: Find a SDR for the sets S1 = {a, c, m, e}. S2 = {m.a.c.e), S3 = {a,...
 10.SE.13E: a) Use Exercise 12 to show that the collection of setsS1 = {a. b. c...
 10.SE.15E: We say that three vertices u, v. and w of a simple graph G form a t...
 10.SE.14E: Use Exercise 12 to show that collection of sets S1 = {a. b. c}, S2 ...
 10.SE.16E: Find the clustering coefficient of each of the graphs in Exercise 2...
 10.SE.17E: Explain what the clustering coefficient measures in each of these g...
 10.SE.18E: For each of the graphs in Exercise 17, explain whether you would ex...
 10.SE.22E: A dominating set of vertices in a simple graph is a set of vertices...
 10.SE.21E: A clique in a simple undirected graph is a complete subgraph that i...
 10.SE.20E: A clique in a simple undirected graph is a complete subgraph that i...
 10.SE.19E: A clique in a simple undirected graph is a complete subgraph that i...
 10.SE.23E: A dominating set of vertices in a simple graph is a set of vertices...
 10.SE.25E: A simple graph can be used to determine the minimum number of queen...
 10.SE.24E: A dominating set of vertices in a simple graph is a set of vertices...
 10.SE.26E: A simple graph can be used to determine the minimum number of queen...
 10.SE.28E: Suppose that G 1 and H1are isomorphic and that G 2and H2 are isomor...
 10.SE.27E: A simple graph can be used to determine the minimum number of queen...
 10.SE.29E: Show that each of these properties is an invariant that isomorphic ...
 10.SE.31E: How many nonisomorphic connected bipartite simple graphs are there ...
 10.SE.30E: How can the adjacency matrix of be found from the adjacency matrix ...
 10.SE.32E: How many nonisomorphic simple connected graphs with five vertices a...
 10.SE.33E: Determine whether the following graphs are self converse. ________...
 10.SE.34E: Show that if the directed graph G is selfconverse and H is a direc...
 10.SE.37E: An orientation of an undirected simple graph is an assignment of di...
 10.SE.35E: An orientation of an undirected simple graph is an assignment of di...
 10.SE.36E: An orientation of an undirected simple graph is an assignment of di...
 10.SE.38E: Because traffic is growing heavy in the central part of a city, tra...
 10.SE.39E: Show that a graph is not orientable if it has a cut edge. A tournam...
 10.SE.40E: How many different tournaments are there with n vertices?
 10.SE.41E: What is the sum of the indegree and outdegree of a vertex in a to...
 10.SE.42E: Show that every tournament has a Hamilton path.
 10.SE.44E: Suppose that a connected graph G has n vertices and vertex connecti...
 10.SE.47E: Find the two nonisomorphic simple graphs with six vertices and nine...
 10.SE.46E: Show these graphs have optimal connectivity.a) Cn for n?3__________...
 10.SE.45E: Show that a connected graph with optimal connectivity must be regular.
 10.SE.43E: Given two chickens in a flock, one of them is dominant. This define...
 10.SE.48E: Suppose that G is a connected multigraph with 2k vertices of odd de...
 10.SE.49E: In Exercises 49 and 50 we consider a puzzle posed by Petkovic in [P...
 10.SE.50E: In Exercises 49 and 50 we consider a puzzle posed by Petkovic in [P...
 10.SE.51E: Let G be a simple graph with n vertices. The bandwidth of G, denote...
 10.SE.52E: The distance between two distinct vertices v1 and v2 of a connected...
 10.SE.53E: a) Show that if the diameter of the simple graph G is at least four...
 10.SE.54E: Suppose that a multigraph has 2m vertices of odd degree. Show that ...
 10.SE.56E: Devise an algorithm for finding the second shortest path between tw...
 10.SE.57E: Find the shortest path between the vertices a and z that passes thr...
 10.SE.58E: Devise an algorithm for finding the shortest path between two verti...
 10.SE.60E: A set of vertices in a graph is called independent if no two vertic...
 10.SE.59E: Show that if G is a simple graph with at least 11 vertices, then ei...
 10.SE.55E: Find the second shortest path between the vertices a and z in Figur...
 10.SE.62E: Show that the chromatic number of a graph is less than or equal to ...
 10.SE.61E: Show that the number of vertices in a simple graph is less than or ...
 10.SE.63E: Suppose that to generate a random simple graph with n vertices we f...
 10.SE.64E: For each of these properties, determine whether it is monotone incr...
 10.SE.66E: Suppose that P is a monotone increasing property of simple graphs. ...
 10.SE.65E: Show that the graph property P is monotone increasing if and only i...
 10.SE.1E: How many edges does a 50regular graph with 100 vertices have?
 10.SE.2E: How many nonisomorphic subgraphs does K3 have?
 10.SE.3E: In Exercises 35 determine whether two given graphs are isomorphic.
 10.SE.4E: In Exercises 35 determine whether two given graphs are isomorphic.
 10.SE.5E: In Exercises 35 determine whether two given graphs are isomorphic....
 10.SE.6E: Draw these graphs.a) K1,2,3________________b) K2,2,2_______________...
Solutions for Chapter 10.SE: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 10.SE
Get Full SolutionsChapter 10.SE includes 66 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 66 problems in chapter 10.SE have been answered, more than 184917 students have viewed full stepbystep solutions from this chapter.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Cyclic shift
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Fibonacci numbers
0,1,1,2,3,5, ... satisfy Fn = Fnl + Fn 2 = (A7 A~)I()q A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } A].

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

Iterative method.
A sequence of steps intended to approach the desired solution.

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.