Detour: Graphs
Let's learn about graphs and their different types.
We'll cover the following...
What “graph” means in this course
The use of the word “graph” in this course is different from its use in high school mathematics; we don’t mean a chart of data. You can think of a graph as a diagram showing cities connected by roads.
The first panel in the below figure shows a 4 × 4 chessboard with the four corner squares removed. A knight can move two steps in any of four directions (left, right, up, and down) followed by one step in a perpendicular direction. For example, a knight at square 1 can move to square 7 (two down and one left), square 9 (two down and one right), or square 6 (two right and one down).
STOP and Think: Can a knight travel around this board, pass through each square exactly once, and return to the same square it started on?
The second panel in the above figure represents each of the chessboard’s twelve squares as a node. Two nodes are connected by an edge if a knight can move between them in a single step. For example, node 1 is connected to nodes 6, 7, and 9. Connecting nodes in this manner produces a “Knight Graph” consisting of twelve nodes and sixteen edges.
We can describe a graph by its set of nodes and edges, where every edge is written as the pair of nodes that it connects. The graph in the second panel of the above figure is described by the node set
| 1 , 2 , 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
|---|
and the following edge set:
1 — 6 ...