ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
———–

NGUYỄN THỊ MINH THƯƠNG

LÝ THUYẾT ĐỒ THỊ
VỚI CÁC BÀI TOÁN PHỔ THÔNG

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

HÀ NỘI - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
———–

NGUYỄN THỊ MINH THƯƠNG

LÝ THUYẾT ĐỒ THỊ
VỚI CÁC BÀI TOÁN PHỔ THÔNG

Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60.46.01.13

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

Người hướng dẫn khoa học:
GS.TS Đặng Huy Ruận


1.4.1 Xích, chu trình . . . . . . . . . . . . . .
1.4.2 Đường, vòng . . . . . . . . . . . . . . . .
1.4.3 Một số tính chất . . . . . . . . . . . . .
Đồ thị liên thông . . . . . . . . . . . . . . . . .
1.5.1 Định nghĩa . . . . . . . . . . . . . . . .
1.5.2 Tính chất . . . . . . . . . . . . . . . . .
Số ổn định trong, số ổn định ngoài . . . . . . .
1.6.1 Số ổn định trong . . . . . . . . . . . . .
1.6.2 Số ổn định ngoài . . . . . . . . . . . . .
1.6.3 Các thuật toán tìm số ổn định trong, số
ngoài. . . . . . . . . . . . . . . . . . . .
Nhân của đồ thị và ứng dụng vào trò chơi . . .
1.7.1 Định nghĩa . . . . . . . . . . . . . . . .
1.7.2 Tính chất . . . . . . . . . . . . . . . . .
1.7.3 Trò chơi Nim . . . . . . . . . . . . . . .
1.7.4 Trò chơi bốc các vật . . . . . . . . . . .
Cây và bụi . . . . . . . . . . . . . . . . . . . . .
1.8.1 Định nghĩa . . . . . . . . . . . . . . . .
1.8.2 Đặc điểm của cây và bụi . . . . . . . . .
1

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

16
17
18
18
19
20
21
21
22
23
24
29
29
30


2 Một số bài toán đồ thị cơ bản
2.1 Bài toán về đường đi . . . . . . . . . . . . . . . .
2.1.1 Đường đi Euler - Chu trình Euler. . . . . .
2.1.2 Đường đi Hamilton - Chu trình Hamilton.
2.2 Bài toán tô màu đồ thị . . . . . . . . . . . . . . .
2.2.1 Định nghĩa . . . . . . . . . . . . . . . . .
2.2.2 Một số tính chất . . . . . . . . . . . . . .
2.2.3 Thuật toán tô màu đỉnh. . . . . . . . . . .

.
.
.
.
.

40
43
43
43
53

3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông.
3.1 Quy trình giải bài toán bằng phương pháp đồ thị. . . . .
3.1.1 Xây dựng đồ thị G mô tả các quan hệ. . . . . . .
3.1.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý
luận trực tiếp suy ra đáp án của bài toán D. . . .
3.2 Bài toán về đỉnh - cạnh của đồ thị. . . . . . . . . . . . .
3.3 Bài toán về xích, chu trình, đường, vòng và tính liên thông
của đồ thị. . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Bài toán về tô màu đồ thị. . . . . . . . . . . . . . . . .
3.5 Bài toán liên quan đến số ổn định trong, số ổn định ngoài.
3.6 Bài toán liên quan đến đường đi. . . . . . . . . . . . . .
3.6.1 Bài toán tìm đường đi trong mê cung . . . . . . .
3.6.2 Bài toán liên quan đến đường và chu trình Euler .
3.6.3 Bài toán liên quan đến đường và chu trình Hamilton
3.7 Bài toán liên quan đến cây. . . . . . . . . . . . . . . . .

54
54
54

Kết luận

89


