PDF 6-7-8 Network-flow

Question 1

What’s a network

Question 2

What constraints a feasible flow need to satisfy?

Question 3

What is the value of the flow?

Question 4

When an arc is saturated?

Question 5

What is a maximum flow problem?

Question 6

Linear Programming model for max-flow problem

Question 7

What’s a cut separating s from t?

Question 8

Capacity of the cut?

Question 9

Value of the flow

Question 10

Property one

Question 11

Property two + proof (weak duality)

Question 12

Dual problem

Question 13

Ford fulkerson

Question 14

Proof of exactness

Question 15

Theorem of strong dduality

Question 16

Size of an istance

Question 17

Ford Fulkerson complexity

Question 18

WHy ford fulkerson may be inefficient

Question 19

Name of faster implementation for max-flow problem

Question 20

What’s a recognition problem

Question 21

What a P class is?

Question 22

What an NP-class is?

Question 23

What reduce in polynomial time mean?

Question 24

What’s a polinomial time transformation?

Question 25

NP-complete class

Question 26

NP-hard problem

Question 27

ILP is NP-Hard proof

Question 28

Traveling salesman problem formulation

Question 29

WHat’s an hamiltonian circuit