(Brian Thomas HW week 12 contribution) |
|||
| Line 8: | Line 8: | ||
-Brian ([[User:Thomas34|Thomas34]] 21:02, 18 November 2008 (UTC)) | -Brian ([[User:Thomas34|Thomas34]] 21:02, 18 November 2008 (UTC)) | ||
| + | |||
| + | ---- | ||
| + | In similar fashion, each square can be represented by the pair (i,j). Then one set of vertices V1 = {(i,j) | i+j is odd} and another set of vertices V2 = {(i,j) | i+j is even}. By looking at the moves of the knight, one can show that every edge of the graph connects a vertex of V1 to a vertex of V2. --[[User:Asuleime|Asuleime]] 22:47, 19 November 2008 (UTC) | ||
Latest revision as of 17:47, 19 November 2008
A proof outline follows:
- Given: Let each space s be a vertex, and let each valid knight jump be an edge. We want to prove that the graph G representing all legal moves for the knight on a m x n chessboard is bipartite.
- Consider partitioning the board into white spaces W and black spaces B. We will show G is bipartite with "sides" W and B.
- A knight on a white space can only jump to a black space, and vice versa.
- So, a knight on a white space cannot jump to another white space; likewise for black.
- (This means that for any two vertices in W, there is no edge connecting them; likewise for black.)
- By definition of a bipartite graph, then, G is bipartite.
-Brian (Thomas34 21:02, 18 November 2008 (UTC))
In similar fashion, each square can be represented by the pair (i,j). Then one set of vertices V1 = {(i,j) | i+j is odd} and another set of vertices V2 = {(i,j) | i+j is even}. By looking at the moves of the knight, one can show that every edge of the graph connects a vertex of V1 to a vertex of V2. --Asuleime 22:47, 19 November 2008 (UTC)
