Question

20. Three jealous wives and their husbands come to a river. The party must cross the river (from near shore to far shore) in a boat that can hold at most two people. Find a sequence of boat trips that will get the six people across the river without ever letting any husband be alone (without his wife) in the presence of another wife. 

28. Let T be a spanning tree in a connected undirected graph G. Show that when any non-tree edge is added to T, a unique circuit results.

Answer 1

Let $M_1,M_2,M_3$ are three husbands and $F_1,F_2,F_3$ are their wives respectively.

To find the sequence of boat trips that will get the six people across the ricer without letting any husband be alone in th presence of another wife.

Initially M1,F1,M2,F2,M3,F3 ------------------------------------   

(F1,F2) cross then M1,M2,M3,F3 ------------------------------------ F1,F2

F1 comes back

(F1,F3) cross then M1,M2,M3 ------------------------------------ F1,F2,F3

F1 comes back

(F1,M1) cross then M2,M3 ------------------------------------ M1,F1,F2,F3

F2 comes back

(F2,M2) cross then M3 ------------------------------------ M1,F1,M2,F2,F3

F3 comes back

(F3,M3) cross then ------------------------------------ M1,F1,M2,F2,M3,F3

Answer 2

Let the three husbands be H.H,.H and their wives be WI,W,, W Now the following table represents the sequence of boat trips that will get the six people across the river without ever letting any husband be alone in the presence of another wive. 1:243 Left Bank Crossing Right Bank WİT, X111 M,M,W,M