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

LÊ THỊ THU HƯỜNG

XÂY DỰNG VÀ PHÂN LOẠI MỘT SỐ
LỚP ĐỒ THỊ CÓ CẤU TRÚC ĐẶC BIỆT

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

Hà Nội – 2014


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

LÊ THỊ THU HƯỜNG

XÂY DỰNG VÀ PHÂN LOẠI MỘT SỐ
LỚP ĐỒ THỊ CÓ CẤU TRÚC ĐẶC BIỆT
Chuyên ngành: Lý thuyết xác suất và thống kê toán học
Mã số:

60460106

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

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. LÊ ANH VINH


1.2. Một số tính chất cơ bản của đồ thị n-e.c . . . . . . . . . . . . . . . . . . . . .

7

1.3. Các đồ thị Paley và biến thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Chương 2. Xây dựng và phân loại một số đồ thị n-e.c . . . .

18

2.1. Đồ thị n-e.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2. Đồ thị 2-e.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.3. Đồ thị 3-e.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.4. Các đồ thị n-e.c với n ≥ 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Chương 3. Xây dựng đồ thị ngẫu nhiên chính quy mạnh .

thị n-e.c, sau đó xây dựng và phân loại các đồ thị n-e.c, cuối cùng nêu
ra một số cách xây dựng cụ thể cho đồ thị n-e.c. Luận văn bao gồm ba
chương.
Chương 1 : Giới thiệu về đồ thị n-e.c, các tính chất của đồ thị n-e.c
và một vài dạng đồ thị n-e.c đã biết.

Chương 2 : Xây dựng các đồ thị n-e.c tổng quát với điều kiện nhất
định sau đó cụ thể hơn cho các lớp đồ thị 2-e.c, 3-e.c và các đồ thị

n-e.c với n ≥ 4.

Chương 3 : Nêu ra hai cách xây dựng đồ thị ngẫu nhiên chính quy
mạnh, sau đó chứng minh các đồ thị sinh ra thỏa mãn tính chất kề

n-e.c.
3


Mặc dù đã rất cố gắng nhưng do thời gian thực hiện luận văn không nhiều
nên trong luận văn không tránh khỏi những hạn chế và sai sót khi trình
bày. Em rất mong nhận được sự góp ý và những ý kiến xây dựng của thầy
cô và các bạn đọc. Em xin chân thành cảm ơn!

4


Chương 1
Đồ thị n-e.c
1.1. Khái niệm về đồ thị n-e.c
Trước khi đi vào khái niệm đồ thị n − e.c, chúng ta sẽ nhắc lại một vài

Hình 1.2).
Định nghĩa tính chất kề n-e.c khá rõ ràng nhưng từ định nghĩa lại không
dễ để chỉ ra đồ thị tồn tại tính chất này. Tuy nhiên, theo chứng minh đầu
tiên trong [16], hầu hết tất cả các đồ thị hữu hạn đều là n-e.c. Với một
số nguyên m, không gian xác suất G(m, 21 ) bao gồm một đồ thị với tập
đỉnh{0, ..., m − 1} sao cho hai đỉnh riêng biệt được nối với nhau một cách
độc lập với xác suất 12 .
Định lý 1.1.1. ([3]) Cố định số nguyên n > 1. Với xác suất 1 khi m → ∞,

G(m, 12 ) thỏa mãn tính chất n-e.c.
Chứng minh. Cố định một tập S chứa n phần tử trong tập đỉnh V , và cố
định hai tập con A và B rời nhau của S với A ∪ B = S . Cho z ∈
/ S , xác
suất để z chỉ kề với một trong hai tập A và B là ( 12 )n .
Như vậy xác suất để z không thỏa mãn tính chất chỉ kề với một trong hai
tập A và B là

1
1 − ( )n .
2
Do đó, xác suất để các đỉnh thuộc G − (A ∪ B) không thỏa mãn tính chất
chỉ kề với một trong hai tập A và B là
1
(1 − ( )n )m−n .
2
n
Do có m
n cách chọn S và 2 cách chọn của A và B trong S nên xác suất
để G(m, 12 ) không là n-e.c là
m