độc đáo và khó của chủ đề kiến thức này.
Luận văn "Lý thuyết đồ thị với các bài toán phổ thông" đưa đến sự
sáng tạo trong cách nhìn nhận bài toán và lập luận cách giải dưới con
mắt của lý thuyết đồ thị.
Ngoài phần mở đầu và kết luận luận văn gồm 3 chương:
Chương 1 Đại cương về đồ thị.
Chương 2 Một số bài toán đồ thị cơ bản.
Chương 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông.
Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của
GS.TS Đặng Huy Ruận, tác giả xin bày tỏ sự kính trọng và lòng biết ơn
sâu sắc tới thầy.
Tác giả cũng xin gửi lời cảm ơn chân thành đến Ban giám hiệu cùng các
thầy cô giáo khoa Toán - Cơ - Tin, Trường Đại học Khoa Học Tự Nhiên
- Đại Học Quốc Gia Hà Nội đã tạo điều kiện, dạy bảo và dìu dắt tác giả
trong những năm học vừa qua.
Xin chân thành cảm ơn sự giúp đỡ của bạn bè, người thân trong thời
gian học tập và làm luận văn.
Do khả năng nhận thức của bản thân tác giả, luận văn còn nhiều hạn
chế, thiếu sót. Tác giả kính mong các ý kiến chỉ bảo của quý thầy cô
cùng sự đóng góp của các bạn đọc.
Tác giả xin chân thành cảm ơn!
Hà Nội, tháng 6 năm 2015

3


Chương 1
Đại cương về đồ thị
1.1


nối với x bằng ít nhất một cạnh; D+ (x) để chỉ tập đỉnh mà mỗi đỉnh
này từ x có cung đi tới; D− (x) để chỉ tập đỉnh mà mỗi đỉnh này có cung
đi tới x.
Hai cạnh (cung) a,b được gọi là kề nhau, nếu:
i) Chúng khác nhau.
ii) Chúng có đỉnh chung (nếu a, b là cung, thì không phụ thuộc vào
đỉnh chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh
cuối của cung b).
Ví dụ 1.1. Cho đồ thị hỗn hợp có khuyên G(X, E) với tập đỉnh
X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 },
tập cạnh và cung
E = {x1 , x2 ; x2 , x3 ; x4 , x6 ; x5 , x6 ; x3 , x3 ; x1 , x6 ; x5 , x5 }
= {a1

a2

a3

a4

a5

b1

b2 },

trong đó a1 , a2 , a3 , a4 , a5 là các cạnh; b1 , b2 là các cung.

Hình 1.2




chiều tùy ý).
Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) hai mảng
nếu tập đỉnh X của nó được phân thành hai tập con rời nhau X1 , X2
(X1 X2 = X và X1 X2 = ∅) và mỗi cạnh đều có một đầu thuộc
X1 còn đầu kia thuộc X2 .Khi đó G = (X, E) còn được ký hiệu bằng
G = (X1 , X2 , E).

Hình 1.5: Đồ thị hai mảng

Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) phẳng,
nếu nó có ít nhất một dạng biểu diễn hình học trải trên một mặt phẳng
nào đó, mà các cạnh của đồ thị chỉ cắt nhau ở đỉnh.
Đồ thị (đa đồ thị) G = (X, E) được gọi là hữu hạn, nếu số đỉnh của
nó hữu hạn, tức tập X có lực lượng hữu hạn.
Đồ thị (đa đồ thị) G = (X, E) được gọi là vô hạn, nếu số đỉnh của
nó là vô hạn.
Đồ thị (đa đồ thị) với số cạnh thuộc mỗi đỉnh đều hữu hạn được gọi
là đồ thị (đa đồ thị) hữu hạn địa phương.
Một đồ thị hay đa đồ thị hữu hạn thì nó cũng hữu hạn địa phương.
Cho Y ⊆ X, Y = ∅; H ⊆ E, F = E ∩ (Y × Y ) và V = (X × X)/E.
Đồ thị G1 (Y, F ) được gọi là đồ thị con, còn G2 (X, H) là đồ thị bộ
phận của đồ thị G(X, E).
Đồ thị G (X, V ) được gọi là đồ thị bù của đồ thị G(X, E).
Đồ thị có hướng G(X, E) được gọi là đồ thị đối xứng nếu
∀x, y ∈ X, (x, y) ∈ E ⇒ (y, x) ∈ E
Trong đồ thị đối xứng tùy ý, hai đỉnh kề nhau luôn luôn được nối
bằng hai cung ngược chiều nhau. Để đơn giản, trong trường hợp này
người ta quy ước thay hai cung nói trên bằng một cạnh nối giữa x và y.

