 10.1.1E: Graphs are represented by drawings. Define each graph formally by s...
 10.1.2E: Graphs are represented by drawings. Define each graph formally by s...
 10.1.3E: Draw pictures of the specified graphs.Graph G has vertex set {v1,v2...
 10.1.4E: Graph H has vertex set {v1, v2, v3, v4, v5} and edge set {e1, e2, e...
 10.1.5E: Show that the two drawings represent the same graph by labeling the...
 10.1.6E: Show that the two drawings represent the same graph by labeling the...
 10.1.7E: Show that the two drawings represent the same graph by labeling the...
 10.1.8E: For each of the graphs in(i) Find all edges that are incident on v1...
 10.1.9E: For each of the graphs in(i) Find all edges that are incident on v1...
 10.1.10E: Use the graph of Example to determinea. whether Sports Illustrated ...
 10.1.11E: Find three other winning sequences of moves for the vegetarians and...
 10.1.12E: Another famous puzzle used as an example in the study of artificial...
 10.1.13E: Solve the vegetariansandcannibals puzzle for the case where there...
 10.1.14E: Two jugs A and B have capacities of 3 quarts and 5 quarts, respecti...
 10.1.15E: A graph has vertices of degrees 0, 2, 2, 3, and 9. How many edges d...
 10.1.16E: A graph has vertices of degrees 1, 1, 4, 4, and 6. How many edges d...
 10.1.17E: Either draw a graph with the specified properties or explain why no...
 10.1.18E: Either draw a graph with the specified properties or explain why no...
 10.1.19E: Either draw a graph with the specified properties or explain why no...
 10.1.20E: Either draw a graph with the specified properties or explain why no...
 10.1.21E: Either draw a graph with the specified properties or explain why no...
 10.1.22E: Either draw a graph with the specified properties or explain why no...
 10.1.23E: Either draw a graph with the specified properties or explain why no...
 10.1.24E: Either draw a graph with the specified properties or explain why no...
 10.1.25E: Either draw a graph with the specified properties or explain why no...
 10.1.26E: Find all subgraphs of each of the following graphs.a. _____________...
 10.1.27E: a. In a group of 15 people, is it possible for each person to have ...
 10.1.28E: In a group of 25 people, is it possible for each to shake hands wit...
 10.1.29E: Is there a simple graph, each of whose vertices has even degree? Ex...
 10.1.30E: Suppose that G is a graph with v vertices and e edges and that the ...
 10.1.31E: Prove that any sum of an odd number of odd integers is odd.
 10.1.32E: Deduce from exercise that for any positive integer n, if there is a...
 10.1.33E: Recall that Kn denotes a complete graph on n vertices.a. Draw K6.__...
 10.1.34E: Use the result of exercise to show that the number of edges of a si...
 10.1.35E: Is there a simple graph with twice as many edges as vertices? Expla...
 10.1.36E: Recall that Km,n denotes a complete bipartite graph on (m, n) verti...
 10.1.37E: A bipartite graph G is a simple graph whose vertex set can be parti...
 10.1.38E: Suppose r and s are any positive integers. Does there exist a graph...
 10.1.39E: Find the complement of each of the following graphs.a. ____________...
 10.1.40E: a. Find the complement of the graph K4, the completegraph on four v...
 10.1.41E: Suppose that in a group of five people A, B, C, D, and E the follow...
 10.1.42E: Let G be a simple graph with n vertices. What is the relation betwe...
 10.1.43E: Show that at a party with at least two people, there are at least t...
 10.1.44E: a. In a simple graph, must every vertex have degree that is less th...
 10.1.45E: In a group of two or more people, must there always be at least two...
 10.1.46E: Imagine that the diagram shown below is a map with countries labele...
 10.1.47E: In this exercise a graph is used to help solve a scheduling problem...
 10.1.48E: A department wants to schedule final exams so that no student has m...
Solutions for Chapter 10.1: Discrete Mathematics with Applications 4th Edition
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 10.1
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics with Applications was written by Sieva Kozinsky and is associated to the ISBN: 9780495391326. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4th. Since 48 problems in chapter 10.1 have been answered, more than 23844 students have viewed full stepbystep solutions from this chapter. Chapter 10.1 includes 48 full stepbystep solutions.

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

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

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.

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

Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b  Ax is orthogonal to all columns of A.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

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 matrix A.
A square matrix that has no inverse: det(A) = o.

Stiffness matrix
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.

Tridiagonal matrix T: tij = 0 if Ii  j I > 1.
T 1 has rank 1 above and below diagonal.

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.