thỏa mãn các tính chất này, ví dụ như đồ thị Paley. Tuy nhiên, các tính
chất ngẫu nhiên này không nhất thiết biểu thị tính n-e.c. Ví dụ được cho
trong [14] là ngẫu nhiên chuẩn nhưng không phải 4-e.c.

1.2. Một số tính chất cơ bản của đồ thị n-e.c
Đầu tiên ta nhắc lại một số khái niệm trong đồ thị như sau.

¯ . Đó là một đồ thị
Định nghĩa 1.2.1. Phần bù của đồ thị G ký hiệu là G
với tập đỉnh là tập đỉnh của đồ thị G đồng thời nếu 2 đỉnh kề trong G thì
¯ và ngược lại.
không kề trong G
Định nghĩa 1.2.2. Sắc số của một đồ thị G là số màu tối thiểu cần dùng
để tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau phải có màu khác
nhau. Sắc số của đồ thị G kí hiệu là χ(G).
7


Với x ∈ V (G) ta ký hiệu G − x là đồ thị con của G thu được bằng cách
xóa đi điểm x. Đặt N (x) = {y ∈ V (G), y = x : {x, y} ∈ E(G)} và

N c (x) = {y ∈ V (G), y = x : {x, y} ∈
/ E(G)}. Với S ⊆ V (G) ta ký hiệu
G S là đồ thị cảm sinh của G trên S, tức là với x, y ∈ S thì {x, y} ∈ E(S)
khi và chỉ khi {x, y} ∈ E(G). Với N (S) = {y ∈ V (G), y = x : {x, y} ∈
E(G), x ∈ S}, thì N (S) = ∪x∈S N (x)
Định nghĩa 1.2.3. Chỉ số clique của đồ thị G là số đỉnh lớn nhất của tập

U ( U là tập con của tập đỉnh V ) thỏa mãn tính chất: Với mỗi cặp đỉnh
thuộc U luôn tồn tại một cạnh của G nối chúng. Chỉ số clique của đồ thị

có xác suất để G không là n-e.c là
8


m
1
.2n .(1 − ( )n )m−n
2
n
m
n

.2n .(1 − ( 21 )n )m−n < 1.
Theo bất đẳng thức Becnuli ta có

Do G là n-e.c nên

Hơn nữa

m
n

1
1
(1 − ( )n )m−n ≥ 1 − (m − n)( )n .
2
2
≥ 1, nên ta có

1


sao cho v kề với tất cả các đỉnh của U và không kề với đỉnh nào của W .
¯ thì v không kề với đỉnh nào của U và kề với tất cả các
Khi đó trong G
¯ cũng là n-e.c.
đỉnh của W . Do đó, G
(4) Chọn U gồm n điểm và W là tập rỗng. Do G là n-e.c nên tồn tại

v ∈ V − (U ∪ W ) sao cho v kề với tất cả các đỉnh của U và không kề với
đỉnh nào của W . Phải tô màu υ và các đỉnh trong U bởi các màu khác
nhau nên cần n + 1 màu. Vậy χ(G) ≥ n + 1.
Chọn U1 = {u1 } và W1 là tập gồm n − 1 đỉnh. Do G là n-e.c nên tồn
tại u2 ∈ V − (U1 ∪ W1 ) sao cho u2 kề với u1 . Chọn U2 = {u1 , u2 } và

W2 là tập gồm n − 2 đỉnh. Khi đó cũng tồn tại u3 ∈ V − (U2 ∪ W2 )
sao cho u3 kề với U2 = {u1 , u2 }. Chọn U3 = {u1 , u2 , u3 } khi đó U3 có
các đỉnh đôi một kề nhau. Tiếp tục quá trình trên ta sẽ thu được tập
Un+1 = {u1 , u2 , u3 , ..., un+1 } gồm n + 1 đỉnh đôi một kề nhau. Như vậy
ω(G) ≥ n + 1.
(5) Chọn x ∈ S . Do G là n − e.c nên tồn tại đỉnh zx kề với x và không
kề với các đỉnh khác của S . Ta có zx ∈ N (S). Hơn nữa, với x = x thì

