Consider the following network in a matching problem: The compatibilities are: Edge Compatibility FP $1\mathrm{.}5$ FQ $2\mathrm{.}5$ GP $1$ GQ $2$ HR $51.$ Write down an LP which can be solved to give the best matching $($i$.$e$.$ max compatibility$)$ between nodes F $,$ G$,$ H and nodes P $,$ Q$,$ R$.$ Provide two optimal solutions $$ one that is a BFS and one that is not a BFS$.($Let xXY be the flow through edge XY$)2.$ Formulate the dual of the LP in $(1)$ and solve it Consider the following network in a matching problem: