UNIT 4 DAA

n the simplex method, the slack, surplus and artificial variables are restricted to be

• multiplied

• negative

• non-negative

•   divided

   n simplex method basic solution set as (n-m), all the variables other than basic are classified as

•      constant variable

•    non positive variables

•     basic variables

•     non-basic variable

In simplex method, the feasible basic solution must satisfy the

•    non-negativity constraint

•   negativity constraint

• basic constraint

•       common constraint

The third requirement of simplex method is that all the variables are restricted to include

• negative even values

• odd values

•       even values

•      non-negative values

  According to algebra of simplex method, the slack variables are assigned zero coefficients because

• no contribution in objective function

• high contribution in objective function

•      divisor contribution in objective function

•      base contribution in objective function

What does Maximum flow problem involve?

• finding a flow between source and sink that is maximum

•    finding a flow between source and sink that is minimum

•   finding the shortest path between source and sink

• computing a minimum spanning tree

What is the source?

•   Vertex with no incoming edges

• Vertex with no leaving edges

• Centre vertex

•   Vertex with the least weight

Which algorithm is used to solve a maximum flow problem?

• Prim’s algorithm

• Kruskal’s algorithm

       

• Dijkstra’s algorithm

• Ford-Fulkerson algorithm

     Does Ford- Fulkerson algorithm use the idea of?

• Naïve greedy algorithm approach

• Residual graphs

• Minimum cut

• Minimum spanning tree

   Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?

• Number of vertices in U = Number of vertices in V

     

• Sum of degrees of vertices in U = Sum of degrees of vertices in V

• Number of vertices in U > Number of vertices in V

• Nothing can be said