BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————————————–

NGUYỄN THỊ THANH THỦY

MATROID VỚI LÝ THUYẾT ĐỒ THỊ
VÀ MỘT SỐ ỨNG DỤNG TRONG TỐI ƯU TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC

HÀ NỘI - 2017


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————————————–

NGUYỄN THỊ THANH THỦY

MATROID VỚI LÝ THUYẾT ĐỒ THỊ
VÀ MỘT SỐ ỨNG DỤNG TRONG TỐI ƯU TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC

Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60 46 01 12

Người hướng dẫn khoa học:

TS. Trần Minh Tước


Mục lục

Lời mở đầu

1

1 Một số kiến thức chuẩn bị

3

1.1

1.2

1.3

Lý thuyết matroid . . . . . . . . . . . . . . . . . . . . .

3

1.1.1

Định nghĩa matroid . . . . . . . . . . . . . . . . .

3

1.1.2

Tiên đề cơ sở . . . . . . . . . . . . . . . . . . . .


1.2.2

Đồ thị đối ngẫu . . . . . . . . . . . . . . . . . . .

18

1.2.3

Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . .

19

Một số tính chất liên hệ giữa matroid với đồ thị . . . . .

20

2 Một số liên hệ giữa matroid với lý thuyết đồ thị
2.1

2.2

22

Tính đối ngẫu của matroid đồ thị . . . . . . . . . . . . .

22

2.1.1



Sử dụng thuật toán tham lam giải quyết bài toán trên
matroid có trọng số . . . . . . . . . . . . . . . . . . . . .

35

3.1.1

Bài toán thực tế

. . . . . . . . . . . . . . . . . .

35

3.1.2

Đưa bài toán về matroid có trọng số . . . . . . .

36

3.1.3

Thuật toán . . . . . . . . . . . . . . . . . . . . .

37

Hệ đại diện phân biệt . . . . . . . . . . . . . . . . . . . .

39


1.1

Đồ Thị H . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Đồ Thị H1 . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3

Vòng C1 . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.4

Vòng C2 . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.5

Vòng C3 . . . . . . . . . . . . . . . . . . . . . . . . . . .

11


. . . . . . . . . . .

20

2.1

Đồ thị H2 . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.2

Xây dựng đối ngẫu hình học của một đồ thị phẳng . . .

24

2.3

Xây dựng đối ngẫu hình học của một đồ thị phẳng . . .

25

2.4

Phép đồng nhất đỉnh và phép tách đỉnh . . . . . . . . .

29

2.5


43

Công nhân y1 , y2 và công việc x1 , x2 . Cho p (x1 ) < p (x2 )

44

iii


DANH SÁCH HÌNH VẼ

DANH SÁCH HÌNH VẼ

Lời mở đầu
1. Lý do chọn đề tài
Lý thuyết matroid được giới thiệu lần đầu tiên bởi Hassler Whitney
vào năm 1935 và được BL Van Der Wearden độc lập đưa ra ngay sau đó.
Cả hai nhà toán học đều quan tâm đến việc xây dựng một mô tả chung
về “sự độc lập” với các tính chất liên quan chặt chẽ đến đại số tuyến tính
và lý thuyết đồ thị. Lý thuyết này nghiên cứu về sự gắn kết của cấu trúc
hình học mang tính trừu tượng (matroid) với cấu trúc hình học mang
tính cụ thể. Mặc dù ra đời khá muộn nhưng việc nghiên cứu matroid đã
phát triển và trở thành một lý thuyết hoàn chỉnh và có nhiều ứng dụng.
Lý thuyết matroid đã tổng quát hóa được những tính chất về sự độc lập
tuyến tính, phụ thuộc tuyến tính trong không gian vectơ và có nhiều
ứng dụng với lý thuyết đồ thị. Bên cạnh đó, phương pháp tham lam để
giải quyết nhiều bài toán tối ưu tổ hợp đã được biểu diễn hiệu quả bằng
ngôn ngữ của matroid. Trong một thời gian rất ngắn so với lịch sử toán
học, cho đến nay, lý thuyết matroid đã nhanh chóng trở thành một lĩnh
vực đặc biệt của toán học, một dạng hiện đại của hình học, tiêu chuẩn

