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







LÊ QUANG HÀM







BƯỚC NHẢY NGẪU NHIÊN TRÊN ĐỒ THỊ









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

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






LÊ QUANG HÀM








BƯỚC NHẢY NGẪU NHIÊN TRÊN ĐỒ THỊ




Chuyên ngà nh: Bảo đảm toán học cho máy tính và hệ thống tính toán
M s : 60 46 35



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



Cán bộ hướ ng dẫ n: TS. Lê Anh Vinh







H NI – 2012
1
MỤC LỤC
Mục lục 1
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1 Cơ bản về E-đồ thị 4
1.1. Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Thuật ngữ và khái niệm đại số . . . . . . . . . . . . . . . . 9
1.3. E-Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Họ E-Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Bước nhảy ngẫu nhiên trên đồ thị. 29
2.1. Xích Markov. . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2. Bước nhảy ngẫu nhiên trên đồ thị . . . . . . . . . . . . . . . 34
2.3. Bước nhảy ngẫu nhiên trên E-đồ thị d-đều . . . . . . . . . . 52
3 Bước nhảy ngẫu nhiên trên đồ thị Paley và đồ thị Marg ulis57
3.1. Đồ thị Paley . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2. Đồ thị Margulis . . . . . . . . . . . . . . . . . . . . . . . . 6 0
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Tài liệu t ham khảo . . . . . . . . . . . . . . . . . . . . . . . 67
2
LỜI NÓI ĐẦU
Trong lý thuyết đồ thị, bước nhảy ngẫu nhiên trên đồ thị dành được rất
nhiều sự quan tâm trong nhiều thập niên qua. Các kết quả của nó ứng
dụng trong rất nhiều các lĩnh vực khác nhau. Việc nghiên cứu trên từng
lớp đồ thị cụ thể cho ta những ứng dụng khác nhau như: thiết kế mạng,
thiết kế thuật toán mã hóa, mật mã, giả ngẫu nhiên Khi nghiên cứu
các E- đồ thị cho ta thấy những tính chất rất đặc biệt như: tốc độ hội
tụ tới phân phối dừng, phân phối dừng, thời gian va chạm, thời gian
phủ Luận văn này tập trung nghiên cứu các E- đồ thị và các tham số
của bước nhảy ngẫu nhiên trên E- đồ thị. Dựa vào đó tôi đưa ra cấu trúc
luận văn như sau:
Chương 1: C ơ bản về E - đồ thị.
Chương này gồm hai phần. Phần thứ nhất đưa ra những khái niệm
và định nghĩa cơ bản về đồ thị. Phần thứ hai đưa ra những khái niệm,
định nghĩa và tính chất liên quan đến đồ thị.
Chương 2: Bước nhảy ngẫu nhiên trên đồ thị.
Chương này gồm hai phần. Phần thứ nhất gồm những khái niệm, định
nghĩa và những kết quả cơ bản của bước nhảy ngẫu nhiên. Phần thứ hai
nghiên cứu bước nhảy ngẫu nhiên trên E- đồ thị và các tính chất của
bước nhảy ngẫu nhiên trên E- đồ thị.
Chương 3: Bước nhảy ngẫu nhiên trên đồ thị Paley và đồ thị
Margulis.

Chương này áp dụng bước nhảy ngẫu nhiên trên hai đồ thị là đồ thị
Paley và đồ thị Magulis.
Để hoàn thành luận văn này trước hết tôi xin chân thành cảm ơn TS
3
Lê Anh Vinh người cố vấn với những thảo luận hiệu quả và hướng dẫn
nhiệt tình. Đồng thời tôi cũng xin chân thành cảm ơn TS Lê Trọng Vĩnh
đã động viên, khuyến khích và giúp đỡ trong suốt quá trình hoàn thiện.
Vì lý do thời gian, nên trong luận văn không tránh khỏi những thiếu
sót, bất hợp lý về nội dung cũng như cách trình bày. Kính mong nhận
được những góp ý của thầy cô.
Hà Nội, tháng 12 năm 2011
Lê Quang Hàm
4
CHƯƠNG 1
CƠ BẢN VỀ E-ĐỒ THỊ
Kiến thức chủ yếu được đưa ra trong chương này, chúng ta dễ dà ng tham
khảo trong các tài liệu viết về lý thuyết đồ thị, E- đồ thị [2], [3], [5], [7].
1.1. Lý thuyết đồ thị
Định nghĩa 1.1. 1. Giả sử có tập V = ∅ các đối tượng tùy ý. E là tập
một số cặp đối tượng thuộc V được sắp thứ tự hoặc không. Cặp (V, E)
được gọi là một đồ thị. Ký hiệu là G = (V, E) hoặc G(V, E). Trong đó
V là tập đỉnh và E là tập cạnh của đồ thị G.
+ Nếu a = (x, y) trong đó x, y ∈ V không sắp thứ tự thì a được gọi là
cạnh (vô hướng) của đồ thị; x, y được gọi là hai đầu của cạnh a (hay
là hai điểm đầu của cạnh a)
+ Nếu b = (u, v) trong đó u, v ∈ V được sắp thứ tự thì b được gọi là
cạnh có hướng (cung) của đồ thị; u là đỉnh đầu, v là đỉnh cuối.
+ Nếu c = (z, z) trong đó z ∈ V là cặp đỉnh trùng nhau thì c được gọi
là một khuyên. Nếu trong hai đỉnh này vẫn quy định thứ tự thì c được
gọi là khuyên có hướng.