zx = zx . Từ đó ta suy ra |N (S) ≥ |S|.

Định lý 1.2.2. Nếu n > 1, thì với mỗi đỉnh x của G ta có các đồ thị

G − x, G N (x) và G N c (x) là đồ thị (n − 1)-e.c.
Chứng minh. Với x ∈ V (G), xét cặp tập con U, W của tập đỉnh V (G

N c (x)) sao cho U ∩ W = ∅ và |U | + |W | = n − 1. Khi đó (U + x) ∩ W = ∅

2
|N c (x)| ≤ mec (n)− mec (n)−1
−1 ( giá trị 1 ở đây là điểm x). Cũng theo
2
.
Định lý 1.2.2 thì G N c (x) là (n − 1)-e.c nên mec (n − 1) ≤ mec (n)−1
2
Từ đó ta có điều cần chứng minh.

Dễ dàng để chỉ ra rằng mec (1) = 4. Có chính xác ba đồ thị 1-e.c cấp 4
không đẳng cấu là: 2K2 , C4 và P4 ( xem Hình 1.1).

Hình 1.1: Đồ thị 1-e.c với cấp nhỏ nhất

Theo Hệ quả 1.2.1, mec (2) ≥ 2.mec (1) + 1 = 9. Với hai đồ thị G và H ,
tích Descartes của G và H (ký hiệu là G H ) có tập đỉnh V (G) × V (G)
và các cạnh {(a, b); (c, d)} ∈ E(G H) nếu và chỉ nếu {a, c} ∈ E(G) và

b = d hoặc a = c và {b, d} ∈ E(G).
11


Trong [5] ta có chú ý đầu tiên là mec (2) = 9 và K3 K3 là 2-e.c. Theo [2]
ta cũng thu được K3 K3 là dạng đẳng cấu duy nhất của đồ thị 2-e.c có
cấp 9. Đồ thị K3 K3 được cho trong Hình 1.2.

Hình 1.2: Đồ thị 2-e.c có cấp nhỏ nhất duy nhất

Cũng theo Hệ quả 1.2.1, mec (3) ≥ 2.mec (2) + 1 = 19. Tuy nhiên, một đồ
thị 3-e.c với 19 đỉnh là đồ thị 9- chính quy và vì thế mec (3) ≥ 20. Kết

ta bắt đầu với các ký hiệu và khái niệm cơ bản.
Ký hiệu Fq là trường hữu hạn q phần tử, trong đó q là lũy thừa của một
số nguyên tố. Ký hiệu Fq [x] là vành đa thức trên Fq và F∗q là nhóm nhân
các phần tử khác 0 của Fq .
Một đặc trưng χ của F∗q là một ánh xạ từ F∗q vào nhóm nhân các số phức
sao cho |χ(x) = 1| với ∀x ∈ F∗q và χ(xy) = χ(x).χ(y) với x, y ∈ F∗q . Trong
số các đặc trưng của F∗q chúng ta có đặc trưng tầm thường χ0 định nghĩa
bởi χ(x) = 1 với ∀x ∈ F∗q . Các đặc trưng khác của F∗q được gọi là đặc
trưng không tầm thường. Với mỗi đặc trưng của F∗q chúng ta kết hợp đặc
trưng liên hợp định nghĩa bởi χ(x) = χ(x) với ∀x ∈ F∗q . Đặc trưng χ có
cấp d nếu χd = χ0 và d là số nguyên dương nhỏ nhất có tính chất này.
Chúng ta mở rộng khái niệm đặc trưng không tầm thường cho trường Fq
bằng cách định nghĩa χ(0) = 0. Với χ0 ta định nghĩa χ(0) = 1. Chú ý
rằng χt (a) = χ(at ) với a ∈ Fq và t là một số nguyên dương. Nếu χ là đặc
trưng không tầm thường của Fq thì theo [18] chúng ta có