hiểu biết cho bản thân về lý thuyết matroid và văn bản luận văn có thể
là tài liệu tham khảo hữu ích cho những ai quan tâm.

2


Chương 1
Một số kiến thức chuẩn bị
Trong chương này trình bày một số khái niệm cơ bản nhất về lý thuyết
matroid và lý thuyết đồ thị.

1.1

Lý thuyết matroid

1.1.1

Định nghĩa matroid

Đầu tiên chúng ta sẽ tìm hiểu: Matroid là gì? Khái niệm được đưa ra
sau đây dựa trên các tập con độc lập của tập nền S cùng với một số ví
dụ giúp ta có hình dung đầu tiên về matroid. Ngoài ra ta có thể định
nghĩa matroid bằng các khái niệm tương đương dựa trên tập cơ sở, tập
vòng hay hàm hạng được trình bày trong các mục sau.
Định nghĩa 1.1.1. Matroid là một cặp M gồm tập hữu hạn S và họ
F các tập con của S được gọi là các tập độc lập của M khi và chỉ khi
thỏa mãn các điều kiện sau:
M(1i) ∅ ∈ F .
M(2i) Nếu X ∈ F và Y ⊆ X thì Y ∈ F .
M(3i) Nếu U, V ∈ F và |U | = |V |+1 thì sẽ tồn tại phần tử x ∈ U −V

Matroid xác định như trên gọi là matroid vòng của G.
Ví dụ 1.1.3. Cho tập S hữu hạn phần tử.
Xét họ F1 = {∅} khi đó ta có (S, F1 ) là một matroid được gọi là
matroid tầm thường.
4


Xét họ F2 = P(S) = 2S khi đó ta có (S, F2 ) là một matroid được
gọi là matroid rời rạc.
1.1.2

Tiên đề cơ sở

Cho matroid M = (S, F ). Xét họ không rỗng B có phần tử là các tập
con độc lập lớn nhất của S trong M. Vì các phần tử của B là các tập
độc lập nên B là họ các tập độc lập của M.
Bổ đề 1. Nếu B1 , B2 là cơ sở của matroid M thì |B1 | = |B2 |.
Định lý 1.1.1. Một Matroid M bao gồm một tập hữu hạn khác rỗng E
và một họ khác rỗng B các tập con của E (được gọi là cơ sở) khi và chỉ
khi thỏa mãn các điều kiện sau:
B(1i) Không có cơ sở nào chứa cơ sở nào.
B(2i) Nếu B1 và B2 là cơ sở và e là phần tử bất kỳ của B1 , khi đó tồn
tại một phần tử f của B2 sao cho (B1 − {e} ∪ {f }) là một cơ sở.
Nếu lấy ra một phần tử từ B1 , khi đó tồn tại một phần tử trong B2
sao cho có một cơ sở mới B3 hình thành khi thêm phần tử đó vào B1 .
Chứng minh. Ta chứng minh rằng họ B được xác định như trên thỏa
mãn hai điều kiện B(1i), B(2i) của định lý 1.1.1.
Xét B1 , B2 ∈ B, B1 = B2 , mà theo bổ đề 1 ta có số phần tử của các
cơ sở bằng nhau |B1 | = |B2 |, hiển nhiên B(1i) được thỏa mãn.
Cho B1 − x và B2 là hai tập độc lập, |B1 − x| < |B2 |. Theo điều

Tiếp theo ta chứng minh B1 − (I1 ∪ B2 ) là rỗng. Giả sử B1 − (I1 ∪ B2 )
là không rỗng, thì có x ∈ B1 − (I1 ∪ B2 ) và y ∈ B2 − B1 sao cho
(B1 − x) ∪ y ∈ B.
Bây giờ thì (I1 ∪ y) ⊆ ((B1 − x) ∪ y) nên I1 ∪ y ∈ I .
Từ y ∈ (B2 − B1 ), theo (2), y ∈ (I2 − I1 ), mâu thuẫn với điều giả sử.
Suy ra B1 − (I1 ∪ B2 ) là rỗng. Vì thế B1 − B2 = I1 − B2 .
B1 − B2 ⊆ I1 − I2