Định nghĩa 1.1.2. x, y được gọi là hai đỉnh kề nhau nếu chúng được
nối với nhau bằng một cạnh hay một cung.
+ Hai cạnh có chung ít nhất một đỉnh gọ i là hai cạnh kề nhau. Hai
cung a và b, nếu điểm cuối a trùng với điểm đầu của b thì a và b gọi là
hai cung kề nhau. Dùng D(x) để ký hiệu tập gồm tất cả các đỉnh mà
mỗi đỉnh này có cạnh nối với x.
D
+
(x) là tập tất cả các đỉnh mà từ x có cung đi tới.
5
D
−
(x) là tập tất cả các đỉnh có cung đi tới x.
Định nghĩa 1.1.3. (i) Nếu tập E gồm toàn cạnh thì G(V, E) là đồ thị
vô hướng.
(ii) Nếu tập E gồm toàn cung thì G(V, E) là đồ thị có hướng.
(iii) Nếu tập E gồm cả cạnh và cung thì G(V, E) được gọi là đồ thị
hỗn hợp.
(iv) Nếu trong đồ thị G(V, E), hai đỉnh bất kỳ đều được nối với nhau
bằng không quá một cạnh (có hướng hay vô hướng) thì G gọi là đồ thị
đơn.
(v) Nếu trong đồ thị G(V, E) có ít nhất một cặp đỉnh được nối với
nhau không ít hơn hai cạ nh có hướng hoặc vô hướng thì G(V, E) được
gọi là đa đồ thị.
Định nghĩa 1.1.4. (i) Đồ thị vô hướng G = (V, E) được gọi là đồ thị
đầy đủ nếu mỗi cặp đỉnh của nó được nối với nhau bởi đúng một cạnh.
(ii) Một đa đồ thị vô hướng mà mỗi cặp đỉnh của nó được nối với
nhau bằng đúng k cạnh được gọi là đồ thị k-đầy đủ.
(iii) Một (đa) đồ thị được gọi là (đa) đồ thị phẳng nếu nó có ít
nhất một dạng biểu diễn hình học trên mặt phẳng mà các cạnh chỉ cắt

nhau ở đỉnh.
(iv) Một (đa) đồ thị với số cạnh của mỗi đỉnh đều hữu hạn được gọi
là (đa) đồ thị hữu hạn địa phương.
Định nghĩa 1.1.5. (i) Giả sử x là đỉnh tùy ý của đồ thị G = (V, E).
Người ta gọi số cạnh và cung của đỉnh x là bậc của đỉnh x, kí hiệu là
d(x).
(ii) Đồ thị mà bậc của tất cả các đỉnh đều bằng nhau và bằng d thì
được gọi là đồ thị d-đều.
Định nghĩa 1.1.6. Dãy đỉnh α = (x
1
, x
2
, . . . , x
m
) được gọi là một xích
nếu với mọi 0  t  m − 1 thì cặp x
t
, x
t+1
kề nhau. Ta cũng nói xích
6
nối giữa đỉnh x
1
và đỉnh x
m
hoặc xích α đi từ đỉnh x
1
đến đỉnh x
m
.

Hình 1.1:
(i) Một xích mà có hai đầu trùng nhau thì được gọi là chu trình.
(ii) Một xích được gọ i là xích sơ cấp nếu nó đi qua mỗi cạnh của đồ
thị không quá một lần.
(iii) Một chu trình được gọi là chu trình sơ cấp nếu nó đi qua mỗi
đỉnh của đồ thị không quá một lần.
(iv) Một xích được gọi là xích đơn nếu nó đi qua mỗi đỉnh của đồ
thị không quá một lần.
(v) Một chu trình được gọi là chu trình đơn nếu nó đi qua mỗi cạnh
của đồ thị không quá một lần.
Định nghĩa 1.1.7. (i) Tổng số cạnh xuất hiện trong chu trình α được
gọi là độ dài của chu trình.
(ii) Tổng số cạnh xuất hiện trong xích α đượ c gọi là độ dài của xích
và ký hiệu bởi |α|.
Định nghĩa 1.1.8. Giả sử G = (X, E) là đồ thị có hướng. Dãy đỉnh
β = (y
1
, y
2
, , y
t
, y
t+1
, , y
m
) được gọi là một đường trong G nếu với mọi
0  t  m − 1, có một cung từ y
t
sang y
t+1

. Ta còn nói rằng đường β
xuất phát từ đỉnh y
1
đi tới đỉnh y
m
. Trong đó y
1
là đỉnh đầu của đường
β và y
m
là đỉnh cuối của đường β.
7
Định nghĩa 1.1.9. (i) Một đường có đỉnh đầu trùng với đỉnh cuối thì
gọi là một vòng.
(ii) Một đường đi qua mỗi đỉnh không quá một lần thì gọi là đường
sơ cấp.
(iii) Một vòng đi qua mỗi đỉnh không quá một lần thì gọ i là vòng sơ
cấp.
(iv) Một đường đi qua mỗi đỉnh cung không quá một lần thì gọi là
đường đơn.
(v) Một vòng đi qua mỗi cung không quá một lần thì gọi là vòng
đơn.
Định nghĩa 1.1.10. Tổng số các cung xuất hiện trên đường β (vòng β)
được gọi là độ dài của đường β (vòng β).
Định nghĩa 1.1. 11 . Giả sử G = (V, E) là một đồ thị vô hướng .
(i) Hai đỉnh a, b thuộc V được gọi là hai đỉnh liên thông (hay cặp
đỉnh liên thông) nếu chúng được nối với nhau ít nhất một xích.
(ii) Đồ thị vô hướng G(V, E) được gọi là đồ thị liên thông nếu mỗi
cặp đỉnh của nó đều liên thông với nhau.
Định nghĩa 1.1. 12 . Giả sử G = (V, E) là đồ thị có hướng.

