Murota K. Matrices and Matroids for Systems Analysis

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

282 5. Polynomial Matrix and Valuated Matroid

where C = {x

}.ForB = {x

} and B



= {x

} we have

ω(B)=ω(B



)=0andω(B −x

+ x

)=ω(B



+ x

−x

)=1fori =1, 2and

j =3, 4. 2

Example 5.2.4. This is an example from combinatorial optimization due to

Murota [224]. Let G =(V, A) be a directed graph, and S and T be disjoint

subsets of the vertex set V .ByL (⊆ A) we denote (the arc set of) a Menger-

type vertex-disjoint linking from S to T ,andby∂

L (⊆ S) the set of its

initial vertices. Put B = {∂

L | L ∈L}, where L (⊆ 2

) denotes the family of

maximum linkings. It is well known (see also the augmenting-path argument

below) that B forms the basis family of a matroid (S, B). Given a cost function

γ : A → R, deﬁne a function ω : B→R by

ω(B)=−min

{



a∈L

γ(a) | ∂

L = B,L ∈L} (B ∈B).

By deﬁnition, −ω(B) means the minimum cost of a maximum linking L with

initial vertex set B.

The function ω is a valuation of (S, B), satisfying the exchange axiom

(VM). To see this, let L, L



∈Lbe such that ∂

L = B, ∂



= B



ω(B)=−



a∈L

γ(a), and ω(B



)=−



a∈L



γ(a). For u ∈ B \B



,astandard

augmenting-path argument shows that there exists P ⊆ (L\L



)∪(L



\L) such

that (P ∩L)∪(

P ∩ L



) forms a directed path from u to some v ∈ B



\B, where

P ∩ L



means the set of arcs in P ∩L



reoriented. Note the maximality of L and



is used here. For

L =(L\(P ∩L))∪(P ∩L



)and



=(L



\(P ∩L



))∪(P ∩L),

we have



∈L, ∂

L = B − u + v, ∂



= B



+ u − v, and therefore,

ω(B)+ω(B



)=−



a∈L

γ(a) −



a∈L



γ(a)=−



a∈

γ(a) −



a∈



γ(a)

≤ ω(B − u + v)+ω(B



+ u − v).