(3)

Mà |B1 | = |B2 | nên |B1 − B2 | = |B2 − B1 |, kết hợp với (1), (2), (3) ta
có
|I1 − I2 | ≥ |I2 − I1 | ⇔ |I1 | ≥ |I2 |, mâu thuẫn với giả thuyết |I1 | < |I2 |
Vậy (S, I ) là matroid.
Định lý 1.1.2. Các sơ sở của một matroid có cùng số phần tử.

6


Chứng minh. Giả sử hai cơ sở của matroid là B1 và B2 có số lượng
phần tử khác nhau . Giả sử |B1 | < |B2 | và có một phần tử {e1 } ∈ M sao
cho e1 ∈ B1 nhưng e1 ∈
/ B2 . Nếu lấy e1 ∈ B1 , theo B(2i), ta có e2 ∈ B2 ,
e2 ∈
/ B1 sao cho B3 = B1 − (e1 ) ∪ (e2 ). Khi đó B3 là một cơ sở trong M.
Vì thế |B1 | = |B3 | nhưng B2 = B1 = B3 . Nếu ta tiếp tục thay các phần
tử k lần khi đó sẽ không có phần tử ở B1 mà không có trong Bk .
Vậy nên ∀ e ∈ Bk thì e ∈ B2
Suy ra Bk ⊆ B2 (mâu thuẫn với B(i)).
Ví dụ 1.1.4. Cho ma trận A là ma trận 5 x 8 có các cột là các vecter

1

Tập các cột của ma trận là một matroid. Cơ sở của matroid là một
tập độc lập tuyến tính tối đại trong không gian vecter cột. Xét hai cơ sở
của matroid.
       

1
1
0
0 




















 0
0
0
1 

7


       

0 
0
0
1















1 1 0 0

1




























1 1 1 0

1.1.3

Tiên đề vòng

Cho matroid M = (S, F ). Gọi mỗi tập phụ thuộc tối tiểu của M là một
vòng, kí hiệu C(M ) là họ các vòng.
Nhận xét: Nếu bớt đi một phần tử của C thì ta được tập độc lập.
Định lý 1.1.3. Cho tập hữu hạn S và C là họ các tập con của S. Khi
đó C là tập vòng của matroid M trên S khi và chỉ khi thỏa mãn các điều
kiện sau:
C(1i) ∅ ∈
/ C.
C(2i) Nếu C1 , C2 ∈ C và C1 ⊆ C2 thì C1 = C2 .
C(3i) Nếu C1 , C2 ∈ C và e ∈ C1 ∩ C2 thì tồn tại C3 ∈ C, C3 ⊆
(C1 ∪ C2 ) − e.
Chứng minh. Ta chứng minh tập C được xây dựng như trên sẽ thỏa
mãn ba điều kiện của định lý 1.1.3.
8


Theo M(1i) ta có ∅ ∈ F nên hiển nhiên ∅ ∈
/ C, C(1i) được thỏa mãn.
Theo M(2i), nếu X ∈ F , Y ⊆ X thì Y ∈ F . Khi ta thêm cùng một
phần tử vào mỗi tập X, Y thì được X , Y là các tập phụ thuộc tối tiểu
và Y ⊆ X . Nếu Y ⊂ X thì vô lý vì một tập phụ thuộc tối tiểu không
thể là con thực sự của một tập phụ thuộc tối tiểu khác, suy ra Y = X ,
C(2i) được thỏa mãn.
Cho C1 , C2 ∈ C, C1 ∩ C2 = e. Giả sử không có C3 ∈ C sao cho C3 ⊆
(C1 ∪ C2 ) − e. Ta có C1 − e, C2 − e, C3 ⊆ (C1 ∪ C2 ) − e đều là các tập độc
lập và |(C1 ∪ C2 ) − e| > |C1 − e|, |(C1 ∪ C2 ) − e| > |C2 − e|. Theo M(3i),