(i) Cặp đỉnh c, d thuộc X được gọi là hai đỉnh liên thông (hay cặp
đỉnh liên thông) nếu có ít nhất một đường đi từ c đến d hoặc ngược lại.
(ii) Đồ thị có hướng G(V, E) được gọi là đồ thị liên thông mạnh
nếu mỗi cặp đỉnh của nó đều liên thông với nhau.
Định nghĩa 1.1.13. Giả sử G = (V, E) là một đồ thị tuỳ ý. Mỗi đồ
thị con của G mà liên thông hay liên thông mạnh đều được gọi là một
thành phần liên thông của G.
Định nghĩ a 1.1.14 . Đỉnh x trong đồ thị liên thông được gọi là đỉnh
cắt nếu đồ thị nhận được bằng cách bỏ điểm x sẽ là đồ thị không liên
thông.
8
Ví dụ 1.1.15. Cho đồ thị (Hình 1.2)
Hình 1.2:
+ Các thành phần G
1
, G
2
, G
3
, G
4
liên thông, G không là đồ thị liên thông.
+ G
1
, G
2
, G
3
, G
4

là thành phần liên thông của G.
Định nghĩa 1.1. 16 . Đồ thị tự bù:
Cho G=(V,E) là một đồ thị hữu hạn. Đồ thị bù của G là G với
V (G) = V (G),
và E(G) được xác định như sau:
(x, y) ∈ E(G) ⇔ (x, y) /∈ E(G).
Đồ thị G gọi là tự bù nếu nó đẳng cấu với phần bù của nó.
9
Ví dụ 1.1.17.
Hình 1.3:
C
5
là tự bù vì C
5
∼
=
C
5
(Hình 1.3)
Đồ thì đều mạnh:
Cho đồ thị κ- đều G với |G| = n. Nếu có hai số nguyên λ, µ thỏa mãn.
Mọi cặp đỉnh kề đều có λ đỉnh kề chung và mọi cặp đỉnh không kề
đều có µ đỉnh kề chung.
Thì G gọi là một đồ thị đều mạnh với các tham số (n, κ, λ, µ) và ký
hiệu srg(n, κ, λ, µ).
Đồ thị đối xứng:
Đồ thị G được gọi là đối xứng nếu cho trước các cặp đỉnh kề (u
1
; v
1

), (u
2
; v
2
)
bất kỳ của G thì tồn tại một tự đẳng cấu.
f : V (G) −→ V (G)
sao cho
f(u
1
) = u
2
và f(v
1
) = v
2
.
1.2. Thuật ngữ và khái niệm đại số
Định nghĩa 1.2.1. Chúng ta sẽ làm việc với các thuậ t ngữ đại số sau
đây.
- Chúng ta sẽ làm việc chủ yếu trên trường số thực R
- Dùng R
n×m
là không gian các ma trận thực n ×m. Dùng M
n
(R) =
R
n×n
chúng ta sẽ coi véc tơ cộ t v ∈ R
n

như ma trận trong R
n×1
.
10
- Dùng I
n
để biểu thị ma trận đường chéo n ×n. Chúng ta viết I khi
không có sự nhầm lẫn về kích cỡ của ma trận, J
n
nếu là ma trận đơn vị.
- Dùng A
T
để biểu thị ma trận chuyển vị của A, A là đối xứng nếu
A = A
T
, A là trực giao nếu AA
T
= I.
- Ma trận thực A thuộc M
n
(R) với các phần tử a
i,j
 0 được gọi là
ma trận ngẫu nhiên kép nếu

j
a
kj
=


i
a
ik
= 1 với mọi 1  k  n.
- Tích của các vec tơ là x, y = x
1
y
1
+ ···+ x
n
y
n
. Chuẩn L
1
của một
vec tơ x được biểu thị bởi |x|
1
và bằng tổng

n
i=1
|x
i
|. Chuẩn L
2
của x
được biểu thị bởi ||x||
2
và bằng


x, x.
- Hai véc tơ x và y được gọi là trực giao nếu x, y = 0. Nếu x và y
trực giao, chúng ta viết x⊥y.
+ Biểu diễn đồ thị bằng ma trận kề. Cho đồ thị G(V, E) và n đỉnh.
Mỗi đồ thị G(V, E) được đặc trưng bởi một ma trận kề A = (a
ij
)
n×n
.
Trong đó: a
ij
là số cạnh (cung) nối đỉnh i và j của đồ thị G vô hướng
(có hướng).
Ví dụ 1.2. 2. Cho đồ thị G(V, E) vô hướng (Hình 1.4), trong đó
V = {0, 1, 2, 3},
E = {(0, 1), (0, 2), (0, 3), (1, 2)}.
Hình 1.4:
11
Khi đó ta có
A =



0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0




.
Ví dụ 1.2. 3. Cho đồ thị G(V, E) có hướng (Hình 1 .5) . Trong đó
V = {0, 1, 2, 3},
E = {(0, 1); (0, 2); (1, 2); (2, 3); (3, 0)}.
Hình 1.5:
Khi đó ta có
A =



0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0