χ(x − a)χ(x − b) = −1
x∈Fq

với a, b ∈ Fq và a = b. Trước khi định nghĩa về đồ thị Paley chúng ta có
khái niệm về đồ thị chính quy như sau.
Định nghĩa 1.3.1. Đồ thị chính quy là một đồ thị trong đó mỗi đỉnh có số
đỉnh kề bằng nhau, nghĩa là các đỉnh có bậc bằng nhau. Một đồ thị chính
quy với các đỉnh có bậc bằng k được gọi là đồ thị chính quy bậc k hay đồ
thị k -chính quy.
Định nghĩa 1.3.2. Một đồ thị G là k - chính quy với v đỉnh, sao cho mỗi
cặp đỉnh nối với nhau có chính xác λ đỉnh kề chung, và mỗi cặp đỉnh không

13


χ(f (x))| ≤ (m − 1)q 1/2

|
x∈Fq

Một đồ thị Paley bậc 3 có cấp q ≡ 1( mod 3) có các đỉnh kề với các đỉnh
khác nếu hiệu của nó là lập phương của một phần tử trong Fq . Một đồ thị
14


Paley bậc 4 có cấp q ≡ 1( mod 8) có các đỉnh kề với các đỉnh khác nếu
hiệu của nó là lũy thừa bậc 4 của một phần tử trong Fq . Kết quả dưới đây
được chứng minh bằng cách sử dụng ước lượng tổng đặc trưng.
Định lý 1.3.4. ([20])

√
(3)
(1) Nếu q > (2n.22n−1 − 22n + 1)2n q + 3n.2−n .32n−1 thì Pq là n-e.c.
√
(4)
(2) Nếu q > (2n.22n−1 − 22n + 1)3n q + 4n.2−n .42n−1 thì Pq là n-e.c.
Cho q = pr là lũy thừa của một số nguyên tố sao cho q ≡ 1( mod 4) và

p ≡ 3( mod 4). Cho v là một phần tử sinh của nhóm nhân của Fq . Do
đó v là một căn nguyên thủy của q . Định nghĩa đồ thị P ∗ (q) có các đỉnh
là các phần tử của Fq , và với hai đỉnh a, b bất kỳ được nối với nhau nếu
|a − b| = v j , trong đó j ≡ 0( mod 4) hoặc j ≡ 1( mod 4). Tương tự các
đồ thị Paley, đồ thị P ∗ (q) cũng là đồ thị chính quy mạnh, tự bù, và đối
xứng. Sử dụng ước lượng tổng đặc trưng ta đưa ra được kết quả dưới đây.
Định lý 1.3.5. ([7]) Nếu q = pr là lũy thừa của một số nguyên tố sao cho


[χ(w−vj )−1][i−χ(w−vj )]
j=1

15


Chúng ta ước lượng giá trị của |f (S)| bằng cách ước lượng giá trị của

|g(S)| và |g(S) − f (S)|. Khai triển g(S) chúng ta có (chú ý rằng trong
phần còn lại của chứng minh thì và các i có modulo là 1)
q−1

g(S) =

n1 q−1

1+
w=0

n1 q−1

χ(w − ui ) +

1
i=1 w=0

i=1 w=0

n2 q−1

Chúng ta sẽ ước lượng T . T chứa 22n − 5 phần tử dạng
q−1

χ(w − ui1 ).....χ(w − uia ).χ(w − vj1 ).....χ(w − ujb ).
w=0

Do χ là nhân, chúng ta có thể thay đổi mỗi phần tử thành dạng χ(f (w)),
trong đó f là một đa thức, mỗi nghiệm của f có bội nhiều nhất là 2. Do
đó f không là lũy thừa cấp 4. Theo định lý 1.3.3, giá trị tuyệt đối của mỗi
1

