Luận văn tốt nghiệp Phan Thanh Long
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à (G) đợc gọi là số ổn định trong của đồ thị G. Nh vậy
(G) là số phần tử của 1 tập ổn định trong cực đại nào đó.
2. Số ổn định ngoài
Cho đồ thị vô hớng G = <X,U> và B X
a) Tập B đợc gọi là tập ổn định ngoài của đồ thị nếu với mỗi phần tử y X \ B đều
tồn tại x B sao cho có cạnh nối giữa x và y, B còn đợc gọi là tập thống trị của
đồ thị.
b) Tập B đợc gọi là tập ổn định ngoài cực tiểu nếu:
- B là tập ổn định ngoài
- Nếu bớt 1 phần tử bất kỳ của B thị B không còn là tập ổn định ngoài.
Gọi M là tập của tất cả các tập ổn định ngoài của G = <X,U>. Khi đó ký hiệu
(G) = Min { / B M} và (G) đợc gọi là số ổn định ngoài của đồ thị G.
Đối với các tập ổn định ngoài, ta thờng quan tâm đến tập ổn định ngoài có số 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.
24

9
và A
10
là các tập ổn định trong cực đại có 4 phần tử vì nếu thêm 1 đỉnh
mới nữa vào các tập đó thì chúng không còn là tập ổn định trong nữa. Số ổn định
trong của đồ thị trên là (G) = 4.
Với đồ thị trên các tập ổn định ngoài cực tiểu là B
1
= 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

7
Luận văn tốt nghiệp Phan Thanh Long
- 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
) ta tìm tập B
B = {x
k1
, x
k2
,..., x
km
} sao cho (x
k1
) (x
k2
) ... (x
km

toán lập trình trò chơi carô sẽ trở nên thuận lợi hơn nhiều.
a) Mô hình bằng đồ thị theo vị trí liền kề
Ta xây dựng 1 đơn đồ thị theo nguyên tắc sau
- Mỗi 1 quân "x" hoặc quân "o" thì tơng ứng với một đỉnh
- Hai đỉnh là kề nhau nếu tơng ứng với 2 quân ở vị trí liên tiếp nhau
- Mỗi một cạnh đợc gán một nhãn, nhãn cho biết 2 đỉnh kề nhau là kề đứng, kề
chéo hay là kề ngang trong thế cờ. Ta gán tên nhãn nh sau: thẳng ngang nhãn là 1,
thẳng chéo trái là 2, thẳng dọc nhãn là 3, thẳng chéo phải là 4 (xem hình 1.3.a).
26
0 1 0 2
A = 0 0 2 2
0 2 0 0
1 0 0 1
x
1
x
2
x
3
o
2
o
1
x
4
o
3
4
4
4

ta thay đỉnh o
2
bằng đỉnh x
5
thì bây giờ ta có 1 đờng đi cùng nhãn 4 gồm 5 đỉnh
quân "x" (x
1
, x
2
, x
3
, x
5
, x
6
) và ta có 1 thế cờ thắng cho quân x.
Nhận xét:
- Với mô hình này ta sẽ không thể thấy đợc đầy đủ mối quan hệ giữa các đỉnh,
nh đồ thị hình 1.3.b đỉnh o
3
là đỉnh cô lập, trong thế cờ hình 1.2.a o
1
có mối quan
hệ thẳng hàng với x
1
và x
3
nhng trong đồ thị tơng ứng ta không nhìn thấy đợc mối
quan hệ này nên khó tính toán đợc nớc đi cho lần sau. 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ô.

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
1
đến quân x
2
cách nhau 1 ô nếu tính từ x
1
nên
trọng số cạnh (x
1
, x
2
) là 1, quân x
1
cách x
3

là 1 trong
những nớc có lợi nhất, vì nếu ta thay o
1
bằng x
4
thì quân x có thêm 3 khả năng
phát triển nớc dẫn đến thế cờ thắng nh (x
4
, x
2
); (x
4
, x
1
); ( x
4
, x
3
), nếu với đồ thị t-
28
x
1
x
2
x
3
x
4
x
5