vào đỉnh x được gọi là nửa bậc vào của đỉnh x và ký hiệu bằng m (x)
hoặc m− (x). Số cung đi ra khỏi đỉnh x được gọi là nửa bậc ra của đỉnh
x và ký hiệu bằng m (x) hoặc m+ (x).
Ký hiệu tập cung đi vào đỉnh x bằng E − (x), còn tập cung ra khỏi
đỉnh x bằng E + (x).
8


Hình 1.7

Ví dụ 1.3. Trong hình 1.7 ta có:
m (1) = 1, m (2) = 2, m (3) = 2, m (4) = 0, m (5) = 1, m (6) = 1;
m (1) = 1, m (2) = 1, m (3) = 1, m (4) = 1, m (5) = 1, m (6) = 2;
E − (4) = {∅}, E + (4) = {g};
E − (6) = {f }, E + (6) = {e, d}.

1.3.3

Một số tính chất

Định lí 1.3.1. Trong đồ thị hay đa đồ thị tùy ý, tổng số bậc của tất cả
các đỉnh bao giờ cũng gấp đôi số cạnh.
Chứng minh.
Thật vậy, khi tính bậc của các đỉnh mỗi cạnh vô hướng hặc có hướng
đều được tính mỗi đầu đúng một lần, do đó tổng số bậc của tất cả các
đỉnh bao giờ cũng gấp đôi số cạnh.
Định lí 1.3.2. Trong đồ thị hay đa đồ thị tùy ý, số đỉnh bậc lẻ luôn luôn
là số chẵn.
Chứng minh.
Giả sử đồ thị (đa đồ thị) G = (X, E) có n đỉnh, m cạnh

cùng bậc.
Khẳng định được chứng minh.
Định lí 1.3.4. Nếu đồ thị với n đỉnh (n ≥ 2) có đúng hai đỉnh cùng bậc,
thì hai đỉnh này không thể đồng thời có bậc 0 hoặc bậc n − 1.
Chứng minh.
Giả sử x,y là hai đỉnh cùng bậc của đồ thị G = (X, E) và đều có bậc
0 hoặc bậc n − 1. Loại x, y và tất cả các cạnh thuộc chúng khỏi đồ thị
G, ta được đồ thị con G1 có n − 2 đỉnh. Theo định lý 1.3 trong G1 có
hai đỉnh cùng bậc, chẳng hạn u,v.
1) Nếu x, y cùng bậc 0, thì u,v trong G không kề với x,y nên u,v trong
G đồng thời là hai đỉnh cùng bậc. Như vậy, đồ thị G phải có ít nhất hai
cặp đỉnh cùng bậc.

10


2) Nếu x, y đều bậc n − 1. Khi đó, mỗi đỉnh u, v đều kề đồng thời với
x, y nên trong đồ thị G các đỉnh u, v cũng cùng bậc. Như vậy, đồ thị G
phải có ít nhất hai cặp đỉnh cùng bậc.
Cả hai trường hợp có thể đều dẫn tới mâu thuẫn với tính chất: Đồ
thị G có duy nhất một cặp đỉnh cùng bậc, nên x, y không thể cùng bậc
0 hặc cùng bậc n − 1 .
Khẳng định được chứng minh.
Định lí 1.3.5. Số đỉnh bậc n − 1 trong đồ thị G với n đỉnh (n ≥ 4), mà
bốn đỉnh tùy ý có ít nhất một đỉnh kề với ba đỉnh còn lại, không nhỏ hơn
n − 3.
Chứng minh.
1) Nếu G là đồ thị đầy đủ, thì khẳng định là hiển nhiên.
2) Nếu G có cặp đỉnh duy nhất không kề nhau. Khi đó, trong G có
n − 2 đỉnh bậc n − 1

