temi_esame1a.pdf
----------------

Problem 4)
----------
1) Given a graph G=(V,E), what is a spanning tree? How many edges are contained in a spanning tree with n nodes? Explain why.
2) Solve using Kruskal's algorithm the problem of connecting at minimum cost five computing centers. The table reports connecting costs for all pairs of centers.
2a) Briefly describe (in 3 lines) Kruskal's algorithm
2b) Report the value of an optimal solution and the corresponding tree.

Problem 5)
----------
Consider the undirected graph
...
with a cost (length) assigned to each edge.
a) Determine a minimum cost spanning tree and the corresponding cost.
Indicate what method you used and its complexity, as a function of the number of nodes n and/or arcs m (explaining).
What optimality condition allows to easily verify if a given spanning tree is of minimum total cost?
b) Find the cost of a shortest path between nodes 1 and 6. Indicate what method you used and its complexity (explaining).
a) Optimum cost spanning tree:
Method and complexity:
Optimality condition:
b) Shortest path:
Method and complexity:

temi_esame1b.pdf
----------------

Problem 6)
----------
Find shortest paths between node 1 and all the other nodes in the following graph:
..
a) Briefly describe (max 5 lines) the method that you used. Indicate, explaining why, its order of complexity.
b) Indicate, for each node, the cost of a shortest path connecting 1 to it.

Problem 7)
----------
Consider the following network, where the values on the arcs indicate the corresponding capacities.
...
Determine the value of a maximum flow that can be sent from s to t, starting from the feasible flow where 10 units are sent over the path s,1,2,3,4,t.
Report:
-Value of the max flow:
-Final network with flow values on the arcs:
..
-The sequence of paths that have been used to send units of flow, and the corresponding flow increase.
Path:                             increment:
Path:                             increment:
Path:                             increment:
Path:                             increment:

What property of maximum flows guarantees that the obtained flow is of maximum value? Explain why.

Problem 8)
----------
Consider an undirected graph where the capacities are reported in the following table:
...
a) determine with Ford-Fulkerson's method a maximum flow between s and t. Report all passages.
b) Find a minimum capacity cut and indicate its relationship with a maximum flow.
c) Assume that all capacities are integer. Indicate an upper bound on the value of the max flow between s and t as a function of the max capacity K_max. Deduce an upper bound on the complexity of the version of the Ford-Fulkerson's method that explicitly uses auxiliary (incremental) networks (as a function of the number of arcs m and of K_max). Explain why.

Problem 9)
----------
A company is starting the production of a new product P. Each unit of P is obtained by assembling a unit of product P1 and one of product P2. Before starting the production of any product, materials must be bought and workers must be trained. Training is different for workers involved in the production of P1 and P2 (the assembling phase requires no training), while materials needed for the two production lines are bought at the same time. We can train and buy materials in parallel. Before products P1 and P2 can be assembled, each unit of P2 must be inspected. After the assembling phase, products P must be tested and then stocked in a suitable area. The list of activities with the corresponding durations are reported:
Activity                      Duration
A) buying materials                  9
B) training line P1                 10
C) training line P2                  5
D) production of P1                  8
E) production of P2                  7
F) inspection of P2                  4
G) assembling phase                  6
H) testing product P2                5
I) stocking                          2

a) report for each activity the set of predecessors (if any). Define the graph corresponding to the project.
b) Determine via the CPM method the earliest completion time for the project and the slack of each activity.
c) Report the order of complexity of the CPM algorithm, as a function of the number of arcs in the graph. Explain why.	

Problem 10)
-----------
A company activates a project composed of 8 activities, denoted by letters A to H. The following table reports the duration of each activity and the corresponding precedences.
Activity ...
Predecessors ...
Duration ...
a) Draw the directed graph corresponding to the project, reporting Tmin and Tmax corresponding to the occurrence of each event corresponding to a vertex.
b) Determine the total minimum completion time for the project and the slack of activity.
c) Indicate the critical activities.
d) Report the Gantt diagram at the latest (each activity is completed as late as possible).