Answer the following questions.

a$.$ Consider a network with $n$ nodes. Then, any shortest path between

two nodes consist of at most $n-2$ ares. True or false? Explain.

b$.$ Suppose that each arc$-$length on a network is multiplied by the same

positive constant. How would that affert the solution to the shortest

path problem?

c$.$ Consider a network flow problem with several sources and several

sinks in which the goal is to maximize the total flow into the sinks$.$

Show how such a problem can be converted into a maximum$-$flow

problem having only a single source and a single sink.

Indicate whether the following statements are true or false. Provide a brief

and sufficient justification for your answer.

a$.$ The assignment problem can be solved using network simplex method.

b$.$ In a minimum spanning tree, the paths that connect the nodes are

shortest paths between those nodes.

c$.$ If the maximum flow value on a network flow problem is $10,$ then it

is possible to find a cut on this network with capacity $15.$

Seven types of parkages are to be delivered by five trucks. There are three

packages of each type, and the capacities of the five trucks are $6,4,5,4,$

and $3$ packages, respectively. Set up a maximum$-$flow problem that can

be used to determine whether the packages can be loaded so that no truck

carries two packages of the same type.