Hình 1.3: Vòng C1

Hình 1.4: Vòng C2

10


Hình 1.5: Vòng C3

Có thể thấy ở đây ba vòng trong C3 là {a, e, f }, {a, b, c, d, e}, {b, c, d, f },
trong đó,{b, c, d, f } là một vòng trong C3 mà không chứa cả {a} và {e}.
Như vậy, tính chất C(3i) được thỏa mãn.
1.1.4

Tiên đề hạng

Cho đồ thị G = (V, E), M(G) là matroid vòng của đồ thị G xác định
trên tập cạnh E và tập độc lập gồm các tập con của E không chứa chu
trình của G.
Cho M = (S, F ) và họ tất cả các tập con của S là 2S .
Gọi hàm số r(A) = max{|X||X ⊆ A và X ∈ (F )} là hạng của A.
Hạng của matroid M kí hiệu là r(M ), hay r(S).
Nhận xét: Hạng của tập A là số phần tử của tập độc lập lớn nhất
thuộc A. Nếu A độc lập thì r(A) = |A|.
Định lý 1.1.4. Cho S là tập hữu hạn khác rỗng và hàm số r : 2S −→ N.
Khi đó r là hàm hạng của matroid trên S khi và chỉ khi thỏa mãn các
điều kiện sau ∀X, Y của S:
R(1i) 0 ≤ r(X) ≤ |X|.
R(2i) Nếu Y ⊆ X thì r(Y ) ≤ r(X).

⇔ r(X) ≥ r(X ∪ {y1 , y2 , ..., yk + 1})
Theo R(2i) suy ra (X ∪ {y1 , y2 , ..., yk + 1}) ⊆ X, vô lý, suy ra
r(X) = r(X ∪ {y1 , y2 , ..., yk + 1}) (bài toán được chứng minh).
Ta trở lại phần chứng minh (S, I ) là matroid. Theo R(1i), 0 ≥ r(∅) ≥
|∅| nên r|∅| = |∅| suy ra ∅ ∈ I . M(1i) được thỏa mãn.
12


Cho I ∈ I , I ⊆ I. Khi đó r(I) = |I|. Theo R(3i)
r(I ∪ (I − I )) + r(I ∩ (I − I )) ≥ r(I ) + r(I − I ) ≥ r(I ) + r(I − I )
⇔ r(I) + r(∅) ≥ r(I ) + r(I − I )

(1)

Nhưng r(I) = |I| và r(∅) = 0. Ngoài ra, theo R(2i), r(I ) ≥ |I | và
r(I − I ) ≥ |I − I | và (1) suy ra
|I| ≥ r(I ) + r(I − I ) ≥ |I | + |I − I | = |I|
⇒ r(I ) = |I | ⇔ I ∈ I . M(2i) được thỏa mãn. Để chứng minh I
thỏa mãn M(3i), giả sử ngược lại.
Cho I1 , I2 ∈ I với |I1 | < |I2 | và ∀e ∈ (I2 − I1 ), I1 ∪ e ∈ I . Khi đó,
∀e, r(I1 ∪ e) = |I1 ∪ e|. Do đó, theo R(1i), R(2i) và I ∈ I , ta nhận được
∀e:
|I1 | + 1 > r(I1 ∪ e) ≥ r(I1 ) = I1
⇔ (I1 ∪ e) = |I1 |
Áp dụng bài toán phụ đã chứng minh ở trên với X = I1 và Y = I2 ,
ta có r(I1 ) = r(I1 ∪ I2 ). Nhưng |I1 | = r(I1 ) và r(I1 ∪ I2 ) ≤ r(I2 ) = |I2 |,
nên |I1 | ≤ |I2 |, mâu thuẫn với |I1 | < |I2 |.
Suy ra I thỏa mãn M(3i). Vậy (S, I ) là một matroid.
Ví dụ 1.1.6.
Xét ma trận A và matroid như ở ví dụ 1.1.4. Ta có một trong những



1
0
1
0

       

    
B1 = 0,1,0,0

       


0 0 1 1





































1 0 1 0 1
     
C = 0,1,0,0,1
         



