Luận văn tốt nghiệp
24
Chương 2

SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐỒ THỊ
I. SỐ ỔN ĐỊNH TRONG, SỐ ỔN ĐỊNH NGOÀI, NHÂN ĐỒ THỊ
1. Số ổn định trong
Cho đồ thị vô hướng G = <X, U> và A

X.
a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là
không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y.
b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu:
- A là tập ổn định trong
- Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong.
Gọi L là tập hợp các tập ổn đỉnh trong c
ủa của G = <X,U>. Khi đó ký hiệu

(G) = Max {

A

/ A

L} và

phần tử ít nhất vì lực lượng của nó liên quan tới số ổn định ngoài của đồ thị.
3. Nhân đồ thị
Cho đồ thị vô hướng G = <X, U>. Nếu tập A

X vừa là tập ổn định trong vừa
là tập ổn định ngoài của đồ thị G thị A được gọi là nhân của đồ thị.
Đối với nhân của đồ thị, ta quan tâm tới nhân có số phần tử ít nhất.

Luận văn tốt nghiệp
25
Hình 1.1

Ví dụ: xét đồ thị hình 1.1 ta có:
Các tập ổn định trong của đồ thị là:
A
1
= {1, 5, 7} A
6
= {2, 6, 7}
A
2

= A
1
; B
2
= A
2
; B
3
= A
3
; B
4

= A
4
. Vì các tập này nếu bớt đi 1 trong các phần tử của chúng thì tập còn lại
không là tập ổn định ngoài nữa. Số ổn đỉnh ngoài của đồ thị này là

(G) = 3.
Nhân của đồ thị trên là B
1
, B
2
, B
3
, B
4
vì các tập này là tập ổn định trong và đồng
thời cũng là tập ổn định ngoài.
4. Các thuật toán tìm các tập ổn định trong cực đại, ổn định ngoài cực tiểu.

26
- Bước 1: Xác định các tập

x
i
) i = 1..n với

x
i
) = {x
i
và các đỉnh kề với
x
i
}
- Bước 2: Từ các tập

x
1
),

x
2
),...,

x
n

u tư duy thuật toán, cũng như cơ sở về trí tuệ
nhân tạo cho việc lập trình trò chơi giữa người và máy.
Ta xét ứng dụng của đồ thị phục vụ cho bài toán lập trình trò chơi Carô.
Xét một thế cờ Carô như hình 1.2.a

o
1
x
1

x
2
x
4
x
3

o
2 o
3
a) b)

Hình 1.2

Cấu trúc dữ liệu cho thế cờ này có thể dùng bảng ma trận như hình 1.2.b, với 0
là vùng trắng, 1 là quân "o" và 2 là quân "x". Nhưng như vậy việc tính toán sẽ
rất khó khăn, ta có thể dùng đồ thị làm cấu trúc dữ liệu cho thế cờ Carô, khi đó
a) b)
Hình 1.3 a) Cách đánh nhãn b) Đồ thị cho thế cờ hình 1.2.a

Ví dụ đồ thị như hình 1.3.b là thể hiện cho thế cờ hình 1.2.a
Trong luật chơi cờ carô nếu quân "x" đi trước thì ngay sau đó là quân "o" đi sau,
tiếp tục lại "x" rồi lại "o"... Chính điều này ta có thể coi những quân "x" tương
ứng là những đỉnh số lẻ, quân "o" tương ứng những đỉnh số chẵn hoặc ngược
lạ
i.
Trong 1 thế cờ Carô nếu tồn tại 1 dãy 5 quân liên tiếp của "x" hoặc "o" được
sắp thẳng hàng ngang, thẳng hàng dọc hoặc thẳng hàng chéo thì thắng. Với đồ
thị nếu tồn tại một đường đi các cạnh cùng nhãn gồm 5 đỉnh số lẻ, hoặc số chẵn
thì thế cờ thắng cho tương ứng quân "x" hoặc quân "o".
Xét đồ thị hinh 1.3.b đã có 1 đường đi cùng nhãn 4 gồm 3 đỉnh cùng quân x
1
,
x
2
, x
3
. Nếu ta thêm 1 đỉnh x
6
kề với đỉnh o
2
sao cho cạnh (o
2
, x
6

Mà mối quan hệ "thẳng hàng" giữa các quân là quan trọng trong bài toán lập
trình trò chơi carô.
- Mô hình này chỉ thích hợp cho việc lập trình khi mà chỉ chơi giữa người với
người, lúc này bài toán chỉ là tìm đường đi cùng nhãn gồm 5 đỉnh cùng quân,
không phải là bài toán tính nước đi cho các bước tiếp theo.
b) Mô hình bằng đồ thị theo mối quan hệ thẳng hàng.
Cách xây d
ựng này tương tự như cách thứ nhất nhưng có những đặc điểm sau:
4
1
2 3
x
1
x
2
x
3
o
2
o
1
x
4
o
3
4
4
4
2
1

3

x
4
o
2
o
3
x
5

a) b)
Hình 1.4

Ví dụ xét thế cờ như hình 1.4.a và hình 1.4.b thì đồ thị tương ứng của nó như
hình 1.5.a và hình 1.5.b
a) b)
Hình 1.5

Mỗi cạnh của đồ thị, nhãn đặt trước trọng số, trọng số đứng sau cách nhãn bởi
dấu phẩy. Xét thế cờ 1.4.a từ quân x

, x
2
, x
3
,

x
4
, x
5
)
Trong kỹ thuật chơi cờ Ca rô, nước đi có lợi nhất là nước có tạo được nhiều
khả năng dẫn đến thế cờ thắng, ví dụ thế cờ như hình 1.4.b thì ví trí của o
1
là 1
x
1

x
2

x
3

x
4
x
5
o
1