An example of this kind is provided by G =(V, A) with V = S ∪ T , S =

}, T = {t

A = {(s

), (s

)},

γ(a) = 0 except for γ(s

)=1andγ(s

) = 2. We have, for example,

ω({s

})=0,ω({s

})=−1, ω({s

})=−2. This valuation is not

separable, since the system of equations α + p

+ p

= ω({s

})(i = j)in

(α, p

) ∈ R

has no solution. 2

5.2.3 Basic Operations

Basic operations for a valuated matroid, such as dual, restriction, contraction,

truncation, and elongation, are explained here, whereas other more sophisti-

cated operations such as union are treated in §5.2.6.

5.2 Valuated Matroid 283

Let M =(V, B,ω) be a valuated matroid. For α ∈ R and 0 ≤ β ∈ R,the

function ω

α,β

: B→R deﬁned by

α,β

(B)=α + βω(B)(B ∈B)

is a matroid valuation. For p : V → R we deﬁne ω[p]:B→R (or ω[p]:

→ R ∪ {−∞})by

ω[p](B)=ω(B)+



{p(u) | u ∈ B}. (5.16)

M[p]=(V,B,ω[p]) is again a valuated matroid, called a similarity transfor-

mation of M by p. A linear weighting is a similarity transformation of the

trivial valuation.

The dual of M =(V,B,ω) is a valuated matroid M

∗

=(V,B

∗

,ω

∗

) deﬁned

∗

= {B ⊆ V | V \ B ∈B},ω

∗

(B)=ω(V \ B)forB ∈B

∗

The restriction and the contraction of M =(V,B,ω)toU (⊆ V )are

deﬁned as follows (Dress–Wenzel [57]). Let (U, B

) and (U, B

) be the re-

striction and the contraction of the underlying matroid (V,B)toU . Similarly

for (V \U, B

V \U

) and (V \U, B

V \U

). Fix a base I of (V \U, B

V \U

) and a base

J of (V \ U, B

V \U

), and deﬁne ω

: B

→ R and ω

: B

→ R by

(X)=ω(I ∪X),X∈B

; ω

(X)=ω(J ∪ X),X∈B

Theorem 5.2.5.

(1) M

=(U, B

,ω

) is a valuated matroid, and for I,I



∈B

V \U

there

exists α

I,I



∈ R, independent of X ∈B

, such that



(X)=ω

(X)+α

I,I



,X∈B

(2) M

=(U, B

,ω

) is a valuated matroid, and for J, J



∈B

V \U

there

exists β

J,J



∈ R, independent of X ∈B

, such that



(X)=ω

(X)+β

J,J



,X∈B

Proof. (1) It is obvious that ω

satisﬁes (VM). We may assume I \ I



= {u}

and I



\ I = {u



}.ForX, Y ∈B

weapply(VM)to(I ∪ X, I



∪ Y )and

u ∈ (I ∪ X) \ (I



∪ Y ) to obtain

ω(I ∪ X)+ω(I



∪ Y ) ≤ ω(I



∪ X)+ω(I ∪ Y ),

since u



is the only exchangeable element of (I



∪ Y ) \ (I ∪ X). The reverse

inequality can be shown similarly, and therefore

ω(I



∪ X) − ω(I ∪ X)=ω(I



∪ Y ) − ω(I ∪ Y )=α

I,I



284 5. Polynomial Matrix and Valuated Matroid

(2) This can be proven similarly.

Let (V,B

) and (V,B

) denote the truncation to k and the elongation

to l, respectively, of the underlying matroid (V,B) of a valuated matroid

M =(V, B,ω), where k ≤ r ≤ l. By deﬁnition,

= {I ⊆ V ||I| = k, ∃B : I ⊆ B ∈B}, (5.17)

= {S ⊆ V ||S| = l, ∃B : S ⊇ B ∈B}. (5.18)

For a spanning set S

of (V,B) and an independent set I

of (V,B), deﬁne

k,S

: B

→ R and ω

l,I

: B

→ R by

k,S

(I) = max{ω(B) | I ∪ S

⊇ B ⊇ I,B ∈B} (I ∈B

), (5.19)

l,I

(S) = max{ω(B) | S ∩ I

⊆ B ⊆ S, B ∈B} (S ∈B

). (5.20)

The following theorem (Murota [229]) states that these constructions yield

valuated matroids. We call M

k,S

=(V, B

,ω

k,S

)thetruncation of M to

rank k relative to a spanning set S

,andM

l,I

=(V,B

,ω

l,I

)theelongation

of M to rank l relative to an independent set I

Theorem 5.2.6. For a valuated matroid M =(V,B,ω) of rank r,letω

k,S

and ω

l,I

be deﬁned by (5.19) and (5.20) for a spanning set S

and an inde-

pendent set I

,where0 ≤ k ≤ r ≤ l ≤|V |.

(1) M

k,S

=(V,B

,ω

k,S

) is a valuated matroid (of rank k).

(2) M

l,I

=(V,B

,ω

l,I

) is a valuated matroid (of rank l).

(3) (ω

r+s,I

)

∗

=(ω

∗

)

(r+s)

∗

for s with 0 ≤ s ≤|V |−r,where(r +s)

∗

|V |−(r + s) and I

∗

= V \ I

Proof. First note that (2) follows from (1) and (3), and that (3) can be proven

by a direct calculation:

(ω

∗

)

(r+s)

∗

(I) = max{ω

∗



) | I ∪ I

∗

⊇ B



⊇ I}

= max{ω(B) | (V \ I) ∩ I

⊆ B ⊆ V \ I}

= ω

r+s,I

(V \ I)=(ω

r+s,I

)

∗

(I),

where I ⊆ V and |I| =(r + s)

∗

Next, we show that the proof of (1) reduces to the case of S

= V . Deﬁne

p : V → R by

p(u)=



α (u ∈ S

)

0(u ∈ V \ S

)

with a suﬃciently large number α, and consider ω[p] of (5.16), which is also

a valuation of (V, B). Then we have

k,S

(I)=(ω[p])

k,V

(I) −



{p(u) | u ∈ I}−α(r − k).

5.2 Valuated Matroid 285

Hence it suﬃces to prove that (ω[p])

k,V

is a valuation, which is done later in

Lemma 5.2.21.

For two valuated matroids M

=(V

, B

,ω

)andM

=(V

, B

,ω

) with