.
Định nghĩa 1.2.4. Một trường F là một tập có ít nhất hai phần tử, với
hai phép toán ⊕ gọi là phép cộng và ∗ gọi là phép nhân thỏa mãn các
tiên đề sau:
(1) F cùng với các phép toá n ⊕ là một nhóm Abel (với phần tử trung
hòa ký hiệu là 0).
(2) F
∗
= F\{0} cùng với các phép toán ∗ là một nhóm Abel (với phần
tử đơn vị ký hiệu là 1).
(3) Luật phân phối: với mọi a, b, c ∈ F, chúng ta có (a ⊕ b) ∗ c =
a ∗ c ⊕ b ∗ c.
12

Chú ý 1.2.5. Phần tử 0 là một phần tử ngoại lệ không có phần tử nghịch
đảo.
Ví dụ 1.2.6. (1) Q, R, C cùng với các phép cộng + và phép nhân * tạo
thành các trường.
(2) Tập con Q[i] = {a + bi ∈ C : a, b ∈ Q} của C là một trường. Gọi
là trường hữu tỉ Gauss.
(3) Vành các số nguyên modulo p, Z
p
là một trường nếu p là một số
nguyên tố.
Định nghĩa 1.2.7. Số đặc trưng của trường F (ký hiệu là CharF) là
số nguyên dương nhỏ nhất n sao cho n1=0. Trong đó n1 là ký hiệu hình
thức của tổng n số 1: 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ ··· ⊕ 1. Nếu n1 không bằng 0 thì
ta nói F có số đặc trưng là 0.
Lưu ý rằng số đặc trưng của mộ t trường có thể không bao giờ là 1 vì
1 ∗ 1 = 0. Nếu Char F = 0 thì Char F phải là một số nguyên tố. Vì nếu
Char F = n = rs trong đó r và s là các số nguyên dương lớn hơn 1. Khi
đó (r1)(s1) = n1 = 0, nên hoặc r1 hoặc s1 bằng 0, điều này nói lên rằng
Char F < n.
Định nghĩa 1.2.8. Nếu F và E là các trường và F ⊆ E, ta nói E là một
sự mở rộng của F và F là một trường con của E và ta viết F  E.
Lưu ý rằng nếu F  E thì ta có thể xem E như một không gian vectơ
trên F, vì nếu chúng ta xét các phần tử của E như các vectơ và các phần
tử của F như các vô hướng thì các tiêu đề của một không gian vectơ được
thỏa mãn. Số chiều của không gian vectơ này gọi là bậc của sự mở rộng
và được ký hiệu [E : F]. Nếu [E : F] = n < ∞ ta nói E là một sự mở rộng
hữu hạn của F.
Định nghĩa 1.2.9. Một trường con nhỏ nhất F
p
của một trường F với

Char F = p được gọi là một trường nguyên tố
13
Định lý 1.2.10. Số các phần tử của một trường hữu hạn F bằng p
n
,
trong đó p là một số nguyên tố và n ∈ N.
Định lý 1.2.11. Với mọi số nguyên tố p và n ∈ N có một trường với p
n
phần tử.
1.3. E-Đồ thị
Trong phần này chúng ta sẽ giớ i thiêụ về E-đồ thị
Xét một cách trực quan một E-đồ thị là một đồ thị mà với bất kì một
tập nhỏ các đỉnh nào cũng có tập đỉnh kề với nó lớn.
Định nghĩa 1.3.1. Cho đồ thị G = (V, E) với n đỉnh. Với mỗi tập
S ⊆ V ta định nghĩa tập S = V \S.
(i) Tập cạnh biên của S, ký hiệu là ∂S, bao gồm tất cả các cạnh nối
giữa S và S, nghĩa là bao gồm tất cả các cạnh (u, v) ∈ E trong đó u ∈ S
và v /∈ S.
(ii) Tập các đỉnh kề với ít nhất một đỉnh của S được ký hiệu bởi Γ(S).
Chú ý rằng Γ(S) có thể giao với S.
Định nghĩa 1.3. 2. (i) Đại lượng
h(G) = min
S:|S|<
n
2
|∂S|
|S|
gọi là tham số nở cạnh của đồ thị G(hoặc là hằng số Cheeger trong
hình học Riemann).
(ii) Đại lượng

g(G) = min
|S|
n
2
|Γ(S) \S|
|S|
được gọi là tham số nở đỉnh của đồ thị G.
Định nghĩa 1.3.3. Một (n, d, c)-nở cạnh là một đồ thị d-đều, có bậc
n, và có h(G)  c .
Một (n, d, c)-nở đỉnh là một đồ thị d-đều, có bậc n, và có g(G)  c.
14
Hằng số c thường được gọi là tốc độ nở (expansion rate) của đồ thị.
Định nghĩa 1.3.4. Cho đồ thị d-đều, bậc n, G(V,E). Gọi A(G) là ma
trận kề của đồ thị G, ta định nghĩa ma trận kề chuẩn hóa của đồ thị G
là

A =
1
d
A(G).
Ma trận

A có tính chất sau:
n

i=1
a
ij
= 1, ∀i = 1, n và
n


j=1
a
ij
= 1, ∀j = 1, n.
Lúc này

A là ma trận ngẫu nhiên kép. Thêm vào đó

A là ma trận
thực, không âm và đối xứng, vì thế tất cả các giá trị riêng của ma trận
này là thực.
Chúng ta phát biểu mà không chứng minh định lí sau.
Định lý 1.3.5. Gọi A là ma trận n × n đối xứng gồm các số thực. Khi
đó tồn tại một hệ các véc tơ trực giao {v
1
, v
2
, . . . , v
n
} tương ứng với n
giá trị riêng λ
1
, λ
2
, . . . , λ
n
.
Định nghĩa 1.3.6. Gọi λ
1