phần tử cấp s là nhỏ hơn hoặc bằng (s − 1)q 2 . Có

2n
s

phần tử cấp s. Do

đó

|T | = |g(S) − q| ≤

1
1
2n
(s − 1)q 2 ≤ 2n.22n .q 2 .
s

Từ đó, ta có
1

{u1 , u2 , ..., un1 } và không kề với bất cứ đỉnh nào thuộc W = {v1 , v2 , ..., vn2 }
mà U ∩ W = ∅ và |U | + |W | = n1 + n2 = n. Vậy P ∗ (q) là n-e.c theo định
nghĩa.

17


Chương 2
Xây dựng và phân loại một số đồ
thị n-e.c
Như đã mô tả ở phần đầu của Chương 1, ta đã biết đồ thị 1-e.c là đồ
thị không có đỉnh cô lập cũng không có đỉnh phổ quát. Trong chương này
chúng ta sẽ tập trung xây dựng các đồ thị n -e.c sau đó sẽ phân loại và tìm
hiểu cụ thể hơn các lớp đồ thị: 2-e.c, 3-e.c và các đồ thị n-e.c với n ≥ 4.

2.1. Đồ thị n-e.c
Đầu tiên, ta đi xây dựng đồ thị n-e.c bằng cách sử dụng hình học hữu
hạn. Cố định hai số nguyên dương v, λ và cố định k sao cho 2 ≤ k < v .
Một cấu trúc khối cân bằng khuyết cấp v ký hiệu là BIBD(v, k, λ) là một
cặp thứ tự (V, B) trong đó V là tập chứa v điểm còn B là tập hợp các tập
con của tập V được gọi là các khối thỏa mãn:
(1) Mỗi khối có chính xác k phần tử.
(2) Mỗi tập con chứa 2 phần tử của V được chứa trong chính xác λ
khối.
Với A là tập khác rỗng các phần tử được gọi là đỉnh, và L là họ các tập
con của A được gọi là đường, một mặt phẳng affine là một cặp (A, L) thỏa
mãn các tính chất sau.
(1) Qua hai điểm bất kỳ xác định duy nhất một đường thẳng.
(2) Từ một đường thẳng l và một điểm x ∈
/ l, khi đó có duy nhất một


S ⊆ l∞ . Định nghĩa G(q, S, A) là đồ thị có các đỉnh là các điểm trong A,
và hai đỉnh p, q là kề nhau nếu và chỉ nếu đường thẳng pq có hệ số góc
trong S . Khi đó, G(q, S, A) là một đồ thị SRG(q 2 , |S|(q −1), q −2+(|S|−
1)(|S| − 2), |S|(|S| − 1)). Ký hiệu G(q, A) là họ các đồ thị G(q, S, A) với
các tất cả các lựa chọn của S . Nếu 0 ≤ k ≤ q + 1 là cố định, thì ta viết
19


G(q, k, A) là họ con tất cả các đồ thị trong G(q, A) với |S| = k . Với k cố
định, G(q, k, A) có thể chứa các đồ thị không đẳng cấu.
Cố định A là mặt phẳng affine với cấp chẵn q ≥ 8 được tọa độ hóa bởi
q
2 hệ số
q(q−2) q(q−2)
SRG(q 2 , q(q−1)
2 ,
4 ,
4 ) (đó

F2k . Chọn S là một tập cố định nào đó có

góc trong l∞ . Khi

đó G(q, S, A) là một

là một đồ thị hình

vuông La tinh).
Chúng ta có thể xét G(q, 2q , A) như một không gian xác suất với

Chứng minh. Cố định hai tập đỉnh rời nhau X và Y của G, |X ∪ Y | = n.
Đặt U = X ∪ Y . Chúng ta sẽ chứng minh rằng với q đủ lớn, với xác suất

