Next: Basic Search Techniques Up: Introduction Previous: Introduction

Graph Theory

When talking about search we use terms from graph theory. In case anyone is not familiar, here are some pictures illustrating some of the important concepts:

So, a graph consists of a set of (possibly labelled) nodes with links between them. These links can be directed. A path is a sequence of nodes connecting two nodes via links (e.g., [a,b,e]). An acyclic graph has no paths linking a node with itself.

Using the tree as an example, we say that A is the parent of B and F (who are its children). B is F's sibling. A is the ancestor of all the other nodes, which are descendents of A.


alison@
Fri Aug 19 10:42:17 BST 1994