, λ
2
, . . . , λ
n
là các giá trị riêng của đồ thị G,
với thứ tự 1 = |λ
1
|  |λ
2
|  ···  |λ
n
| chúng ta nói rằng G là λ-nở phổ
nếu |λ
2
|  λ. Hơn nữa, chúng ta định nghĩa λ
2
(G) = |λ
2
|.
Chúng ta sẽ thêm cho định nghĩa này các tham số n và d rằng đồ thị
G là một (n, d, λ)-nở phổ nếu G có n đỉnh đều bậc d và λ
2
(G) = |λ|.
Xét bất kì phân phối xác suất x ∈ R
n
trên các đỉnh của đồ thị, trong
đó x
i
 0, ∀i và


n
i=1
x
i
= 1. Vì

A là ma trận thực và đối xứng, nên có
thể biểu diễn x là tổ hợp tuyến tính của các véc tơ riêng {v
1
, v
2
, . . . , v
n
}
với các giá trị riêng tương ứng λ
1
, λ
2
, . . . , λ
n
, trong đó v
1
= u là phân
phối đều và v
i
⊥u, ∀i = 1. Rõ ràng, hệ số của u trong phân tích này là 1
vì

n
i=1

x
i
= 1. Do đó chúng ta có x = u + c
2
v
2
+ ··· + c
n
v
n
. Trong đó
c
i
∈ R. Ta có

Ax = u +
n

i=2
λ
i
c
i
v
i
và

(A)
t
x = u +

n

j=2
λ
t
i
c
i
v
i
. (1.1)
15
Dễ thấy rằng nếu |λ
2
| càng nhỏ thì tốc độ để hội tụ về u càng nhanh.
Bổ đề 1.3.7. Giá trị riêng của một ma trận kề chuẩn hóa của đồ thị G
bất kì luôn tối đa là bằng 1, tương ứng với véc tơ riêng u.
Chứng minh. Xét bất kì giá trị riêng λ của

A =

A(G) tương ứng với véc
tơ riêng v, sẽ có một vài i nào đó sao cho |v
i
| = max
j
|v
j
| , trong đó
|v

i
| > 0. Khi đó áp dụng bất đẳng thức tam giác ta có
|λ||v
i
| = |
n

j=1
a
ij
v
j
|  |v
i
|
n

j=1
|a
ij
| = |v
i
|.

j
|a
ij
| = 1 vì

A là ma trận không âm và ngẫu nhiên kép. Nên dấu bằng

xảy ra khi v là phân phối đều.
Định nghĩa 1.3.8. Đồ thị bình phương của đồ thị G là G
2
= (V, E
2
),
trong đó (i, j) ∈ E
2
⇐⇒ ∃k ∈ V sao cho (i, k) ∈ E và (k, j) ∈ E.
Nếu ma trận kề chuẩn hóa của G là

A thì ma trận chuẩn hóa của G
2
là

A
2
.
Rõ ràng, nếu λ là một giá trị riêng của ma trận

A thì λ
2
cũng là giá
trị riêng của ma trận

A
2
với cùng một véc tơ riêng.
Bổ đề 1.3.9. Đồ thị G là liên thông nếu và chỉ nếu giá trị riêng 1 của
ma trận


A xuất hiện với bội 1.
Chứng minh. Giả sử G là không liên thông. Khi đó G phải có ít nhất hai
thành phần liên thông. Gọi X ⊂ V là một thành phần liên thông của
đồ thị và đặt Y = V | X. Với mỗi tập S ⊂ V , gọi χ
s
là một véc tơ đặc
trưng của nó, nghĩa là véc tơ có tọa độ i bằng 1 nếu i ∈ S và bằng 0 với
mọi trường hợp khác. Ta phát biểu rằng χ
X
và χ
Y
là hai véc tơ riêng
ứng với giá trị riêng 1.
(

Ax)
i
=

j
a
ij
x
j
=

j∈X
a
ij

x
j
=

1 i ∈ X
0 i /∈ X
Điều này nói lên rằng

Ax = x nên x là một véc tơ riêng ứng với giá
trị riêng 1. Lập luận tương tự ta có y cũng là một véc tơ riêng ứng với
giá trị riêng 1.
16
Giả sử giá trị riêng bằng 1 xuất hiện với bội lớn hơn 1. Khi đó có
một vài véc tơ x⊥u là véc tơ riêng tương ứng với giá trị riêng 1. Gọi
X = {i | x
i
= max
j
x
j
}. Vì λ = 1, điều này nói lên rằng với bất kì i ∈ X,
và với bất kì a
ij
= 0, phải có x
j
= x
i
. Vậy nên a
ij
= 0, ∀i ∈ X, j ∈ V \X

và X không liên thông với V \X.
Bổ đề 1.3.10. Đồ thị liên thông G là đồ thị hai phần nếu và chỉ nếu ma
trận kề chuẩn hóa của nó có một giá trị riêng -1.
Chứng minh. Nếu đồ thị G là hai phần thì đồ thị bình phương của nó là
không liên thông. Nên G
2
có giá trị riêng 1 với bội 2. mỗi giá trị riêng
của G
2
là bình phương giá trị riêng của G. Vì G là đồ thị liên thông nên
nó có giá trị riêng bằng 1 với bội 1, nên tương ứng với một giá trị riêng
1 của. Vì giá trị riêng bằng 1 khác của G
2
cũng phải là bình phương của
giá trị riêng của G nên G phải có giá trị riêng bằng -1.
Nếu G có một giá trị riêng bằng -1, khi đó có một véc tơ riêng x⊥u
sao cho

