A knight in chess is a piece that can move either two squares horizontally and one...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
A knight in chess is a piece that can move either two squares horizontally and one square vertically, or one square horizontally and two squares vertically. A knight's tour is a sequence of legal moves by a knight starting at some square and visiting each square on the chessboard exactly once. A knight's tour is called reentrant if there is a legal move that takes the knight from the last square of the tour back to the starting square. A well-known problem is to determine, given an m x n chessboard (that is, a chessboard with m rows and n columns), whether there exists a reentrant knight's tour. a. (5 points) Show how the knight tour problem can be modeled as a graph problem. Specify the vertices and the edges of the graph. b. (10 points) Show that there is a knight tour on a 3 4 chessboard. To do so, you need to describe the tour by listing the sequence of squares on the tour. You might find it convenient to use the standard labeling of a chessboard where the rows are labeled by the integers 1, 2, 3 and the columns by the characters a, b, c, d. A square is then referred to by a pair (x, y), where x is the row and y is the column determining the square. c. (5 points) Explain why there is no re-entrant knight tour on a 3 3 chessboard. 2. (15 points) A graph G is said to be a forest if G is a collection of trees, that is, if each connected component of G is a tree. Let G be a forest on n vertices, and suppose that G consists of a collection of k trees. What is the number of edges in G (in terms of n and k)? Justify your answer. 3. (20 points) For each of the following questions, either draw a graph with the given specifications or explain why no such graph exists: a. Acyclic graph with seven vertices and four edges. b. Tree with twelve vertices and fifteen edges. c. A graph that is not a tree with six vertices and five edges. d. A tree with five vertices and total degree 10. e. A connected graph with ten vertices and nine edges that contains a cycle. f. A simple connected graph with six vertices and six edges. g. A tree with ten vertices and total degree 24. Please refer to the figures given on the last page for the next 2 problems. 4. (15 points) Is the graph given in Figure 1 Hamiltonian? If so, list the vertices on a Hamiltonian cycle in order. 5. (15 points) Are the graphs given in Figure 2 isomorphic? If so, give an isomorphism between the two graphs. 6. (15 points) Is the graph given in Figure 2 planar? If so, give a planar drawing of the graph. How many faces does your drawing have? f k a d C f 3 Figure 1. Figure 2. n 3 2 6 5 A knight in chess is a piece that can move either two squares horizontally and one square vertically, or one square horizontally and two squares vertically. A knight's tour is a sequence of legal moves by a knight starting at some square and visiting each square on the chessboard exactly once. A knight's tour is called reentrant if there is a legal move that takes the knight from the last square of the tour back to the starting square. A well-known problem is to determine, given an m x n chessboard (that is, a chessboard with m rows and n columns), whether there exists a reentrant knight's tour. a. (5 points) Show how the knight tour problem can be modeled as a graph problem. Specify the vertices and the edges of the graph. b. (10 points) Show that there is a knight tour on a 3 4 chessboard. To do so, you need to describe the tour by listing the sequence of squares on the tour. You might find it convenient to use the standard labeling of a chessboard where the rows are labeled by the integers 1, 2, 3 and the columns by the characters a, b, c, d. A square is then referred to by a pair (x, y), where x is the row and y is the column determining the square. c. (5 points) Explain why there is no re-entrant knight tour on a 3 3 chessboard. 2. (15 points) A graph G is said to be a forest if G is a collection of trees, that is, if each connected component of G is a tree. Let G be a forest on n vertices, and suppose that G consists of a collection of k trees. What is the number of edges in G (in terms of n and k)? Justify your answer. 3. (20 points) For each of the following questions, either draw a graph with the given specifications or explain why no such graph exists: a. Acyclic graph with seven vertices and four edges. b. Tree with twelve vertices and fifteen edges. c. A graph that is not a tree with six vertices and five edges. d. A tree with five vertices and total degree 10. e. A connected graph with ten vertices and nine edges that contains a cycle. f. A simple connected graph with six vertices and six edges. g. A tree with ten vertices and total degree 24. Please refer to the figures given on the last page for the next 2 problems. 4. (15 points) Is the graph given in Figure 1 Hamiltonian? If so, list the vertices on a Hamiltonian cycle in order. 5. (15 points) Are the graphs given in Figure 2 isomorphic? If so, give an isomorphism between the two graphs. 6. (15 points) Is the graph given in Figure 2 planar? If so, give a planar drawing of the graph. How many faces does your drawing have? f k a d C f 3 Figure 1. Figure 2. n 3 2 6 5
Expert Answer:
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date:
Students also viewed these databases questions
-
Show that there is a knight's tour on a 3 Ã 4 chessboard A knight is a chess piece that can move either two spaces horizontally and one space vertically or one space horizontally and two...
-
Show that there is no knight's tour on a 4 Ã 4 chessboard. A knight is a chess piece that can move either two spaces horizontally and one space vertically or one space horizontally and two...
-
1. Jowel, the financial manager for Berjayasama Bhd, wishes to evaluate three potential investments: Investment A, Investments B and Investment C. Table 1 shows the expected returns. You have been...
-
What factors should retailers consider when assessing opportunity costs?
-
Discuss three approaches in measuring the gross domestic product. (10 marks) (b) Explain why GDP if often criticized as a measure of aggregate economic activity? (15 marks) (c) What is the difference...
-
A stream of hot gases at \(1,000^{\circ} \mathrm{C}\), having a specific heat of \(6.9 \mathrm{cal} / \mathrm{mol}-{ }^{\circ} \mathrm{C}\), is used to preheat air fed to a furnace. Because of...
-
A liquid mixture of 30 wt% acetone and 70wt% 2-methyl-l-pentanol (C6H14O) is cooled from 45C to 20C. Calculate the associated specific enthalpy change in J/g, using Kopps rule to estimate any heat...
-
Suppose the Jenson's alpha of a portfolio is 2.5%, while the actual return is 12%. The risk-free rate is 2.5% and the expected return on the market is 12%. What is the Treynor Ratio of the portfolio?
-
The Agnes Co. is considering the acquisition of the Bilko Co. Agnes projects that earnings next year will be $500. Agnes has 1000 shareholders and a P/E ratio of 10. Bilko projects that earnings next...
-
Zane company reported cost of good sold of 8 3 5 , 0 0 0 beginning inventory of 3 7 , 2 0 0 and ending inventory of 4 6 , 3 0 0 .What is the average inventory amount ?
-
Do a business reporting on the information management of the business focusing of the following aspect: - Incorporating Improved decision-making with information system of a business: - How Systems...
-
A 6.95% coupon, 9.0-year annual bond has a yield to maturity of 3.96%. Assuming the par value is 1,000 and the YTM does not change over the next year, Compute the following: A. Price of the bond...
-
Please give me a full business plan for marketing agency that called Marketing Masterminds located in London Ontario . They take care of small businesses' digital presence and promoting them on...
-
Evaluate 2NC P(n + 1) for each of the following values. N=27, C 68, P = 2754, and n = 23 2NC P(n + 1) = (Round to three decimal places as needed.)
-
Discuss the decision to use the atomic bomb on Hiroshima and Nagasaki.
-
Create a data model for one of the processes in the end-of-chapter Exercises for Chapter 4. Explain how you would balance the data model and process model.
-
Harry wants to contribute either \($6,500\) (BT\($)\) to a traditional deductible IRA or \($6,500\) (AT\($)\) to a Roth IRA. His current tax rate is 30% for ordinary income and 15% for capital gains....
-
The XYZ Partnership reports the following items during 2022: Calculate ordinary income (or loss) by completing page 1 of Form 1065, and complete Schedule K (Partners Shares of Income, Credits,...
-
Rita, a calendar year taxpayer, is an employee of the RST Partnership, which has a June 30 year-end. The partnership pays Rita a salary of 2,500 per month for the period January 1 through June 30,...
Study smarter with the SolutionInn App