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

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

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

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

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

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.

Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

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

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

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

Norm
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.

Symmetric matrix A.
The transpose is AT = A, and aU = a ji. AI is also symmetric.

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