Ax = −x. Gọi X = {i | x
i
= max
j
x
j
}. Chúng ta có với bất kì
i ∈ X, và với bất kì a
ij
= 0, phải có x
i
= −x

j
. Vậy a
ij
= 0 ∀i, j ∈ X.
Hơn nữa, vì G là liên thông, điều này có nghĩa ∀i ∈ Y = V \Xchúng ta
có x
i
= −max
j
x
j
, do đó không có cạnh nào giữa các đỉnh trong Y . Điều
này dẫn đến G là đồ thị hai phần với một phần là X phần còn lại là
Y .
Bổ đề 1.3.11 . Cho A là một ma trận vuông đối xứng cấp n gồm các
số thực. Gọi λ
1
 λ
2
, . . . ,  λ
n
là phổ của A với hệ các véc tơ trực
chuẩn tương ứng {v
1
, v
2
, , v
n
}. Với k ∈ [n] bất kì, định nghĩa W
k

⊂ R
n
là không gian con được sinh bởi hệ {v
1
, v
2
, , v
k
}. Khi đó chúng ta có
với mọi k thì
Ax, x
x, x
 λ
k
với mọi x ∈ W
k
\ {0} (1.2)
Ay, y
y, y
 λ
k+1
với mọi y ∈ W
⊥
k
\ {0} (1.3)
17
Chứng minh. Vì {v
1
, v
2

, , v
k
} là một cơ sở của W
k
, chúng ta có thể viết
x =

k
i=1
c
i
v
i
với các hằng số c
i
∈ R. Bằng tính chất trực chuẩn, chúng
ta có
Ax, x
x, x
=

k
i=1
λ
i
c
2
i
||v||
2

x, x
=

k
i=1
λ
i
c
2
i
x, x


k
i=1
λ
k
c
2
i
x, x
=
λ
k

k
i=1
c
2
i

x, x
= λ
k
.
Tương tự, vì {v
1
, v
2
, . . . , v
n
} là cơ sở của R
n
nên
W
⊥
k
= Span(v
k+1
, v
k+2
, . . . , v
n
)
Lí luận tương tự sẽ đưa ra được giới hạn trên của
Ay,y
y,y
.
Bổ đề 1.3.1 2. Cho đồ thị G bất kỳ với ma trận kề chuẩn A thì
λ
2

(G) = max
x⊥u
|Ax, x|
x, x
(1.4)
= max
x⊥u
||Ax||
||x||
(1.5)
= max
x⊥u



1 −
1
D||x||
2

(i,j)∈E
(x
i
− x
j
)
2




. (1.6)
Chứng minh. Giả sử G có phổ 1 = λ
1
 λ
2
 ···  λ
n
tương ứng với
các véc tơ riêng trực chuẩn {v
1
, v
2
, . . . , v
k
}.
Chứng minh 1.4.
Nếu λ
2
> 0 thì λ
2
(G) = λ
2
, áp dụng theo bổ đề trên cho k = 1 và cho
y = v
2
∈ W
⊥
1
.
Nếu λ

2
< 0, khi đó λ
2
(G) = λ
n
, nên lấy k = n và x = v
n
∈ W
n
. Áp
dụng bổ đề trên ta có đẳng thức
Ax,x
x,x
= λ
n
và như vậy
|Ax,x|
x,x
= |λ
n
|.
Chứng minh 1.5.
Chúng ta thấy rằng
||Ax|| =

|Ax, Ax| =

|A
2
x, x|.

18
Áp dụng đẳng thức vừa chúng minh suy ra
max ||Ax|| là λ
2
(G)||x||.
Chứng minh 1.6.
Ta có
|Ax, x| =




i,j
a
ij
x
i
x
j



=



2
d

(i,j)∈E

x
i
x
j



=



||x||
2
−
1
d

||x||
2
d −

(i,j)∈E
2x
i
x
j





=



||x||
2
−
1
d

(i,j)∈E
(x
i
− x
j
)
2



.
Bổ đề 1.3.13. Cho A là ma trận thực đối xứng n × n và R là ma
trận n × m sao cho R
T
R = I. Khi đó ma trận B = R
T
AR là một
ma trận m × m mà các giá trị riêng của chúng đan xen với các giá trị
riêng của A. Nếu λ
1

 λ
2
 ···  λ
n
là các giá trị riêng của A và
µ
1
 µ
2
 µ
3
 ···  µ
m
là các giá trị riêng của B, thì với mọi k ∈ [m]
chúng ta có λ
k
 µ
k
 λ
n−m+k
.
Chứng minh. Gọi {v
1
, v
2
, , v
n
} là các véc tơ riêng của A ứng với các
giá trị riêng λ
1

 λ
2
 λ
n
và {w
1
, w
2
, , w
m
} là các véc tơ riêng của
B ứng với các giá trị riêng µ
1
 µ
2
 µ
3
 ···  µ
m
. Gọi
V
k
= Span(v
1
, v
2
, , v
k
),
W

k
= Span(w
1
, w
2
, w
k
).
Với k bất kì, số chiều của W
k
là k. Trong khi số chiều của R
T
V
k−1
tối
đa là k −1, dẫn đến phần bù trực giao của nó có số chiều tối thiểu bằng
n − k + 1.Vậy W
k
∩ (R
T
V
k−1
)
⊥
có một phần tử khác 0, nên sẽ có một
vài véc tơ y = W
y
∩ (R
T
V

k−1
)
⊥
.
Theo định nghĩa y, R
T
v
i
 = 0, ∀i ∈ [k − 1], và tính đối xứng của ma
