Principles of Mathematics in Operations Research

210 Solutions

Problems of Chapter 2

2.1 (a)

[A\\h] =

234 5 6 78 9 10 11 12 13

10000000 0 0 0 0

000000010 0 0 0

1 1000000 0 0 0 0

011000010 0 0 0

001100001 0 0 0

000110000 0 1 1

000011000 1 0 0

000000101 1 0 1

000001100 0 1 0

a + b —> b; a + b —)• a; b + c —> c; c + d —)• d\

d + e -» e; e + /->-/; f + g -^ g; g + i -> i; h + i -> i

[A\\h

h\N

10000000

0 1000000

00100000

00010000

00001000

00000 100

000000 10

00000001

0

10000

10000

10000

00000

01000

0 10 11

0 1111

0110 1

c

0000000000000

D

010000000

110000000

111000000

111100000

111110000

111111000

111111100

0000000 10

111111111

Fig. S.l. The tree T in Problem2.1

Each basis corresponds to a spanning tree T in G = (V,E), where
T C E connects every vertex and ||T|| = ||V|| — 1. Here, we have T =