The second method we talked about is decomposition.

In particular, the simplest way to decompose a network is if we have separate components

that are connected but where each component is connected but the components are disconnected

each other. I'm not sure. Disconnected from each other. If we have a situation like that,

we can just solve each of those components individually and then just take the union

of the solutions we come up with and we have found one assignment that works for the whole

network, which gives us a huge gain in computational efficiency. The other thing we talked about

is how to go about things if we have acyclic constraint graphs, whereby acyclic constraint

graphs will literally just mean the graph is acyclic.

In this case it isn't, but as we talked about, if we get rid of South Australia here, what

we're left with is a network that is R-consistent.

So the idea is that if we're, sorry that is acyclic.

The idea here is that for acyclic constraint graphs, we have the following algorithm that

is rather efficient and a lot more efficient than if we wouldn't exploit the fact that

it's an acyclic graph.

Why this algorithm actually happens to find a solution without ever having to backtrack

will be an exercise for tomorrow, i.e. will be an exercise that will be on the exercise

sheet I'll be giving out tomorrow.

So have fun doing that.

And once we have that, so here's an example of how this algorithm proceeds.

It's basically just we check our consist, or we enforce our consistency backwards along

the directed acyclic graph.

So we start from V2 to V3 and then from V1 to V2.

This is a somewhat simple example because every node only has one child.

And the case where we have a node, like imagine here would be a second node with parent V2

then we would also have to enforce our consistency from V2 to that child.