Gn+1 ba đỉnh bất kỳ đều không cùng bậc.
b. Nếu Gn không có đỉnh bậc n − 1. Khi đó, tất cả các đỉnh của Gn
đều có bậc không vượt quá n − 2. Thêm vào Gn đỉnh x (không thuộc Gn )
và nối x với từng đỉnh thuộc Gn bằng một cạnh được đồ thị Gn+1 gồm
n + 1 đỉnh. Đỉnh x có bậc n, còn bậc của mỗi đỉnh thuộc Gn trong Gn+1
được tăng lên một đơn vị, nhưng đều không vượt quá n − 1 và trong bậc
mới ba đỉnh bất kỳ của Gn vẫn không cùng bậc.
Khẳng định được chứng minh.
Định lí 1.3.7. Trong đồ thị G = (X, E) với ít nhất kn + 1 đỉnh, mỗi
đỉnh có bậc không nhỏ hơn (k − 1)n + 1 luôn tồn tại đồ thị con đầy đủ
gồm k + 1 đỉnh.
Chứng minh.
Ta sẽ chứng minh định lý bằng phương pháp quy nạp theo k.
1) Với k = 1 khẳng định hiển nhiên đúng.
2) Với k = 2 có thể làm chặt chẽ hơn giả thiết. Nếu đồ thị 2n + 1
đỉnh mà mỗi đỉnh có bậc không nhỏ hơn n, thì nó có đồ thị con 3 đỉnh
đầy đủ.
Thật vậy, xét đỉnh x tùy ý, còn y là một trong các đỉnh kề với x. Tổng
số đỉnh kề với x và y không nhỏ hơn 2n, nhưng số đỉnh khác x và y chỉ
là 2n − 1. Bởi vậy, phải có ít nhất một đỉnh z được tính hai lần. Khi đó,
x, y, z tạo thành một đồ thị con đầy đủ ba đỉnh.
3) Giả sử khẳng định trên đúng với k. Cần suy ra tính đúng đắn của
khẳng định đối với k + 1.
Theo giả thiết, thông đồ thị G gồm (k + 1)n + 1 đỉnh, số đỉnh kề
với đỉnh x tùy ý không nhỏ hơn kn + 1, nên số đỉnh không kề với x
sẽ không vượt quá n. Bởi vậy, mỗi đỉnh y kề với x thì nó kề với nhiều
nhất n đỉnh không kề với đỉnh x. Do đó, đỉnh y phải kề với ít nhất
kn + 1 − n = (k − 1)n + 1 đỉnh kề với đỉnh x. Xét đồ thị con G1 gồm các
đỉnh kề với x. Đồ thị con G1 có ít nhất kn + 1 đỉnh và mỗi đỉnh của nó
kề với ít nhất (k − 1)n + 1 đỉnh thuộc G1 , nên theo giả thiết quy nạp,

13


α1
α2
α3
α5

= [5, 1, 4, 2, 1] là một dây chuyền không sơ cấp.
= [1, 2, 3, 4] là một dây chuyền sơ cấp.
= [1, 5, 1] và α4 = [1, 2, 3, 4, 1] là các chu trình đơn và sơ cấp.
= [1, 2, 4, 3, 2, 1] là chu trình đơn nhưng không sơ cấp.

1.4.2

Đường, vòng

Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng. Dãy đỉnh β
của G(X, E) :
β = [x1 , x2 , ..., xi , xi+1 , ..., xm−1 , xm ]
được gọi là một đường hay một đường đi nếu ∀i(1 ≤ i ≤ m − 1), đỉnh
xi là đỉnh đầu, còn đỉnh xi+1 là đỉnh cuối của một cung nào đó.
Tổng số vị trí của tất cả các cung xuất hiện trong β được gọi là đồ
dài của đường β, ký hiệu: |β|.
Đỉnh x1 được gọi là đỉnh đầu còn xm là đỉnh cuối của đường β. Người
ta còn nói rằng, đường β xuất phát từ đỉnh x1 và đi tới xm . Đường β
còn được ký hiệu bằng β[x1 , xm ].
Một đường có đỉnh đầu và đỉnh cuối trùng nhau được gọi là một vòng.
Đường (vòng) β được gọi là đường (vòng) đơn (sơ cấp hay cơ bản),
nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần.

