Murota K. Matrices and Matroids for Systems Analysis

Подождите немного. Документ загружается.

60 2. Matrix, Graph, and Matroid

[Minimum covers] For k =0, 1, ···,b,∞, the surplus function p

(k)

→ Z of G

is given by

(k)

(X)=|Γ (X) ∩ V

−

|−|X| = p

k−1

∪ X) − p

k−1

),X⊆ V

where X

k−1

= ∅ for k =0andX

k−1

= X

for k = ∞. This shows that

min

(k)

⎧

⎨

⎩

} (k =0)

{∅,V

} (1 ≤ k ≤ b)

{∅} (k = ∞).

(2.46)

[Admissibility of each arc] For a =(u, v) ∈ A

consider a cover (W

−

)

of G

\{u, v}. Since (W

∪{u},W

−

∪{v}) is a cover of G

but not a

minimum cover by (2.46), we have |W

|+ |W

−

|+2≥ ν(G

) + 1. Therefore,

ν(G

\{u, v}) = min{|W

| + |W

−

|} ≥ ν(G

) − 1. A maximum matching of

\{u, v} augmented with (u, v) yields a maximum matching of G

(3) This follows from the facts that (U

−

) is a cover if and only if

Γ (V

\ U

) ⊆ U

−

, and that X ∈L

min

) if and only if X corresponds to

an order ideal.

(2) For the proof of (2.43) suppose that G

 G

. Then there exists an

order ideal I such that k ∈ I and l ∈ I. By (3), (



j∈I



j∈I

−

)isa

minimum cover. This means in particular that there exists no arc between

and V

−

,thatis,A

= ∅.

For the proof of (2.44) suppose that G

≺· G

, where k<l.Put

I = {i | k<i<l,G

≺ G

},I

∗

= I ∪{k},

J = {j | k<j<l}\I, J

∗

= J ∪{l}.

We have (i) i ∈ I

∗

,j ∈ J ⇒ G

 G

, and (ii) i ∈ I ⇒ G

 G

.The

statement (i) is due to the transitivity of the partial order and the statement

(ii) is by the assumption G

≺· G

. It then follows that

i ∈ I

∗

,j ∈ J

∗

, (i, j) =(k, l) ⇒ G

 G

⇒ A

= ∅,

where (2.43) is used. If A

= ∅ is the case, we have A

= ∅ for i ∈ I

∗

and

j ∈ J

∗

. This implies X = X

k−1

∪





j∈J

∗



belongs to L

min

), since

(X)=(|Y

k−1



j∈J

∗

−

|)−(|X

k−1



j∈J

∗

|)=|Y

k−1

|−|X

k−1

|=min p

Hence we have X ∈L

min

), V

⊆ X and V

⊆ X. This contradicts the

deﬁnition (2.24) of V

 V

. Therefore, A

= ∅.

(4) Let (U

−

) be a minimum cover. By Theorem 2.2.15, a matching

M is maximum if and only if there exists no a ∈ M such that ∂

a ∈ U

and

∂

−

a ∈ U

−

. Then the assertion follows from (1)–(3) above.

2.2 Graph 61

Corollary 2.2.23.

(1) a ∈ A is admissible in G if and only if a ∈



∞

k=0

(2) V

= {v ∈ V

| ν(G)=ν(G \{v})},

−

∞

= {v ∈ V

−

| ν(G)=ν(G \{v})}.

Proof. (1) This follows from (1) and (4) of Theorem 2.2.22.

(2) Note V

\ V

= {v ∈ V

|∃(U

−

) ∈C(G),v ∈ U

}.If

−

) ∈C(G)andv ∈ U

, then (U

\{v},U

−

) is a cover of G \{v},

and hence ν(G \{v}) ≤|U

|+ |U

−

|−1=ν(G) −1. Conversely, for v ∈ V

and any cover (W

−

)ofG \{v},(W

∪{v},W

−

) is a cover of G but

not a minimum cover. Hence |W

∪{v}| + |W

−

|≥ν(G) + 1. Therefore,

ν(G \{v}) = min{|W

| + |W

−

|} ≥ ν(G). Similarly for V