disjoint ground sets (V

∩ V

= ∅), the direct sum is a valuated matroid

M =(V

∪ V

, B,ω) deﬁned by B = {B

∪ B

| B

∈B

} and

ω(B)=ω

(B ∩V

)+ω

(B ∩V

). It is noted that this construction does not

necessarily yield a valuated matroid if V

∩ V

= ∅.

5.2.4 Greedy Algorithms

A greedy algorithm works for valuated matroids and this property in turn

characterizes valuated matroids.

Let M =(V,B,ω) be a valuated matroid. For B ∈B, u ∈ B,andv ∈ V \B,

we deﬁne

ω(B,u,v)=ω(B − u + v) − ω(B), (5.21)

which we refer to as the exchange gain of ω at B for the pair (u, v). Note

that ω(B, u,v)=−∞ if B − u + v ∈B.

The following fact is most fundamental, showing the local optimality im-

plies the global optimality. This is due to Dress–Wenzel [57].

Theorem 5.2.7. Let B ∈B.Thenω(B) ≥ ω(B



) for any B



⊆ V if and

only if

ω(B,u,v) ≤ 0 for any u ∈ B and v ∈ V \ B. (5.22)

Proof.Weproveω(B) ≥ ω(B



) by induction on d = |B



\B|. Obviously, this

is true for d =0.Ford ≥ 1, there exist u ∈ B \ B



and v ∈ B



\ B such that

ω(B)+ω(B



) ≤ ω(B −u + v)+ω(B



+ u − v),

in which ω(B − u + v) ≤ ω(B) by (5.22) and ω(B



+ u − v) ≤ ω(B)bythe

induction hypothesis. Hence follows ω(B



) ≤ ω(B).

For the maximization of ω the greedy algorithm of Dress–Wenzel [54] starts

with an arbitrary base B

= {u

, ···,u

}∈Bwith an arbitrary ordering

of the elements, and repeats the following for k =1, 2, ···,r (= rank M):

Find v

∈ (V \B

k−1

) ∪{u

} = V \{v

, ···,v

k−1

k+1

, ···,u

} such

that

ω(B

k−1

− u

+ v

) ≥ ω(B

k−1

− u

+ v)(∀v ∈ (V \ B

k−1

) ∪{u

})

and put B

= B

k−1

− u

+ v

In this way an optimal base (maximizing ω) can be found with r(|V |−r)+1

function evaluations of ω. Moreover, the success of this algorithm character-

izes valuations, a result of Dress–Wenzel [54].

286 5. Polynomial Matrix and Valuated Matroid

Theorem 5.2.8. Let (V,B) be a matroid, and ω : B→R.Ifω is a valuation,

the above algorithm yields an optimal base. Conversely, if for any p ∈ R

the

above algorithm applied to ω[p] yields an optimal base with respect to ω[p],

then ω is a valuation.

Proof. The algorithm works for a valuation due to Lemma 5.2.9 below, applied

to a sequence of the contractions of (V,B,ω)toV \{v

, ···,v

k−1

} (k =

1, 2, ···). For the converse, suppose that (VM) fails for B,B



∈Band u

∗

∈

B \ B



. Note that |B \ B



|≥2. Deﬁne p : V → R by

p(v)=

⎧

⎪

⎨

⎪

⎩

0(v = u

∗

)

−ω(B,u

∗

,v)(v ∈ B



\ B, B − u

∗

+ v ∈B)

(v ∈ B



\ B, B − u

∗

+ v ∈B)

(v ∈ B ∩ B



)

−M

(v ∈ V \ (B



∪{u

∗

}))

with suﬃciently large positive numbers M

and M

such that M

- M

Then B



is the unique maximizer of ω[p]andω[p](B) ≥ ω[p](B − u

∗

+ v)

for v ∈ V \ B. The latter means that the algorithm applied to B

= B with

= u

∗

fails by choosing v

= u

∗

The proof above relies on the following fundamental fact due to Shioura

[298].

Lemma 5.2.9. Let (V,B,ω) be a valuated matroid, ˆu ∈ B ∈B,andˆv ∈

(V \B)∪{ˆu}.Ifω(B − ˆu +ˆv) = max

v∈(V \B)∪{ˆu}

ω(B − ˆu + v), there exists

B ∈B

such that ˆv ∈

