# 12.5. Searching graphs¶

Solution 5.3

Consider the following program:

```brother(peter,paul).
brother(X,Y):-brother(Y,X).
brother(X,Y):-brother(X,Z),brother(Z,Y).
```

Compare and explain the behaviour of `prove_bf/1` and Prolog on the query `?-brother(peter,adrian)`. Can you re-order the clauses, such that Prolog succeeds?

Prolog will be trapped in an infinite loop, regardless of the order of the clauses. This is so because a refutation of `?-brother(peter,adrian)` requires both recursive clauses, but whichever is found first will also be tried before the second one in all the other refutation steps. In contrast, `prove_bf/1` will be able to construct a refutation.

Solution 5.5

Give the models of the program

```married(X);bachelor(X):-man(X),adult(X).
has_wife(X):-married(X),man(X).
man(paul).
```

This program has four models (bachelors may have a wife, and married man may be bachelors):

```{ man(paul), adult(paul), bachelor(paul) }
{ man(paul), adult(paul), bachelor(paul), has_wife(paul) }
{ man(paul), adult(paul), married(paul), has_wife(paul) }
{ man(paul), adult(paul), married(paul), bachelor(paul), has_wife(paul) }
```

The second and fourth models are non-minimal.

Solution 5.6

Are all minimal models always constructed by `model/1`?

Yes. The set of all Herbrand interpretations can be seen as a search space, in which the models are to be found. This search space is ordered by the subset relation. `model/1` starts from the empty interpretation, and repeatedly adds ground atoms until a model is constructed. Since one atom is added at a time, the procedure will never jump over a model. Since, on backtracking, all possible ways to satisfy a violated clause are considered, `model/1` performs a breadth-first search (which is complete).