trân A ta có AR
y
, R
y
 = 0. Dẫn đến R
y
⊥V
⊥
k−1
. Chúng ta có thể áp dụng
19
R
T
R = I, B = R
T
AR, và bổ đề trên để thu được
λ
k

AR
y

, R
y

R
y
, R
y

=
B
y
, y
y, y
 µ
k
.
Áp dụng phân tích tương tự với −A và −B, ta được giới hạn dưới.
Định nghĩa 1.3.14. Với H là một đồ thị con của đồ thị G d-đều, khi
đó ma trận kề chuẩn hóa của H được cho bởi b
ij
=
d
ij
d
, trong đó d
ij
là số
cạnh nối giữa các đỉnh i và j trong H, và d là bậc của G. Gọi m là kích
thước của H, phổ của H có dạng 1  λ
G

1
 |λ
G
2
|  ···  |λ
G
m
|, trong đó
λ
G
1
không nhất thiết bằng 1 vì B không nhất thiết là ng ẫu nhiên kép.
Đặt λ
G
i
(H) = |λ
G
i
|.
Hệ quả 1.3.15. Cho đồ thị G với giá trị riêng lớn nhất thứ hai λ
2
(G).
Gọi H là đồ thị con bất kì của G. Khi đó λ
G
2
(H)  λ
2
(G).
Chứng minh. Gọi n là kích thước của G, m là kích thước của H, và gọi
các đỉnh của đồ thị con của G là {n

1
, n
2
, . . . , n
m
} ⊂ [n]. Đặt R = [r
ij
] là
ma trận n ×m được xác định như sau:
r
ij
=

1 i = n
j
,
0 trong trường hợp khác.
Tính toán đơn giản cho thấy rằng R
T
R = I. Chúng ta muốn B =
R
T
AR là một ma trận kề chuẩn hóa của H. Điều này là vì nếu chúng
ta đặt B = [b
ij
] thì chúng ta thu đượ c b
ij
=

k,i

r
ki
a
ki
r
ij
= a
n
i
n
i
. Nên
theo bổ đề trên các giá trị riêng của H đan xen với giá trị riêng của G,
và do đó λ
G
2
(H)  λ
2
(G).
Bổ đề 1.3.1 6. Gọi H là đồ thị con của đồ thị G với ma trận kề
B = R
T
AR.
Gọi m là bậc của H. Khi đó
λ
G
i
(H) = max
x
|1 −

1
d

(i,j)∈E
((Rx)
i
− (Ry)
j
)|
trong đó E là tập các cạnh của G
20
Chứng minh. Chúng ta đã biết
λ
G
i
(H) = max
x
| R
T
ARx, x |= max
x
| ARx, Rx | .
Vậy chúng ta có thể phân tích đẳng thức
λ
2
(G) = max
x⊥u
| 1 −
1
d||x||

2

(i,j)∈E
(x
i
− x
j
)
2
|,
dùng Rx thay cho x.
Định lý 1.3.17. Nếu G là mộ t λ- nở phổ, thì nó cũng là
2
λ
2
+1
- nở đỉnh.
Chứng minh. Với tập S ⊂ V bất kỳ, xét phân phối xác suất u
S
=
1
2
χ
S
.
Chúng ta có thể viết u
⊥
S
= u
S

− u,
vì
u
⊥
S
, u = u
S
, u − u , u = 0
nên
u
⊥
S
⊥u.
Bằng các biến đổi đơn giản, ta có
||u
⊥
S
||
2
= ||u
S
||
2
− ||u||
2
=
1
|S|
−
1

n
.
Với phân phối x bất kỳ ta có
||x||
2

1
|x
+
|
trong đó x
+
= {i | x
i
> 0}.
Áp dụng bất đẳng thức Cauchy-Schwartz
1 =


i∈x
+
x
i

2
= χ
S
, x
2
 ||χ

S
||
2
||x||
2
= |x
+
| ·

i∈x
+
x
2
i
.
Suy ra
1
|N(S)|
=
1
|(Au
S
)
+
|
 ||Au
S
||
2
.

21
Lại có Au
⊥
S
⊥u, nên ta có thể viết:
1
|N(S)|
−
1
N
 ||Au
S
||
2
− ||u||
2
= ||A(u
S
− u)||
2
. = ||Au
⊥
S
||
2
 λ
2
||u
⊥
S

||
2
= λ
2

1
|S|
−
1
n

.
Suy ra
1
|N(S)|
−
1
n
 λ
2

1
|S|
−
1
n

,
vì
|N(S)| 

1
λ
2
(1 −
|S|
n
) +
|S|
n
|S|và |S| 
n
2
điều đó dẫn đến
|N(S)| 
2
λ
2
+ 1
|S|.
Định lý 1.3.18. Nếu G là một (n, d, 1 + α)-nở đỉnh thì nó cũng là một
(n, d, λ)- nở phổ với λ =

1 −
α
2
d
2
·(8+4α
2
)

.
Chứng minh. Gọi A
2
là ma trận kề chuẩ n hóa của G
2
. Xét đồ thị G
2
=
(V, E), thì γ-nở đỉnh của G
2
tối thiểu cũng phải bằng (1+ α). Với S ⊂ V
bất kỳ sao cho |S| 
n
2
ta luôn có |N(S)|  (1 + α)|S|. Nếu |N(S)| 
n
2
chúng ta áp dụng tính chất trên một lần nữa. Nếu |N(S)| >
n
2
, ta xét
tập con S