tới mâu thuẫn với tính chất độ dài cực đại của α. Bởi vậy, y ∈ α tức
y ≡ xi , (3 ≤ i ≤ k), nên trong đồ thị G = (X, E) có chu trình sơ cấp
β = [x1 , x2 , ..., xi , x1 ]
Khẳng định được chứng minh.
Định lí 1.4.2. Trong một đồ thị vô hướng với n đỉnh (n ≥ 4) và các
đỉnh đều có bậc không nhỏ hơn 3 luôn tồn tại chu trình sơ cấp độ dài
chẵn.
15


Chứng minh.
Giả sử α là một trong những xích sơ cấp có độ dài cực đại
α = [x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj−1 , xj , xj+1 , ..., xk−1 , xk ]
Vì α có độ dài cực đại, mà bậc của x1 không nhỏ hơn 3, nên x1 phải
kề với hai đỉnh khác thuộc α: xi , (3 ≤ i ≤ k), xj , (3 ≤ j ≤ k). Khi đó có
hai chu trình sơ cấp:
α1 = [x1 , x2 , ..., xi−1 , xi , x1 ]
α2 = [x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj−1 , xj , x1 ]
1) Nếu một trong hai chu trình α1 , α2 có độ dài chẵn thì khẳng định
được chứng minh.
2) Nếu ngược lại, cả hai chu trình α1 , α2 đề có độ dài lẻ.
Khi đó xích: α3 = [x1 , x2 , ..., xi−1 , xi ] có độ dài chẵn,
còn xích α4 = [xi , xi+1 , ..., xj−1 , xj , x1 ] có độ dài lẻ,
nên chu trình α5 = [x1 , xi , xi+1 , ..., xj−1 , xj , x1 ] có độ dài chẵn.
Khẳng định được chứng minh.

1.5
1.5.1

Đồ thị liên thông


Định lí 1.5.1. Đồ thị vô hướng tùy ý với n đỉnh (n ≥ 2), mà tổng bậc
của hai đỉnh tùy ý không nhỏ hơn n là đồ thị liên thông.
Chứng minh.
Giả sử đồ thị vô hướng G(X, E) có n đỉnh (n ≥ 2). Với mọi cặp đỉnh
a, b của đồ thị ta đều có:
m(a) + m(b) ≥ n

(1)

Nhưng a, b không liên thông. Khi đó trong đồ thị G tồn tại hai thành
phần liên thông:
G1 chứa a và có n1 đỉnh, còn G2 chứa b và có n2 đỉnh.

17


Vì G1 , G2 là các thành phần liên thông của G nên n1 + n2 ≤ n Khi
đó
m(a) + m(b) ≤ (n1 − 1) + (n2 − 1) = n1 + n2 − 2 ≤ n − 2 < n

(2)

Như vậy, (1) và (2) mâu thuẫn nhau, nên đồ thị G phải liên thông.
Khẳng định được chứng minh.
Từ định lý trên suy ra hệ quả sau:
Hệ quả 1.5.1. Đồ thị, mà bậc của mỗi đỉnh không nhỏ hơn nửa số đỉnh,
là đồ thị liên thông.
Định lí 1.5.2. Nếu đồ thị có đúng hai đỉnh bậc lẻ, thì hai đỉnh này phải
liên thông.

3. Số ổn định trong
Số phần tử của một trong những tập ổn định trong có lực lượng lớn
nhất được gọi là số ổn định trong của đồ thị G, đồng thời được ký hiệu
bằng α(G).
1.6.2

Số ổn định ngoài

1. Tập ổn định ngoài
Giả sử có đồ thị G(X, E). Tập con B ⊆ X các đỉnh của đồ thị G
được gọi là tập ổn định ngoài, nếu với mọi đỉnh x thuộc tập X\B đều
tồn tại đỉnh y ∈ B, để hoặc từ x sang y có cung hoặc cặp đỉnh x, y được
nối bằng một cạnh.
2. Tính chất
Nếu B là tập ổn định ngoài, thì mọi tập chứa B đều ổn định ngoài.
3. Số ổn định ngoài
Số phần tử của một trong những tập ổn định ngoài có lực lượng bé
nhất được gọi là số ổn định ngoài của đồ thị G, đồng thời được ký hiệu
bằng β(G).
Ví dụ 1.7. Cho đồ thị G như hình 1.12. Hãy tìm tất cả các tập ổn định
trong,số ổn định trong và số ổn định ngoài của đồ thị G.
Các tập ổn định trong