1 thì có một đỉnh z chỉ kề với một trong hai tập X và Y . Để chỉ ra điều
này chúng ta sẽ xây dựng một tập PU các điểm z không thuộc U , sao cho
với xác suất 1 thì z ∈ PU . Đặt s = [q b ], với b < 1 cố định.
Cố định điểm v ∈ A. Phép chiếu từ v lên l∞ , là ánh xạ

πv : A {v} → l∞
biến điểm x thành giao của vx với l∞ . Do đó, πv (x) là hệ số góc của đường
thẳng vx. Nếu V là một tập điểm thì πv (V ) = ∪x∈V πv (x).
Với q đủ lớn, chúng ta xây dựng một tập điểm PU không giao với U và
thỏa mãn các tính chất dưới đây.
(1) Nếu p ∈ PU thì |πp (U )| = n.
(2) Với mọi cặp điểm phân biệt p, q ∈ PU , thì πp (U ) ∩ πq (U ) = ∅.
(3) |PU | = s.
Đầu tiên, chọn một điểm p1 ∈
/ U nào đó sao cho p1 không nằm trên bất
cứ đường nào chứa 2 điểm của U . Với q đủ lớn thì

n+

n
(q − 2) < q 2 ,
2

nên chúng ta có thể chọn được một điểm p1 như vậy. Đặt PU,1 = {p1 }.
Tiếp theo, với một số dương cố định i ≥ s − 1, giả sử rằng PU,i được xây
dựng với q lớn, với PU,i chứa PU,1 và |PU,i | = i. Chúng ta chọn pi+1 ∈
/ U là

tính chất là zx và zy có hệ số góc phân biệt (do (1)). Hơn nữa zx là cạnh
của G nếu và chỉ nếu πz (x) ∈ S . Do đó, xác suất để một đỉnh z không kề
với một trong hai tập X và Y là một hằng số dương
pn = 1 − pm (1 − pn−m ).
Từ tính chất (2) trong định nghĩa tính chất của PU , cứ hai điểm phân biệt
bất kỳ của PU thì hai tập hệ số góc sẽ rời nhau trong l∞ . Đặc biệt, xác
suất pn độc lập với các lựa chọn z ∈ PU . Do đó, xác suất để không tồn tại
b

z ∈ PU kề với một trong hai tập X và Y là (pn )[q ] . Như vậy, xác suất để
Gp (q, A) không thỏa mãn tính chất n-e.c lớn nhất là
q2 n
b
2 (pn )[q ] = O(n log(2q 2 ) + q b log(pn )) → 0(q → ∞)
n

Cuối cùng, chúng ta sẽ tìm hiểu một xây dựng gần đây dựa trên lý
thuyết tổ hợp số và được đưa ra bởi Hausdorff([9]). Xét ma trận với r =

2n(n − 1) + 1 hàng và c cột, trong đó c được chọn thỏa mãn
2c ≥ 2r

2

rc
.
n−1

Chúng ta định nghĩa đồ thị G như sau. Các đỉnh của G là các ma trận


là tập một tập con của V mà không có bất cứ k phần tử nào cùng thuộc
một khối. Như vậy, một tập độc lập trong hệ bộ ba (V, B) là một tập con
của V mà không có bất cứ ba đỉnh nào thuộc cùng một khối.
Một đồ thị giao-khối của một hệ bộ ba Steiner là một đồ thị mà các đỉnh
của nó là các khối của STS(v), và hai khối được nối với nhau nếu giao của
2

v+3
chúng là tập khác rỗng. Một đồ thị như vậy là một SRG( v 6−v , 3v−9
2 , 2 , 9).

Định lý 2.2.1. ([5]) Một đồ thị giao-khối của một hệ bộ ba Steiner cấp v
là 2-e.c nếu và chỉ nếu v ≥ 13.
Chứng minh. Đầu tiên ta chứng minh nếu v ≥ 13 thì một đồ thị giao-khối
của một hệ bộ ba Steiner cấp v là 2-e.c. Thật vậy, xét một STS(v) với

v ≥ 13. Theo định nghĩa thì mỗi khối trong STS(v) chứa 3 phần tử và
23