 7.1.1: Find the adjacency matrix and adjacency relation for the following ...
 7.1.2: Find the adjacency matrix and adjacency relation for the following ...
 7.1.3: Find the corresponding directed graph and adjacency relation for th...
 7.1.4: Find the corresponding directed graph and adjacency relation for th...
 7.1.5: Given the adjacency relation r = 5(1, 4), (1, 5), (1, 6), (6, 2), (...
 7.1.6: Given the adjacency relation r = 5(2, 1), (3, 2), (3, 3), (3, 4), (...
 7.1.7: Let r be a binary relation defined on the set 50, 1, 2, 3, 4, 5, 66...
 7.1.8: Describe a property of a directed graph whose adjacency matrix is s...
 7.1.9: Describe the directed graph whose adjacency matrix has all 0s on th...
 7.1.10: Describe the directed graph whose adjacency matrix has all 1s in ro...
 7.1.11: Describe the directed graph whose adjacency matrix has all 1s in ro...
 7.1.12: Describe the directed graph whose adjacency matrix has 1s in positi...
 7.1.13: Describe a property of a directed graph whose adjacency relation is...
 7.1.14: Describe a property of the adjacency matrix of a graph whose adjace...
 7.1.15: Adjacency relations r and s have the following associated adjacency...
 7.1.16: Adjacency relations r and s have the following associated adjacency...
 7.1.17: The two directed graphs that follow have adjacency relations r and ...
 7.1.18: The two directed graphs that follow have adjacency relations r and ...
 7.1.19: Let A be the matrix a = 0 1 1 1 1 1 0 0 1
 7.1.20: Let A be the matrix a = 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 Find the pr...
 7.1.21: The definition of a connected graph can be extended to directed gra...
 7.1.22: Describe the directed graph with the following reachability matrix ...
 7.1.23: For the following graph, write the reachability matrix R by simply ...
 7.1.24: For the following graph, write the reachability matrix R by simply ...
 7.1.25: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.26: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.27: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.28: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.29: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.30: For Exercises 2530, compute the reachability matrix R by using the ...
 7.1.31: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.32: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.33: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.34: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.35: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.36: For Exercises 3136, compute the reachability matrix R by using Wars...
 7.1.37: Given the binary relation r = 5(1, 3), (3, 2), (2, 3)6 on the set 5...
 7.1.38: Given the binary relation r = 5(1, 2), (2, 3), (4, 1)6 on the set 5...
 7.1.39: Use Warshalls algorithm to find the transitive closure of the follo...
 7.1.40: Use Warshalls algorithm to find the transitive closure of the follo...
 7.1.41: The following directed graph represents a binary relation r on the ...
 7.1.42: The following directed graph represents a binary relation r on the ...
 7.1.43: Let G be a directed graph, possibly with parallel arcs, and let A b...
 7.1.44: Let A be the adjacency matrix of a directed graph G, possibly with ...
 7.1.45: For the following graph, count the number of paths of length 2 from...
 7.1.46: For the following graph, count the number of paths of length 4 from...
Solutions for Chapter 7.1: Directed Graphs and Binary Relations; Warshalls Algorithm
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 7.1: Directed Graphs and Binary Relations; Warshalls Algorithm
Get Full SolutionsSince 46 problems in chapter 7.1: Directed Graphs and Binary Relations; Warshalls Algorithm have been answered, more than 19012 students have viewed full stepbystep solutions from this chapter. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Chapter 7.1: Directed Graphs and Binary Relations; Warshalls Algorithm includes 46 full stepbystep solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. This expansive textbook survival guide covers the following chapters and their solutions.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

Column space C (A) =
space of all combinations of the columns of A.

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

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

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

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

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].

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

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).

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

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

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.

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.