−

∞

An algorithm for the DM-decomposition is given below. For a matching

M an auxiliary graph

=(V

∪ V

−

A; S

−

) is deﬁned by

A = {(u, v) | (u, v) ∈ A or (v, u) ∈ M},S

= V

\∂

M, S

−

= V

−

\∂

−

Recall the notation

∗

−→ for the reachability by a directed path.

Algorithm for the DM-decomposition of G =(V

−

; A)

1. Find

a maximum matching M on G =(V

−

; A).

2. Let V

= {v ∈ V

∪ V

−

| u

∗

−→ v on

for some u ∈ S

3. Let V

∞

= {v ∈ V

∪ V

−

| v

∗

−→ u on

for some u ∈ S

−

4. Let G



denote the graph obtained from

by deleting the vertices V

∪

∞

(and arcs incident thereto).

5. Let V

(k =1, ···,b) be the strong components of G



6. Let G

=(V

−

; A

) be the subgraph of G induced on V

(k =

0, 1, ···,b,∞).

7. Deﬁne a partial order  on {G

| k =1, ···,b} as follows:

 G

⇐⇒ v

∗

−→ v

for some v

∈ V

and v

∈ V

Also deﬁne G

 G

∞

for any k. 2

The validity of the above algorithm will be established in §2.3.5 as a special

case of a more general algorithm (the algorithm for the min-cut decomposi-

tion of an independent matching problem; see Lemma 2.3.35, to be speciﬁc).

This implies, in particular, that the decomposition constructed by the above

algorithm does not depend on the initially chosen maximal matching M.

A maximum matching can be found in O(|A| (min(|V

|, |V

−

|))

1/2

)timeby

an augmenting path method using layered networks; see Lawler [171] and

Papadimitriou–Steiglitz [265]. More recent algorithms can be found in Ahuja–

Magnanti–Orlin [3].

62 2. Matrix, Graph, and Matroid

A bipartite graph G =(V

−

; A) with V

∪ V

−

= ∅ is said to be

DM-irreducible if it cannot be decomposed into more than one nonempty

component in the DM-decomposition. Otherwise, it is called DM-reducible.

AgraphG with V

= ∅ or V

−

= ∅ is DM-irreducible, as the whole graph is

a (vertical or horizontal) tail. Note that G with A = ∅, V

= ∅ and V

−

= ∅

is DM-reducible, as it can be decomposed into two nonempty components,

the horizontal tail G

=(V

, ∅; ∅) and the vertical tail G

∞

=(∅,V

−

; ∅).

The following theorem is a reformulation of the result due to Marcus–Minc

[186] and Brualdi [22] (see also Brualdi–Ryser [24, Theorem 4.2.2]).

Theorem 2.2.24. For a bipartite graph G =(V

−

; A) with |V

| = |V

−

the following three conditions are equivalent:

(i) G is DM-irreducible,

(ii) C(G)={(V

, ∅), (∅,V

−

)},

(iii) ν(G \{u, v})=ν(G) − 1 for ∀u ∈ V

, ∀v ∈ V

−

Proof. The equivalence between (i) and (ii) follows from Theorem 2.2.22(1).

For (ii) ⇒ (iii), ﬁrst note (ii) implies ν(G)=|V

|, and hence ν(G \

{u, v}) ≤|V

|−1=ν(G)−1. Take a minimum cover (W

−

)ofG\{u, v}.

Since (W

∪{u},W

−

∪{v}) is a cover of G but not a minimum cover, we

see ν(G)+1≤|W

∪{u}| + |W

−

∪{v}| = ν(G \{u, v})+2.

For (iii) ⇒ (ii) suppose that (ii) fails. We divide into two cases: (a) ν(G)=

| and (b) ν(G) < |V

|. In case (a), there exists (U

−

) ∈C(G) such

that U

= ∅ and U

−

= ∅.Foru ∈ U

and v ∈ U

−

,(U

\{u},U

−

\{v})isa

cover of G \{u, v}. Hence ν(G \{u, v}) ≤|U

\{u}|+ |U

−

\{v}| = ν(G) −2.

In case (b), both horizontal and vertical tails are nonempty. For u ∈ V

and

v ∈ V

−

∞

we have ν(G \{u, v})=ν(G) by Corollary 2.2.23(2).

The concept of DM-decomposition may be extended to matrices by means

of the DM-decomposition of associated bipartite graphs. Recall from §2.2.1

that for a matrix A =(A

) the associated bipartite graph is deﬁned by G =

−

;

A) with V

= Col(A), V

−

=Row(A)and

A = {(j, i) | A

=0}.

A DM-component G

=(V

−

; A

)ofG corresponds to the submatrix

A[V

−

], which will be referred to as a DM-component of A.

The following relation is obvious from the deﬁnitions, but provides the

DM-decomposition with a linear algebraic signiﬁcance.

Proposition 2.2.25. term-rank A = ν(G). 2

The DM-decomposition of A gives the ﬁnest block-triangularization of

a matrix by means of a transformation P

using two permutation ma-

trices P

and P

, where it is imposed that each diagonal block in a block-

triangularization has full term-rank. In fact, Theorem 2.2.22(1) combined

with Proposition 2.2.25 above guarantees this term-rank condition for the di-

agonal blocks produced by the DM-decomposition. Furthermore, term-rank

2.2 Graph 63

coincides with rank for a generic matrix, in which all nonzero entries are in-

dependent parameters (cf. Proposition 2.1.12). Hence, for a generic matrix,

the DM-decomposition gives the ﬁnest proper block-triangularization in the

sense of §2.1.4.

For instance, the matrix version of the DM-decomposition of the graph

in Fig. 2.7 is given by

A =

∞

−

∞

Note that term-rank A[V

−

] = min(|V

|, |V

−

|)fork =0, 1, 2, ∞.The

matrix P

of (2.16) in Example 2.1.15 gives an instance of the DM-

decomposition of a term-nonsingular matrix.

Though term-rank is a natural combinatorial counterpart, it is not the

same as rank, which is undoubtedly more important in applications. A nu-

merical (nongeneric) matrix may or may not have the same rank as term-

rank, and accordingly, the DM-decomposition may or may not be a proper

block-triangular form. The present argument shows the following.

Proposition 2.2.26. For a matrix A the following three conditions (i)–(iii)

are equivalent.

(i) rank A = term-rank A.

(ii) The DM-decomposition is a proper block-triangularization, i.e., the

DM-components A[V

−

](k =0, 1, ···,b,∞) satisfy

rank A[V

−

] = min(|V

|, |V

−

|)(k =0, 1, ···,b,∞).

(iii) There exist I ⊆ Row(A) and J ⊆ Col(A) such that rank A[I,J]=0,

rank A[Row(A)\I,J]=|Row(A)\I|,andrank A[I,Col(A)\J]=|Col(A)\J|.

Proof. The equivalence of (i) and (ii) is immediate from Theorem 2.2.22. For

(iii) take I =Row(A) \ V

−

and J = Col(A) \ V

The concept of DM-irreducibility can be naturally deﬁned for matri-

ces, and it coincides with the well-studied concept of full indecomposability

(cf. Brualdi–Ryser [24] and Schneider [288]). To see this, ﬁrst recall that a

matrix A is said to be fully indecomposable if it does not contain a zero subma-

trix A[I,J]=O with I = ∅, J = ∅ and |I| + |J| = max(|Row(A)|, |Col(A)|).

Since A[I,J]=O if and only if (V

−

\ I,V

\ J) is a cover of the asso-

ciated graph G =(V

−

;

A), matrix A is fully indecomposable if and

only if G has no cover (U

−

) such that U

= V

, U

−

= V

−

and

64 2. Matrix, Graph, and Matroid

| + |U

−

| = min(|V

|, |V

−

|). The latter condition is equivalent to the

DM-irreducibility (cf. Theorem 2.2.24). Henceforth we use DM-irreducibility

as a synonym of full indecomposability.

The DM-irreducibility for square generic matrices admits two further

characterizations in addition to those given in Theorem 2.2.24. The ﬁrst says

that the DM-irreducibility for a generic matrix is equivalent to the inverse

matrix having a completely dense nonzero pattern.

Theorem 2.2.27. A square generic matrix A is DM-irreducible if and only

if A is nonsingular and (A

−1

)

=0for all (j, i).

Proof. Since (A

−1

)

= det A[R \{i},C \{j}]/ det A, where R =Row(A)

and C = Col(A), the claim here reduces to the equivalence of (i) and (iii) in

Theorem 2.2.24.

The determinant of a generic matrix A can be regarded as a polynomial in

the nonzero entries. Speciﬁcally, let T denote the set of nonzero entries of A,

which is algebraically independent over a ground ﬁeld K. Then det A ∈ K[T ],

where K[T ] means the ring of polynomials in T over K.

The following theorem gives an algebraic characterization of the DM-

irreducibility in terms of the irreducibility of the determinant as a multi-

variate polynomial. This is proven in Ryser [285] and credited essentially to

Frobenius [78] in Ryser [286].

Theorem 2.2.28. A square generic matrix A is DM-irreducible if and only

if det A is an irreducible (nonzero) polynomial in K[T ],whereT denotes the

set of nonzero entries of A.

Proof. The “if” part is obvious, since, for a DM-reducible A with no tails,

det A is equal to the product of the determinants of the diagonal blocks of

the DM-decomposition of A (and det A = 0 if a nonempty tail exists). For

the “only if” part assume that det A is factored as det A = f

· f

with

∈ K[T ] \ K.Fork =1, 2, let T

denote the set of the variables of T

that appear in f

.Put

= {i ∈ R | A

∈T

},C

= {j ∈ C | A

∈T

} (k =1, 2),

where R =Row(A)andC = Col(A). Then R

∩ R

= ∅, R

∪ R

= R,

∩C

= ∅, C

∪C

= C for k =1, 2, since for each pair of terms in f

and

their product remains in f

· f

= det A as a nonvanishing term, which in

turn corresponds to a perfect matching in the associated bipartite graph. We

may assume |R

|≥|C

|≥1 without loss of generality. If A[R

]=O, A

is DM-reducible. If A

= 0 for some i ∈ R

and j ∈ C

, the variable t = A

cannot appear in det A, since otherwise t must be contained in f

for k =1

or 2, which implies i ∈ R

and j ∈ C

, a contradiction to R

∩ R

= ∅ and

∩C

= ∅. The disappearance of t in det A implies det A[R\{i},C\{j}]=0,

or equivalently, ν(G \{i, j}) <ν(G) − 1 in terms of the associated bipartite

graph G. This shows the DM-reducibility by Theorem 2.2.24.

2.2 Graph 65

Remark 2.2.29. We have derived the DM-decomposition in a systematic

manner on the basis of the Jordan–H¨older-type theorem for submodular func-

tions, though alternative quicker derivations would have been possible. Our

systematic derivation here enables us to generalize the DM-decomposition to

a more sophisticated decomposition in §4.4, called the CCF (combinatorial

canonical form) of layered mixed matrices. The DM-decomposition serves as

one of the main tools for the graph-theoretic methods for systems analysis

(see Duﬀ–Erisman–Reid [59], Murota [204, Chaps. 2 and 3]), whereas the

CCF is for the matroid-theoretic methods to be developed in Chap. 4 and

Chap. 6. Applications of the DM-decomposition can be found in Ashcraft–Liu

[8], Erisman–Grimes–Lewis–Poole–Simon [73], Hellerman–Rarick [109, 110],

O’Neil–Szyld [255], and Pothen–Fan [273]. 2

2.2.4 Maximum Flow and Menger-type Linking

In §2.2.4 and §2.2.5 we describe some fundamental results from network ﬂow

theory that are needed in this book; maximum ﬂow in §2.2.4 and mini-

mum cost ﬂow in §2.2.5. For systematic and comprehensive expositions of

network ﬂow theory, the reader is referred to standard textbooks such as

Ahuja–Magnanti–Orlin [3], Cook–Cunningham–Pulleyblank–Schrijver [40],

Ford–Fulkerson [75], Iri [123], Lawler [171], Nemhauser–Rinnooy Kan–Todd

[250], Nemhauser–Wolsey [251], and Papadimitriou–Steiglitz [265].

Consider a network N =(V,A, c; s

−

), where V is the vertex set, A is

the arc set, c : A → R

∪{+∞} is a function deﬁning the capacity of arcs

: set of nonnegative reals), and s