Hình 1.12

19


- Vì đồ thị không có khuyên, nên mỗi đỉnh lập thành một tập ổn định
trong:

.........
- Bước k: Giả sử ta đã tìm được m tập con ổn định trong có k+1
phần tử
+ Duyệt từng tập và bổ sung vào các tập đó thêm 1 phần tử.
+ Nếu không có tập nào bổ sung được nữa thì dừng.

20


1.6.3.2. Thuật toán tìm số ổn định ngoài.

Xét G(X, E) với X = {x1 , x2 , ..., xn }
- Bước 1: Xác định các tập ∆(xi ), i = 1, 2, ..., n
với ∆(xi ) = {xi và các đỉnh kề với xi }
- Bước 2: Từ các tập ∆(x1 ), ∆(x2 ), ..., ∆(xn ) ta tìm tập B = {xk1 , xk2 , ..., xkm }
sao cho ∆(xk1 ) ∪ ∆(xk2 ) ∪ ... ∪ ∆(xkm ) = X.
Khi đó B là tập ổn định ngoài cực tiểu.

1.7
1.7.1

Nhân của đồ thị và ứng dụng vào trò chơi
Định nghĩa

Giả sử có đồ thị G(X, U ). Tập đỉnh S ⊆ X được gọi là nhân của đồ
thị G, nếu nó vừa là tập ổn định trong lại vừa là tập ổn định ngoài.
Do S là tập ổn định trong nên nó không chứa khuyên. Mặt khác S ổn
định ngoài nên nó phải chứa tất cả các đỉnh biệt lập và các đỉnh không
có cung đi ra.
Ví dụ 1.8. Cho hai đồ thị như hình 1.13.

Định lý được chứng minh.
Định lí 1.7.2. Nếu S là nhân của đồ thị G(X, U ), thì nó cũng là tập ổn
định trong cực đại.
Chứng minh.
Giả sử S là nhân của đồ thị G(X, U ) và x là đỉnh tùy ý không thuộc
S. Xét tập S ∪ {x}. Vì S là nhân và x ∈
/ S, nên ∃y ∈ S, để x, y được nối
bằng một cạnh hoặc từ x sang y có cung. Bởi vậy, tập S ∪ {x} không ổn
định trong, nên S là tập ổn định trong cực đại.
Định lý được chứng minh.
Định lí 1.7.3. Trong đồ thị vô hướng không có khuyên mọi tập ổn định
trong cực đại đều là nhân.
Chứng minh.
Giả sử B là một tập ổn định trong cực đại của đồ thị vô hướng
G(X, E). Khi đó ∀x ∈ (X\B) đều ∃y ∈ B để x, y có cạnh nối với nhau,
nên B đồng thời là tập ổn định ngoài.
Định lý được chứng minh.
Giả sử có đồ thị G(X, E) và A ⊆ X. Dùng D(A) để ký hiệu tập đỉnh,
mà mỗi đỉnh này có cạnh nối với ít nhất một đỉnh thuộc A. Còn D+ (A)
là tập đỉnh mà mỗi đỉnh này có ít nhất một đỉnh thuộc A có cung đi tới
nó. D− (A) là tập đỉnh mà mỗi đỉnh này có cung đi tới ít nhất một đỉnh
thuộc A.
22


Hệ quả 1.7.1. Mọi đồ thị vô hướng không có khuyên đều có nhân.
Chứng minh.
Thật vậy, giả sử đồ thị vô hướng G(X, E) là đồ thị vô hướng không
có khuyên. Khi đó mỗi đỉnh đều lập thành một tập ổn định trong.
Xuất phát từ đỉnh tùy ý x0 . Đặt S0 = {x0 }, sau đó chọn đỉnh tùy ý

D(x1 ) ∪ D+ (x1 ) = ∅ tức là A thắng cuộc, hoặc D(x1 ) ∪ D+ (x1 ) = ∅, thì
đối phương B buộc phải chọn đỉnh x2 ∈ (X − S). Khi đó đến lượt mình
đấu thủ A lại có thể chọn x3 ∈ S và cứ như thế mãi.

23