4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

   \multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
   		\(P\)	\(R\)	\(S\)	\(T\)	\(W\)
   	Jeremy ( \(J\) )	56	56	51	57	58
   	Kath ( \(K\) )	53	52	53	54	54
   	Laura ( \(L\) )	57	55	52	58	60
   	Mohammed ( \(M\) )	59	55	53	59	57
   	Natalie ( \(N\) )	57	57	53	59	60
   	Ollie ( \(O\) )	58	56	51	56	57

   The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.