⊂ N(S) sao cho |S

| =
n
2
. Ta sẽ có
|N(N(S))|  |N(S


)|  (1 + α)
N
2
 (1 + α)|S|.
Giả sử A
2
có phổ là λ
1
(G
2
)  λ
2
(G
2
)  ···  λ
n
(G
2
). Gọi x là véc tơ
riêng ứng với giá trị riêng λ
2
2
và gọi u là véc tơ riêng ứng với giá trị riêng
λ
1
. Rõ ràng x⊥u nên tồn tại i và j sao cho x
i
> 0 và x
j

< 0. Đặt
V
+
= {i | x
i
> 0}, V
−
= {i | x
i
< 0}, thì , |V
+
| = ∅, |V
−
| = ∅.
Không mất tính tổng quát ta có thể giả sử |V
+
| 
n
2
. Gọi x là véc tơ
được định nghĩa như sau
x =

x
i
nếu x
i
> 0
0 nếu x
i

 0.
22
Ta có
λ
2
(G
2
) =
A
2
x, x
x, x
,
trong đó
A
2
x, x =

i,j
a
ij
x
i
x
j
= ||x||
2
−
1
d


||x||
2
d
2
−

i∈V
+
(i,j)∈E
2x
i
x
j

= ||x||
2
−
1
d
2

||x||
2
d
2
−

i,j∈V
+

(i,j)∈E
2x
i
x
j
−

i∈V
+
j /∈V
+
(i,j)∈E
2x
i
x
j

.
Vì x
j
 0 với j /∈ V
+
ta có
|A
2
x, x|  ||x||
2
−
1
d

2

||x||
2
d
2
−

(i,j)∈E
2x
i
x
j

 ||x||
2
−
1
d
2

(i,j)∈E
(x
i
− x
j
)
2
.
Do đó

λ
2
2
(G)  1 −
1
d
2

(i,j)∈E
(x
i
− x
j
)
2

i∈V
x
i
2
.
Bây giờ ta xây dựng một đồ thị có hướng có trọng số G với tập đỉnh
V = {s, t}∪V
+
∪V , trong đó s là đỉnh vào, t là đỉnh ra (không có cung
ra). Chúng ta định nghĩa các cung và trọng số của đồ thị này như sau:
1. Với mỗi i ∈ V
+
cung (s, i) có trọng số (1 + α).
2. Với mỗi i ∈ V

+
, j ∈ V , cung (i, j) có trọng số bằng 1 nếu (i, j) ∈ E
và bằng 0 nếu (i, j) /∈ E.
3. Với mỗi j ∈ V , cung (j, t) có trọng số 1.
Lát cắt cực tiểu của mạng này là (1 + α)|V
+
|. Rõ ràng lát cắt đó bao
gồm tất cả các cung (s, i) với i ∈ V
+
. Để thấy rằng lát cắt đó là nhỏ nhất
ta xét lát cắt C bất kỳ khác và gọi W = {i ∈ V
+
| (s, i) /∈ C}. Ta có
N(W )  (1 + α)|W |. Do đó luồng qua C đủ lớn để lớn hơn lát cắt được
xây dựng trên.
23
Ký hiệu

E là tập các cạnh có thứ tự thỏa mãn nếu (i, j) ∈ E thì
(i, j), (j, i) ∈

E.
Vì lát cắt cực tiểu là lớn, theo định lý lát cắt cực tiểu luồng cực đại, nên
tồn tại một hàm F : V × V −→ R với các tính chất sau:
1. ∀(i, j) /∈

E, F (i, j) = 0. Và ∀(i, j) ∈

E, 0  F (i, j)  1.
2. Với i ∈ V

+
bất kỳ cố định,

j|(i,j)∈

E
F (i, j) = 1 + α và F (i, j) = 0
với i /∈ V
+
.
3. Với j ∈ V cố định,

i|(i,j)∈

E
F (i, j)  1.
Ta áp dụng bất đẳng thức 2(a
2
+ b
2
)  (a + b)
2
và ∀a, b ∈ (R). Ta có:

(i,j)∈

E
F
2
(

x
i
+ x
j
)
2
 2

(i,j)∈

E
F
2
(i, j)(x
i
2
+ x
j
2
)
= 2

i∈V
x
i
2


(i,j)∈


E
F
2
(i, j) +

(i,j)∈

E
F
2
(j, i)

 (4 + 2α
2
)

i∈V
x
i
2
.

(i,j)∈

E
F (i, j)(x
i
2
− x
j

2
) =

i∈V
x
i
2


(i,j)∈

E
F (i, j) −

(i,j)∈

E
F (j, i)

 α

i∈V
x
i
2
.
Từ đây ta có
λ
2
(G

2
)  1 −
1
d
2

(i,j)∈E
(x
i
− x
j
)
2

i∈V
x
i
2
= 1 −
1
d
2

(i,j)∈E
(x
i
− x
j
)
2


(i,j)∈

E
F
2
(i, j)(x
i
+ x
j
)
2

i∈V
x
i
2

(i,j)∈

E
F
2
(i, j)(x
i
+ x
j
)
2
 1 −

1
d
2


(i,j)∈

E
F (i, j)(x
i
2
− x
j
2
)

2
2(4 + 2α
2
)


i∈V
x
i
2

2
= 1 −
α

2
d
2
(4 + 2α
2
).