Introduction Play the original wolf-goat-cabbage puzzle.
A Group of Children Play a generalization with five children.
Graphs Terminology and the special types of bipartite graphs and trees.
Which boat size allows a first move and independence sets, stability number, vertex-edge coverings, and vertex-edge covering number.
Start possible but ... even with boat size τ(G) crossing the river is not always possible
Boat size τ(G)+1 If we add one more space to the minimum required boat size, we always succeed.
Trees are in general small boat graphs
States
State Bigraph
Large Graphs
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
blablablablablabla
In the following example, we have 5 vertices, α(G)=3 and τ(G)=2.
Therefore a first move is possible with boat size 2.
But can you transfer all children?