and s

−

are two distinct vertices called

the source and the sink (s

−

∈ V and s

= s

−

). A ﬂow in N is a function

ϕ : A → R. A function ∂ϕ : V → R derived from ϕ by

∂ϕ(v)=



{ϕ(a) | a ∈ δ

v}−



{ϕ(a) | a ∈ δ

−

v},v∈ V, (2.47)

is called the boundary of ϕ. Recall that for v ∈ V , δ

v means the set of arcs

going out of v and δ

−

v the set of arcs coming into v.Afeasible ﬂow in N is

aﬂowϕ : A → R that satisﬁes

capacity condition : 0 ≤ ϕ(a) ≤ c(a),a∈ A,

conservation condition : ∂ϕ(v)=0,v∈ V \{s

−

We call val(ϕ)=∂ϕ(s

)(=−∂ϕ(s

−

)) the value of ϕ.Themaximum ﬂow

problem is to ﬁnd a feasible ﬂow ϕ that maximizes val(ϕ).

Suppose we tear the network N into two parts in such a way that s

and

−

belong to diﬀerent parts. Such tearing is speciﬁed by a set S ⊆ V such

that s

∈ S and s

−

∈ V \ S; we put

S = {S ⊆ V | s

∈ S, s

−

∈ V \ S}. (2.48)

The set of arcs going from S to V \ S is denoted as

66 2. Matrix, Graph, and Matroid

C(S)={a ∈ A | ∂

a ∈ S, ∂

−

a ∈ V \ S}, (2.49)

which is referred to as the cut corresponding to S. Total amount of ﬂow from

to s

−

is obviously bounded by the total capacity of the arcs in C(S). That

is, denoting the capacity of the cut by

κ(S)=



{c(a) | a ∈ C(S)}, (2.50)

we have an inequality

val(ϕ) ≤ κ(S) (2.51)

for any ﬂow ϕ and any S ∈S.

The celebrated max-ﬂow min-cut theorem asserts that the inequality

(2.51) is satisﬁed with equality for a suitable choice of ϕ and S.

Theorem 2.2.30 (Max-ﬂow min-cut theorem). The maximum value

of a ﬂow is equal to the minimum capacity of a cut:

max{val(ϕ) | ϕ : feasible ﬂow} = min{κ(S) | S ∈S}.

If the capacity function is integer-valued, there exists an integer-valued max-

imum ﬂow. 2

In passing it is mentioned that the function κ : S→R satisﬁes the

submodular inequality:

κ(S)+κ(T ) ≥ κ(S ∪ T )+κ(S ∩T )

,S,T∈S. (2.52)

This can be proven easily by the nonnegativity of c.

Next we turn to Menger-type linkings in a graph. Let G =(V, A; X, Y )be

a graph with vertex set V composed of three disjoint parts as V = X ∪U ∪Y .

We call X the entrance and Y the exit (including the case where X = ∅ or

Y = ∅). By a Menger-type linking

from X to Y is meant a set of pairwise

vertex-disjoint directed paths, each from a vertex in X toavertexinY .The

size of a linking is deﬁned to be the number of directed paths from X to Y

contained in the linking. A linking of the maximum size is called a maximum

linking and, in case |X| = |Y |, a linking of size |X| is called a perfect linking.

By a separator of (X, Y ) is meant such a subset of V that intersects any

directed path from a vertex in X toavertexinY . A separator of minimum

cardinality is called a minimum separator.

Menger-type linkings can be treated as a special case of network ﬂow.

Assuming, for simplicity of presentation, that there is no arc entering x ∈ X

Four variants of Menger-type linking are considered in the literature according

to (i) whether arcs are directed or undirected, and (ii) whether paths are vertex-

disjoint or arc-disjoint. Only the version of directed arcs and vertex-disjoint paths

is used in this book.

2.2 Graph 67

or leaving y ∈ Y , we consider a network N

A, c; s

−

) using copies