0 0 1 1 0

0 












1 0 1



     

   
D = 0,1,0
     


0 0 1






và S(M ) − ((B1 − y) ∪ y) ∈ B ∗ (M ). Nhưng S(M ) − ((B1 − y) ∪ x) =
((S(M )−B1 −x)∪y = (B1∗ −x)∪y). Suy ra B ∗ (M ) thỏa mãn B(2i). Vậy
B ∗ (M ) là cơ sở của matroid trên S hay M ∗ = {S, B ∗ } là một matroid.
Matroid trong định lý trên nền S(M) và họ cơ sở B ∗ (M ) được gọi là
đối ngẫu của M. Như vậy B(M ∗ ) = B ∗ (M ).
Sự liên hệ giữa M và M* được nói đến trong định lý sau đây.
Định lý 1.1.6. Trên mỗi tập nền S ta luôn có (M ∗ )∗ = M .

1.2

Một số khái niệm và kết quả của lý thuyết đồ
thị

1.2.1

Khái niệm đồ thị

Mô hình đồ thị xuất hiện nhiều trong khoa học và cả đời sống hàng ngày.
Đồ thị tỏ ra hiệu quả trong việc giải các bài toán trong nhiều lĩnh vực
khác nhau. Ta có thể hình dung đồ thị như tập hữu hạn các đối tượng
và những mối liên hệ giữa các đối tượng đó.
Có nhiều loại đồ thị được xây dựng dựa vào cấu trúc của đồ thị, cụ
thể là tùy thuộc vào sự xác định mối liên hệ giữa các đối tượng. Trong
khuôn khổ luận văn, tôi chỉ đề cập tới ba loại đồ thị: đồ thị có hướng,
đơn đồ thị vô hướng, đa đồ thị vô hướng và đồ thị có trọng số. Các khái
niệm cơ bản về đồ thị được dùng theo cuốn " Lý thuyết tổ hợp và đồ
thị", tác giả Ngô Đắc Tân, NXB ĐHQG Hà Nội.
Định nghĩa 1.2.1. Đơn đồ thị có hướng G là một cặp có thứ tự
G = (V, E), ở đây V là một tập còn E là một tập con của tích Đề các
15


Hình 1.7: Đơn đồ thị G vô hướng

Định nghĩa 1.2.3. Đa đồ thị vô hướng G là một cặp có thứ tự
G = (V, E), ở đây V là một tập còn E là một đa tập lực lượng 2 trên V .
Đa đồ thị vô hướng cũng được biểu diễn trên mặt phẳng tương tự
như đồ thị vô hướng, trong đó các cạnh khác nhau mà có cùng đỉnh đầu
và đỉnh cuối được biểu diễn bằng các đường cong khác nhau.
Định nghĩa 1.2.4. Đồ thị G = (V, E) được gọi là đồ thị có trọng số
nếu ít nhất một trong hai hàm f : V → WV và g : E → WE , được xác
định, ở đây WV và WE là các tập số. Giá trị f (v) được gọi là trọng số
của đỉnh v, còn giá trị g (e) được gọi là trọng số của cạnh e.
Người ta thường kí hiệu đồ thị có trọng số bằng G = (V, E, f ) hay
G = (V, E, g) hay G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f ,
chỉ một hàm g hay cả hai hàm f và g được xác định.
Trong khuôn khổ luận văn này, chúng ta chỉ sử dụng G = (V, E, g).
Biểu diễn một đồ thị G = (V, E, g) có trọng số trên mặt phẳng trực
quan ta biểu diễn đồ thị vô hướng hoặc có hướng và gắn trọng số tương
ứng lên trực tiếp bên cạnh cung mang giá trị đó.
Ví dụ 1.2.3. Cho đồ thị vô hướng có trọng số G = (V, E) với V =
{a, b, c, d, e, f } và E = {ab, bc, cd, db, ce, ef, f d}
17


g (ab) = g (bc) = g (cd) = 2
g (bd) = 3
g (de) = g (ef ) = 4
g (df ) = 5.

Hình 1.8: Đồ thị có trọng số G