 6.1.1: . Give the function g that is part of the formal definition of the ...
 6.1.2: Use the graph in the figure to answer the questions that follow. a....
 6.1.3: Sketch a picture of each of the following graphs. a. Simple graph w...
 6.1.4: Use the directed graph in the figure to answer the questions that f...
 6.1.5: Draw K6
 6.1.6: Draw K3,4.
 6.1.7: For each of the following characteristics, draw a graph or explain ...
 6.1.8: For each of the following characteristics, draw a graph or explain ...
 6.1.9: An acquaintanceship graph is an undirected graph in which the nodes...
 6.1.10: The small world effect states that the average degree of separation...
 6.1.11: The small world effect (see Exercise 10) has been found to be true ...
 6.1.12: An idea closely related to the average degree of separation in a gr...
 6.1.13: Which of the following graphs is not isomorphic to the others, and ...
 6.1.14: Which of the following graphs is not isomorphic to the others, and ...
 6.1.15: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.16: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.17: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.18: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.19: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.20: For Exercises 1520, decide if the two graphs are isomorphic. If so,...
 6.1.21: Prove that two graphs are not isomorphic if one of them a. has more...
 6.1.22: Draw all the nonisomorphic, simple graphs with two nodes.
 6.1.23: Draw all the nonisomorphic, simple graphs with three nodes.
 6.1.24: Draw all the nonisomorphic, simple graphs with four nodes
 6.1.25: Find an expression for the number of arcs in Kn and prove that your...
 6.1.26: Verify Eulers formula for the following simple, connected, planar g...
 6.1.27: Prove that K2,3 is a planar graph
 6.1.28: Prove that the following graph is a planar graph.
 6.1.29: If a simple, connected, planar graph has six nodes, all of degree 3...
 6.1.30: If all the nodes of a simple, connected, planar graph have degree 4...
 6.1.31: Does Eulers formula (Equation (1) of the theorem on the number of n...
 6.1.32: What is wrong with the following argument that claims to use elemen...
 6.1.33: For Exercises 3336, determine whether the graph is planar (by findi...
 6.1.34: For Exercises 3336, determine whether the graph is planar (by findi...
 6.1.35: For Exercises 3336, determine whether the graph is planar (by findi...
 6.1.36: For Exercises 3336, determine whether the graph is planar (by findi...
 6.1.37: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.38: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.39: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.40: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.41: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.42: For Exercises 3742, write the adjacency matrix for the given graph
 6.1.43: For Exercises 4346, draw the graph represented by the adjacency mat...
 6.1.44: For Exercises 4346, draw the graph represented by the adjacency mat...
 6.1.45: For Exercises 4346, draw the graph represented by the adjacency mat...
 6.1.46: For Exercises 4346, draw the graph represented by the adjacency mat...
 6.1.47: The adjacency matrix for an undirected graph is given in lower tria...
 6.1.48: The adjacency matrix for a directed graph is given by
 6.1.49: Describe the graph whose adjacency matrix is In, the n n identity m...
 6.1.50: Describe the graph whose adjacency matrix is 0n, the n n matrix of ...
 6.1.51: Describe the adjacency matrix for Kn, the simple, complete graph wi...
 6.1.52: Given the adjacency matrix A for a directed graph G, describe the g...
 6.1.53: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.54: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.55: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.56: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.57: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.58: For Exercises 5358, draw the adjacency list representation for the ...
 6.1.59: Refer to the accompanying graph. a. Draw the adjacency list represe...
 6.1.60: Draw the adjacency list representation for the following weighted d...
 6.1.61: For the directed graph of Exercise 42, construct the arraypointer ...
 6.1.62: For the weighted directed graph of Exercise 60, construct the array...
 6.1.63: Draw the undirected graph represented by the following adjacency list.
 6.1.64: Draw the directed graph represented by the following adjacency list.
 6.1.65: Draw G for the graph of Figure 6.18a
 6.1.66: Draw K4 r.
 6.1.67: Show that if two simple graphs G1 and G2 are isomorphic, so are the...
 6.1.68: A simple graph is selfcomplementary if it is isomorphic to its com...
 6.1.69: Prove that in any simple graph G with at least two nodes, if G is n...
 6.1.70: Find a simple graph G with at least two nodes where both G and G ar...
 6.1.71: Given an adjacency matrix A for a simple graph G, describe the adja...
 6.1.72: Prove that if 0N 0 11 in a simple, connected graph G, then not both...
 6.1.73: Prove that in any simple graph G with n nodes and a arcs, 2a n2 n
 6.1.74: Prove that a simple, connected graph with n nodes has at least n 1 ...
 6.1.75: Prove that a simple graph with n nodes (n 2) and more than C(n 1, 2...
 6.1.76: Eulers formula is stated for simple, connected planar graphs, but i...
 6.1.77: Show that a coloring of the accompanying map requires three colors ...
 6.1.78: Draw a map that requires four colors.
 6.1.79: Associated with any map is a graph, called the dual graph for the m...
 6.1.80: A coloring of a graph is an assignment of a color to each node of t...
 6.1.81: At least four colors are required to solve the general mapcoloring...
 6.1.82: Prove that in a simple, connected, planar graph with three or more ...
 6.1.83: (Challenging problem) The fivecolor theorem states that the chroma...
 6.1.84: The sixcolor theorem can be proved as a mapcoloring problem witho...
 6.1.85: Five political lobbyists are visiting seven members of Congress (la...
 6.1.86: In a multiprocessor machine, six processors labeled A through F sha...
Solutions for Chapter 6.1: Graphs and Their Representations
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 6.1: Graphs and Their Representations
Get Full SolutionsThis textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. Chapter 6.1: Graphs and Their Representations includes 86 full stepbystep solutions. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Since 86 problems in chapter 6.1: Graphs and Their Representations have been answered, more than 19980 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

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

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

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.

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

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

Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn1c can be computed with ne/2 multiplications. Revolutionary.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

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.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

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

Outer product uv T
= column times row = rank one matrix.

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

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

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

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.