B and ω(

B) = max ω.

Proof.TakeanyB



∈Bwith ω(B



) = max ω.Ifˆv ∈ B



, put

B = B



Otherwise, ˆv ∈ (B −ˆu+ˆv)\B



, and therefore, there exists u ∈ B



\(B −ˆu+ˆv)

such that

ω(B − ˆu +ˆv)+ω(B



) ≤ ω(B − ˆu + u)+ω(B



+ˆv − u),

which must be satisﬁed with equality since ω(B − ˆu + u) ≤ ω(B − ˆu +ˆv)and

ω(B



+ˆv − u) ≤ max ω = ω(B



). Hence

B = B



+ˆv − u is a valid choice.

Example 5.2.10. In case ω is deﬁned by an m × n rational matrix A(s)of

rank m (cf. Example 5.2.3), the exchange gain (5.21) can be represented as

ω(B,i,j) = deg

(A[R, B]

−1

A[R, C \ B])

(i ∈ B,j ∈ C \ B), (5.23)

where the right-hand side designates the degree of the (i, j) entry of the

m ×(n −m) rational matrix A[R, B]

−1

A[R, C \B]. Hence, by Theorem 5.2.7,

we see

B maximizes deg

det A[R, B]

⇐⇒ A[R, B]

−1

A[R, C \ B] is a proper rational matrix. (5.24)

5.2 Valuated Matroid 287

Remark 5.2.11. Greedy algorithms are fundamental in combinatorial op-

timization. Investigation of variants of greedy algorithms leads to many

interesting combinatorial structures. See, for example, Edmonds [68, 69],

Faigle [74], Lawler [171], and Welsh [333] (matroids and polymatroids);

Korte–Lov´asz–Schrader [163] (greedoids); Bouchet [15] and Chandrasekaran–

Kabadi [30] (delta matroids); Dress–Terhalle [51, 52, 53] (variants of val-

uated matroids); and Dress–Wenzel [55] and Murota [222] (valuated delta

matroids). 2

5.2.5 Valuated Bimatroid

In §2.3.7 we explained about bimatroids, which can be regarded as a variant

of matroids (see (2.86) in particular). Following Murota [221] we introduce

here a variant of valuated matroids in a similar vein.

Let S and T be disjoint ﬁnite sets and δ :2

×2

→ R ∪{−∞} be a map

such that

δ(X, Y )=ω((S \ X) ∪ Y )(X ⊆ S, Y ⊆ T ) (5.25)

for some valuated matroid (S ∪ T,ω) with ω(S) = −∞. Then (S, T, Λ) with

Λ = {(X, Y ) | δ(X, Y ) = −∞,X⊆ S, Y ⊆ T }

is a bimatroid due to (2.86). Note that (∅, ∅) ∈ Λ and that |X| = |Y | for

(X, Y ) ∈ Λ.

The axiom (VM) for ω can be translated into a condition on δ that (VB-1)

and (VB-2) below hold true for any (X, Y ) ∈ Λ and (X



) ∈ Λ:

(VB-1) For any x



∈ X



\ X, either (a1) or (b1) (or both) holds,

where

(a1) ∃y



∈ Y



\ Y :

