URL : http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/ 3 (Web 19 9 )
12 ( ) 3 4 K 4 Pk 4 (k) = k (k − 1)(k − 2)(k − 3) = k 4 − 6k 3 + 11k 2 − 6k (409) −6 kn-1 k.4 .  (ii) k n , (i) m m = n(n − 1)/2 , k n − 1 –m , m = 4 × 3/2 = 6 . 3 , (iii) , n = 4 , K 4 : PG(k) = PG-c(k) — PG/c(k) (410) n, m − 1,
(i) m = 1
m — 1
G/e ,
(ii) m = 1
m – 1, −1 n
(iii) m = 1 −(m − 1) : ( 11 , , Menger ,
11.1
Hall
(mariage problem) ? {g1, g2, g3, g4}, {b1,b2,b3,b4,b5}
G(V 1 , V 2 ) . Vi 232: V2 V1 V2 . 。
Hall k k (      ) [      ] : k [     ] : h ).           , m – k 11.2 , E : F = (S1, S2, . . . , Sm) : E F  m ( ) E = {1, 2, 3, 4, 5, 6}, S 1 = S 2 = {1, 2}, S 3 = S 4 = {2, 3}, S 5 = {1, 4, 5, 6} ) F = (S 1 , S 2 , . . , S 5 )
11.3
,       , Hall
E = {b1, b2, b3, b4, b5, b6} = {1, 2, 3, 4, 5, 6} . F = (g1,g2,g3,g4,g5) = (S1,S2,S3,S4,S5)         , $1 = {1,2} S2 = {1,2}
217
$3 = {2,3} $4 = {2,3} S5 ll {1, 4, 5, 6} 233 ( ), F . 233: Hall
11.4  Hall
: m × n (m ≤ n) ..
M (i) 1 ≤ m ij ≤ n (ii) （ ）
(427) m = n 27.1 M     m < n m × n , M n — m ( ) E = {1, 2, 3, 4, 5} , M E M . F = (S1, S2, S3, S4, S5) . (427) Si Hall S 1 , S 2 , . . . ,
S2 ll {1,3} S'3 {4,5} ll {2,3} {1, 2} , F (4, 3, 5, 2, 1), (5, 1, 4, 3, 2)
(

Menger
11.5
vw- (   ) : vw- (   ) : (edge-disjoint path) : w v w (vertex-disjoint path) : v G : E , v w E1 = {ps,qs,ty,tz}, E2 = {uw,xw,yw,zw}. 234 w V V    , v : G 234 V 1 = {s, t}, V 2 = {p, q, y, z}. 2 G. ( E
（ ） 235 G , vw- 2 E1 = {vp, vq}, E2 = {pr, qr, qs}, E3 = {rw, sw}
vw- , vw- , 235:  Menger G.
12
236 ) 236: .  v w . ? II N : Ψ( a ) : a outdeg(x)：xz indeg(x)：zx 1 ,
（ ） 237 ( v - w ) ( = 6 237 237: 236 ,  v, w (cut) :
: 236 , 6 ) {xw, xz, yz, vz},  {xw, zw} 1 , indeg, outdeg , 236, 237
) = 6 12.1 238 ( ： V, V1, V2, ・・・, Vk-1, Vk, W , e i = ( Vi − 1 , Vi ) 238: V i , V i – 1 , ei , e i = ( V i , V i − 1 ) 238 . . e ; , )
, e2 (residual) Ψ(e i ),
(429) g(e i ) g(e i ) V i –1, V i p e ç φ(e ; ) p g(p) min g(e i ) l<i<k φ(e i ) φ(e ç ) + g(p)    (e ç L φ(e i ) φ(e ; ) − g(p)   (e ; ↓ φ   g(p) e1 , , e i g(p) g(p) , e1 p. , e2 (430) (431) (432) , e i p 1. e φ(e) = 0 2. v w  3. . 、3. φ            , 2.
12.2
U 239: U    V V , 88    , 1　, V w U 1 , , . (1) P1 v → a → d → w φ(v, a) = φ(a, d) = φ(d, w) = 0 (433) , P1 g(v,a)    =   Ψ(v,a) − φ(v,a) = 20 − 0 = 20 g(a,d)    =   Ψ(a,d) − φ(a,d) = 11 − 0 = 11 g(d, w)    =   Ψ(d, w) − φ(d, w) = 13 − 0 = 13 P1
(434) φ(v,a)    =    0 + g(p1) = 11 φ(a, d) =   0 + g(p1) = 11 φ(d, w) = 0 + g(p1) = 11 P2 v → b → c → w
P2
φ(v, b) = φ(b, c) = φ(c, w) = 0 (435) g(v,b)   =   Ψ(v,b) − φ(v,b) = 10 − 0 = 10 g(b,c)    =   Ψ(b,c) − φ(b,c) = 7 − 0 = 7 g(c,w)    =   Ψ(c,w) − φ(c,w) = 3 − 0 = 3 P2 g(p2) =
(435)(436) φ(v, b)    =    0 + g(p2) = 3 φ(b, c)    =    0 + g(p2) = 3 φ(c, w) = 0 + g(p2) = 3 .
> W 2
.  (a, c), (c, d) g(v,a)    =   Ψ(v,a) − φ(v,a) = 20 − 11 = 9 g(a,c) = φ(a,c) = 0 g(c, d)    =    φ(c, d) = 0 g(d, w)    =   Ψ(d, w) − φ(d, w) = 13 − 11 = 2 P3 min g(p3) ll k=(v,a),(a,c),(c,d),(d,w) = 0 φ(a, c) = 0 φ(c, d) = 0 φ(d,w) = 11 (436)
225
P4 φ(v, b) = 3 φ(b, c)
,  (c, d) g(v,b)    =   Ψ(v,b) − φ(v,b) = 10 − 3 = 7 g(b,c) = Ψ(b,c) − φ(b,c) = 7 − 3 = 4 g(c, d) = φ(c, d) = 0 g(d, w)    =   Ψ(d, w) − φ(d, w) = 13 − 11 = 2 P4 g(ps) k=(v,b),(b,c),(c,d),(d,w) = 0
11 + 3 = 14 240: , 11 - 4 + 7 = 14 11 + 3 = 14 (2)     240

226
( (1)
) ) ) (2) P1 v → a → w φ(a, w) = 0 φ(ν, a) = , P1 Φ(u,v) (437)
Φ(v, a) − φ(v, a) = 4 − 0 = 4 g(v, a) ll Φ(a, w) − φ(a, w) = 2 − 0 = 2 ll g(a, w) P1 g(p1) g(p1) (440) = 0+g(p1) = 2 φ( sfv,α) φ(a, w) 0 + g(p1) = 2 (441) (442)
, P2, P3 φ(ν, b) φ(b,w) = 0 + g(p 2 ) = 1 φ(v,c) 0 + g(p3) = 2 ll (444) (445) φ(c, w) =   0 + g(p3) = 2 (446) vb, aw, cw
ba 3 ba , v → a → b → w, v → c P4, P5 P4 , Φ(v, a) − φ(v, a) = 4 − 2 = 2 g(v,a) g(a, b) Φ(a, b) − φ(a, b) = 5 − 0 = 5 ll Φ(b, w) − φ(b, w) = 4 − 1 = 3 g(b, w) ll (447) (448) (449) P4 (450) g(k) = 2 min g(p4) k=(v,a),(a,b),(b,w)
(451) (452) (453) g(v,c)    =    Φ(v,c) − φ(v,c) = 5 − 2 = 3 (454) (455) (456) Φ(c, b) − φ(c, b) = 1 − 0 = 1 g(c, b) ll Φ(b, w) − φ(b, w) = 4 − 3 = 1 g(b, w) ll P5 9(P5) min k=(v,c),(c,b),(b,w) g(k) = 1 (457) P5 (443) ,
4 + 1 + 3 = 8
.