of X, Y and U and new vertices s

and s

−

as follows:

V = {s

−

}∪X

∗

∪ U

∗

∪ U

∗

∪ Y

∗

= {x

∗

| x ∈ X},U

∗

= {u

∗

| u ∈ U},

∗

= {u

∗

| u ∈ U},Y

∗

= {y

∗

| y ∈ Y },

A =

∪

= {(v

∗

) | (v, w) ∈ A},

= {(s

∗

) | x ∈ X}∪{(u

∗

) | u ∈ U}∪{(y

∗

−

) | y ∈ Y },

c(a)=



1(a ∈

)

+∞ (a ∈

Note that U

∗

and U

∗

are disjoint copies of U.

There exists a one-to-one correspondence between Menger-type maximum

linkings in G from X to Y and integral maximum ﬂows in N

from s

to s

−

which have no circulation (ﬂow along a cycle). On the other hand,

minimum separators of (X, Y )inG correspond to minimum cuts with respect

to (s

−

)inN

. The max-ﬂow min-cut theorem for N

implies the following

relationship between linkings and separators.

Theorem 2.2.31 (Menger’s theorem). Let G =(V, A; X, Y ) be a graph

with entrance X and exit Y . The maximum size of a Menger-type vertex-

disjoint linking from X to Y is equal to the minimum cardinality of a sepa-

rator of (X, Y ). 2

Remark 2.2.32. Based on the submodularity (2.52) of the cut capacity

function κ, a unique decomposition of a network into subnetworks can be

deﬁned (see Picard–Queyranne [268] and Murota [204, §8.2]). This decompo-

sition can be tailored readily to a decomposition of a graph into subgraphs

with respect to Menger-type maximum linkings and minimum separators.

The decomposition thus obtained is named “Menger-decomposition” (or “M-

decomposition” for short) by Murota [196, 205]. See also Murota [204, §8.3]

for details. 2

2.2.5 Minimum Cost Flow and Weighted Matching

The minimum cost ﬂow problem can be described as follows. Let G =(V,A)

be a graph with vertex set V and arc set A. Suppose we are also given

an upper capacity function

c : A → R ∪{+∞}, a lower capacity function

: A → R ∪ {−∞}, and a cost function γ : A → R. Namely, we are given

a network N =(V, A,

c, c,γ). A ﬂow in N is a function ϕ : A → R, and a

feasible ﬂow (circulation) in N is a ﬂow ϕ : A → R that satisﬁes

capacity condition : c

(a) ≤ ϕ(a) ≤ c(a),a∈ A,

conservation condition : ∂ϕ(v)=0,v∈ V,

68 2. Matrix, Graph, and Matroid

where ∂ϕ : V → R is the boundary of ϕ deﬁned in (2.47). The cost of ﬂow ϕ

is deﬁned to be

cost(ϕ)=



a∈A

γ(a)ϕ(a).

The minimum cost ﬂow problem is to ﬁnd a feasible ﬂow ϕ that minimizes

cost(ϕ). A feasible ﬂow that attains the minimum cost is called an optimal

ﬂow or a minimum cost ﬂow.

The optimality of a feasible ﬂow can be characterized in a manner suitable

for algorithmic veriﬁcation. With a feasible ﬂow ϕ : A → R we associate an

auxiliary network

=(V,

A, ˜γ). The arc set of

is given by

A = A

∗

∪B

∗

with

∗

= {a | a ∈ A, ϕ(a) < c(a)},

∗

= {a | a ∈ A, c(a) <ϕ(a)} (a: reorientation of a)

and the arc length function ˜γ :

A → R is deﬁned by

˜γ(a)=



γ(a)(a ∈ A

∗

)

−γ(a)(a =(u, v) ∈ B

∗

, a =(v, u) ∈ A).

(2.53)

Then optimality of a feasible ﬂow can be characterized as follows.

Theorem 2.2.33. For a feasible ﬂow ϕ : A → R, the following three condi-

tions (i)–(iii) are equivalent.

(i) ϕ is optimal, i.e., ϕ minimizes cost(ϕ).

(ii) There exists a “potential” function p : V → R such that, for each

a ∈ A,

γ(a)+p(∂

a) − p(∂

−

a) > 0=⇒ ϕ(a)=c(a), (2.54)

γ(a)+p(∂

a) − p(∂

−

a) < 0=⇒ ϕ(a)=c(a). (2.55)

(iii) There exists no cycle of negative length with respect to ˜γ in the

auxiliary network

Moreover, if the cost γ is integer-valued, we can choose p to be integer-

valued in (ii).

Proof.Putγ

(a)=γ(a)+p(∂

a) − p(∂

−

a)fora ∈ A.

(ii) ⇒ (i): For any feasible ϕ



: A → R we have

cost(ϕ





a∈A

(a)ϕ



(a)=



a:γ

(a)>0

(a)ϕ



(a)+



a:γ

(a)<0

(a)ϕ



(a)

≥



a:γ

(a)>0

(a)c(a)+



a:γ

(a)<0

(a)c(a) = cost(ϕ).

(i) ⇒ (iii): Suppose there exists a cycle of negative length in

.Let

C ⊆

A be the arc set of such a cycle of minimum cardinality. Then ϕ



deﬁned

2.2 Graph 69



(a)=

⎧

⎨

⎩

ϕ(a)+ε (a ∈ A

∗

∩

ϕ(a) − ε (

a ∈ B

∗

∩

ϕ(a) (otherwise)

(2.56)

with a suﬃciently small ε>0 is feasible and

cost(ϕ



) − cost(ϕ)=ε



a∈

˜γ(a) < 0.

(iii) ⇒ (ii): Since there exists no cycle of negative length in

, there

exists p : V → R such that ˜γ(a)+p(∂

a) − p(∂

−

a) ≥ 0(∀ a ∈

A)(see

Theorem 2.2.35 below). This condition is equivalent to the condition in (ii).

As to the existence of optimal ﬂows, the following theorem states funda-

mental facts. The second statement below refers to another auxiliary network

∞

=(V,A

∗

∪ B

∗

, ˜γ) deﬁned by

∗

= {a | a ∈ A, c(a)=+∞},

∗

= {a | a ∈ A, c(a)=−∞} (a: reorientation of a)

and ˜γ : A

∗

∪ B

∗

→ R of (2.53). It is noted that the existence of an optimal

ﬂow is equivalent to the boundedness of the cost (inf

cost(ϕ) > −∞) under

the assumption of feasibility.

Theorem 2.2.34. (1) A feasible ﬂow exists if and only if



{

c(a) | a ∈ C(S)}≥



{c(a) | a ∈ C(V \S)}

for each S ⊆ V ,whereC(S) is deﬁned by (2.49). Moreover, if the capacity

functions

c and c are integer-valued and there exists a (real-valued) feasible

ﬂow, then there exists an integer-valued feasible ﬂow.

(2) Assume that a feasible ﬂow exists. An optimal ﬂow exists if and only

if there exists no cycle of negative length with respect to ˜γ in the auxiliary

network

∞

=(V,A

∗

∪ B

∗

, ˜γ).

(3) If the capacity functions

c and c are integer-valued and there exists a

(real-valued) optimal ﬂow, then there exists an integer-valued optimal ﬂow.

Proof. (1) This is a theorem due to Hoﬀman [111], which may be regarded as

a variant of Theorem 2.2.30.

(2) The “only if” part is immediate from Theorem 2.2.33 ((i) ⇒ (iii) to

be speciﬁc). The “if” part can be shown by repeated modiﬁcations of feasible

ﬂows as in (2.56).

(3) This can be shown by repeated modiﬁcations of integral feasible ﬂows

as in (2.56), in which we can take ε = 1. Note that an initial integral feasible

ﬂow exists by (1).

The following basic facts are stated here for the convenience of reference.

The function γ : A → R is now interpreted as the arc-length function of a

network N =(V, A,γ).