δ(X, Y )+δ(X



) ≤ δ(X + x



,Y + y



)+δ(X



− x



− y



(b1) ∃x ∈ X \ X



δ(X, Y )+δ(X



) ≤ δ(X − x + x



,Y)+δ(X



− x



+ x, Y



(VB-2) For any y ∈ Y \Y



, either (a2) or (b2) (or both) holds, where

(a2) ∃x ∈ X \ X



δ(X, Y )+δ(X



) ≤ δ(X − x, Y − y)+δ(X



+ x, Y



+ y),

(b2) ∃y



∈ Y



\ Y :

δ(X, Y )+δ(X



) ≤ δ(X, Y − y + y



)+δ(X



− y



+ y).

Atriple(S, T, δ) (or quadruple (S, T, Λ, δ)) satisfying (VB-1) and (VB-2) is

named a valuated bimatroid.

We are now interested in optimal linked pairs (X, Y ) ∈ Λ of a speciﬁed

size k with respect to the value of δ. Deﬁne

r = max{|X||∃(X, Y ) ∈ Λ},

= {(X, Y ) ∈ Λ ||X| = |Y | = k} (0 ≤ k ≤ r),

= max{δ(X, Y ) | (X, Y ) ∈ Λ

} (0 ≤ k ≤ r),

= {(X, Y ) ∈ Λ

| δ(X, Y )=δ

} (0 ≤ k ≤ r).

288 5. Polynomial Matrix and Valuated Matroid

The optimal linked pairs can be chosen to be nested (Murota [221]).

Theorem 5.2.12. For any (X

) ∈M

with 1 ≤ k ≤ r − 1, there exist

) ∈M

(0 ≤ l ≤ r, l = k) such that

(∅ =) X

⊂ X

⊂···⊂X

k−1

⊂ X

k+1

⊂···⊂X

(∅ =) Y

⊂ Y

⊂···⊂Y

k−1

⊂ Y

k+1

⊂···⊂Y

Proof.Takeany(X

−

) ∈M

k−1

and apply (VB-1) to (X, Y )=(X

−



)=(X

) and any x



∈ X

\ X

−

(= ∅). In case (a1),

k−1

+ δ

= δ(X

−

)+δ(X

)

≤ δ(X

−

+ x



−

+ y



)+δ(X

− x



− y



) ≤ δ

+ δ

k−1

and therefore (X

k−1

)=(X

− x



− y



) is eligible. In case (b1),

k−1

+ δ

= δ(X

−

)+δ(X

)

≤ δ(X

−

− x + x



−

)+δ(X

− x



+ x, Y

) ≤ δ

k−1

+ δ

which shows (

−

)=(X

−

− x + x



−

) ∈M

k−1

with |

−

\ X

| =

−

\ X

|−1. We now apply the same argument to (

−

). This process

eventually reaches the case (a1).

The nesting property implies the following fact (Murota [221]).

Theorem 5.2.13. The sequence (δ

,δ

, ···,δ

) is concave, i.e.,

k−1

+ δ

k+1

≤ 2δ

(1 ≤ k ≤ r − 1).

Proof.Take(X

k−1

) ∈M

k−1

and (X

k+1

) ∈M

k+1

with X

k−1

⊂

k+1

and Y

k−1

⊂ Y

k+1

(cf. Theorem 5.2.12). By (VB-1) there exist x ∈

k+1

\ X

k−1

and y ∈ Y

k+1

\ Y

k−1

such that

k−1

+ δ

k+1

≤ δ(X

k−1

+ x, Y

k−1

+ y)+δ(X

k+1

− x, Y

k+1

− y) ≤ 2δ

The nesting property revealed in Theorem 5.2.12 justiﬁes the following

incremental greedy algorithm for computing δ

for k =0, 1, ···,r.

Greedy algorithm for δ

(k =1, 2, ···)

:= ∅; Y

:= ∅;

for k := 1, 2, ···do

Find x ∈ S \X

k−1

, y ∈ T \ Y

k−1

maximizing δ(X

k−1

+ x, Y

k−1

+ y)

and put X

:= X

k−1

+ x, Y

:= Y

k−1

+ y,andδ

:= δ(X

The iteration stops when δ(X

)=−∞, and then we see r = k − 1. This

algorithm involves O(r|S||T |) evaluations of δ to compute the whole sequence

(δ

,δ

, ···,δ

5.2 Valuated Matroid 289

For a valuated bimatroid δ :2

× 2

→ R ∪ {−∞} we deﬁne a function

δ :2

× 2

→ R by

δ(X, Y ) = max{δ(X



) | X



⊆ X, Y



⊆ Y }.

Note that

δ(X, Y ) is ﬁnite for all (X, Y ) since δ(∅, ∅) > −∞.

Theorem 5.2.14. The function

δ :2

× 2

→ R derived from a valuated

bimatroid δ :2

× 2

→ R ∪ {−∞} satisﬁes

δ(X, Y )+

δ(X



) ≥

δ(X ∪ X



,Y ∩ Y



δ(X ∩ X



,Y ∪ Y



)

(X, X



⊆ S; Y,Y



⊆ T ).

Proof. It suﬃces to show

δ(X, Y )+

δ(X + x, Y + y) ≥

δ(X + x, Y )+

δ(X, Y + y), (5.26)

δ(X + x

,Y)+

δ(X + x

,Y) ≥

δ(X, Y )+

δ(X + {x

},Y), (5.27)

δ(X, Y + y

) ≥

δ(X, Y )+

δ(X, Y + {y

}), (5.28)

where x, x

∈ S \ X and y, y

∈ T \ Y .

To show (5.26) take X

⊆ X + x, Y

⊆ Y , X

⊆ X,andY

⊆ Y + y such

that

δ(X + x, Y )=δ(X

)and

δ(X, Y + y)=δ(X

). If x ∈ X

,weare

done, since

δ(X, Y ) ≥ δ(X

)and

δ(X + x, Y + y) ≥ δ(X

). Otherwise,

apply (VB-1) for x ∈ X

\ X

to obtain either (a) δ(X

)+δ(X

) ≤

δ(X

−x, Y

−y

)+δ(X

+ x, Y

+ y

) ≤

δ(X, Y )+

δ(X + x, Y + y) for some

∈ Y

or (b) δ(X

)+δ(X

) ≤ δ(X

−x + x

)+δ(X

−x

x, Y

) ≤

δ(X, Y )+

δ(X + x, Y + y) for some x

∈ X

\ X

To show (5.27) take X

⊆ X, X

⊆ X +{x

},andY

⊆ Y such that

δ(X, Y )=δ(X

)and

δ(X + {x

},Y)=δ(X

). If x

∈ X

,weare

done, since

δ(X+x

,Y) ≥ δ(X

)and

δ(X+x

,Y) ≥ δ(X

). Otherwise,

apply (VB-1) for x

∈ X

\ X

to obtain either (a) δ(X

)+δ(X

) ≤

δ(X

+ x

+ y

)+δ(X

−x

−y

) ≤

δ(X + x

,Y)+

δ(X + x

,Y)for

some y

∈ Y

or (b) δ(X

)+δ(X

) ≤ δ(X

−x + x

)+δ(X

−

+ x, Y

) ≤

δ(X + x

,Y)+

δ(X + x

,Y) for some x ∈ X

\ X

The ﬁnal case (5.28) can be shown similarly.

Example 5.2.15. From an m × n rational matrix A(s) with R =Row(A)

and C = Col(A), a valuated bimatroid (R, C, δ) is deﬁned by

δ(I,J) = deg

det A[I,J](I ⊆ R, J ⊆ C). (5.29)

The associated valuated matroid in (5.25) is the one deﬁned by an m×(m+n)

matrix [I

A] according to (5.15) (see also Fig. 2.12). A weaker form of the

nesting property of Theorem 5.2.12 in this special case has been observed by

Svaricek [306], [307, Satz 6.23]. The concavity of the sequence δ

in Theorem

5.2.13 is equivalent to the monotone decrease of the sequence t

= δ

−δ

k−1

which is called the sequence of contents at inﬁnity in connection to the Smith–

McMillan form at inﬁnity of A(s) (cf. Theorem 5.1.5). 2

290 5. Polynomial Matrix and Valuated Matroid

Example 5.2.16. Another valuated bimatroid arises from a polynomial ma-

trix A(s). For a number α and a polynomial f(s) we denote by ord

(α)

f(s)

the maximum p such that (s − α)

divides f(s). Then

(α)

(I,J)=−ord

(α)

det A[I,J](I ⊆ R, J ⊆ C) (5.30)

deﬁnes a valuated bimatroid (R, C, δ

(α)

), where R =Row(A)andC =

Col(A). This is in fact a variant of the valuated bimatroid in Example 5.2.15,

since δ

(α)

(I,J)forA(s) coincides with δ(I,J)forA(α +1/s). The expo-

nentto(s − α) in the factorization of the kth determinantal divisor d

(s)

of A(s) is given by min{ord

(α)

det A[I,J] ||I| = |J| = k}, which is equal to

−max{δ

(α)

(I,J) ||I| = |J| = k}. Then Theorem 5.2.13 implies that (k−1)st

invariant factor e

k−1

(s)=d

k−1

(s)/d

k−2

(s) divides the kth invariant factor

(s)=d

(s)/d

k−1

(s)fork =2, ···,r (cf. Theorem 5.1.1). 2

Example 5.2.17. Let G =(V

−

; A) be a bipartite graph and w : A → R

be a weight function. A valuated bimatroid (V

−

,δ) is deﬁned by

δ(I,J) = max{w(M) | M: matching,∂

M = I,∂

−

M = J}

(I ⊆ V

,J ⊆ V

−

Then Theorem 5.2.13 shows the concavity of the sequence of

= max{w(M ) | M: k-matching}.

5.2.6 Induction Through Bipartite Graphs

A valuated matroid can be transformed into another valuated matroid

through matchings in a bipartite graph. This is an extension of the well-

known fact (cf. §2.3.6) that a matroid can be transformed into another ma-

troid through a bipartite graph.

Let G =(V

−

; A) be a bipartite graph, w : A → R a weight function,

and M =(V

, B,ω) a valuated matroid. Then, by Theorem 2.3.38,

B = {∂

−

M | M : matching,∂

M ∈B}

forms the basis family of a matroid, provided

B = ∅. Here ∂

M ⊆ V

and

∂

−

M ⊆ V

−

denote the sets of vertices incident to M . Deﬁne ˜ω :

B→R by

˜ω(X) = max

{w(M)+ω(∂

M) | M : matching,∂

M ∈B,∂

−

M = X},

X ∈

B. (5.31)

This construction yields a valuated matroid as follows (Murota [227]).

Theorem 5.2.18.

M =(V

−

B, ˜ω) is a valuated matroid, provided

B = ∅.

5.2 Valuated Matroid 291

Proof. The induction through G =(V

−

; A) with w : A → R can be

decomposed into two stages. Let G

=(V

,A; A

)andG

−

=(A, V

−

; A

−

)

be bipartite graphs with

= {(v, a) | v ∈ V

,a∈ A, v = ∂

a},

−

= {(a, v) | v ∈ V

−

,a∈ A, v = ∂

−

a},

and deﬁne w

: A

→ R and w

−

: A

−

→ R by

(v, a)=w(a),w

−

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

It is not diﬃcult to see that the transformation of M =(V

, B,ω)by(G, w)

is equivalent to the transformation of M to M

◦

=(A, B

◦

,ω

◦

)by(G

)

followed by the transformation of M

◦

by (G

−

). Hence it suﬃces to con-

sider the following two special cases of G =(V

−

; A)andw : A → R:

Case 1: deg v =1for∀ v ∈ V

−

Case 2: deg v =1for∀ v ∈ V

,andw(a)=0for∀ a ∈ A.

In either case we shall show (VM) for ˜ω, i.e., for B, B



∈

B and u ∈ B \ B



there exists v ∈ B



\ B such that

˜ω(B)+˜ω(B



) ≤ ˜ω(B − u + v)+˜ω(B



+ u − v). (5.32)

Fix u ∈ B \ B



Case 1: For v ∈ V

−

let ϕ(v) denote the unique element of V

such that

(ϕ(v),v) ∈ A. Then |ϕ

−1

(x) ∩ B|≤1, |ϕ

−1

(x) ∩ B



|≤1 for all x ∈ V

,and

ϕ(B),ϕ(B



) ∈B, where ϕ(B)={ϕ(v) | v ∈ B}. By deﬁnition, we have

˜ω(B)=ω(ϕ(B)) + ¯w(B), ˜ω(B



)=ω(ϕ(B



)) + ¯w(B



)

with ¯w(B)=



v∈B

w(ϕ(v),v).

If ϕ(u) ∈ ϕ(B



), then ϕ(u)=ϕ(v) for some v ∈ B



\ B,and

ω(ϕ(B − u + v)) + ω(ϕ(B



+ u − v)) = ω(ϕ(B)) + ω(ϕ(B



)),

¯w(B − u + v)+ ¯w(B



+ u − v)= ¯w(B)+ ¯w(B



). (5.33)

Consequently, (5.32) holds true with equality. If x = ϕ(u) ∈ ϕ(B



), then by

(VM), there exists y ∈ ϕ(B



) \ ϕ(B) with

ω(ϕ(B)) + ω(ϕ(B



)) ≤ ω(ϕ(B) − x + y)+ω(ϕ(B



)+x − y)

= ω(ϕ(B −u + v)) + ω(ϕ(B



+ u − v)),

where v ∈ B



\ B, ϕ(v)=y. Combination of this and (5.33) yields (5.32).

Case 2: We may restrict ourselves to a further special case where

∃t ∈ V

−

: deg t =2, deg v =1(∀ v ∈ V

−

\{t}),