ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

MẠC ANH VĂN

MỘT SỐ TÍNH CHẤT CỦA MA TRẬN VÀ ÁP
DỤNG VÀO ĐỒ THỊ

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

Thái Nguyên, 10/2018


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

MẠC ANH VĂN

MỘT SỐ TÍNH CHẤT CỦA MA TRẬN VÀ ÁP
DỤNG VÀO ĐỒ THỊ

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp toán sơ cấp
Mã số:

8460113

NGƯỜI HƯỚNG DẪN KHOA HỌC
GS. TSKH. NGUYỄN VĂN MẬU

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2 Tính chất của ma trận biểu diễn đồ thị và các phép toán đồ
thị
2.1 Tính chất của ma trận biểu diễn đồ thị . . . . . . . . . . . . . .
2.1.1 Ma trận Laplace của đồ thị và một số tính chất cơ bản .
2.1.2 Ma trận Laplace của một cạnh . . . . . . . . . . . . . .
2.1.3 Phân tích ma trận Laplace . . . . . . . . . . . . . . . . .
2.1.4 Định lý Kirchhoff . . . . . . . . . . . . . . . . . . . . . .
2.2 Các phép toán đồ thị . . . . . . . . . . . . . . . . . . . . . . . .
3 Áp


42


ii

Danh mục các ký hiệu, các chữ viết
tắt
• G:

Đồ thị n đỉnh, m cạnh.

• A:

Ma trận kề n × n của G có đường chéo chính bằng 0.

• L = D − A:

Ma trận Laplace của G.

• B:

Ma trận liên thuộc n × m · L = B T B.

• Ckk :

Là phần bù đại số của phần tử thứ k của đường chéo
chính của ma trận vuông L.

• [L]k,k :


1

Mở đầu
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã hình thành và phát triển
từ khá lâu nhưng lại có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của
lý thuyết đồ thị đã xuất hiện từ những năm 30 của thế kỷ XVIII bởi nhà toán
học lỗi lạc người Thụy Sĩ Leonhard Euler. Chính ông là người đã đề xuất mô
hình đồ thị và sử dụng nó để giải bài toán nổi tiếng về cây cầu ở thành phố
K¨onigsberg. Từ đó, lý thuyết đồ thị ngày càng khẳng định được vị trí quan
trọng trong việc áp dụng để giải quyết nhiều bài toán trên mọi lĩnh vực.
Đồ thị mô tả các quan hệ hai ngôi trên tập hợp một cách trực quan sinh
động: giúp chúng ta mô ta các bài toán phức tạp trở lên cụ thể, đơn giản hơn.
Sơ đồ biểu diễn một hệ thống các tuyến bay của một hãng hàng không là một
hình ảnh của đồ thị. Các đối tượng là các sân bay, mỗi đường bay thẳng sẽ
biểu diễn mối liên hệ giữa 2 sân bay đầu cuối của tuyến.
Các tính chất của đồ thị có thể được biểu diễn bằng ngôn ngữ đại số tuyến
tính và những kết quả của đại số tuyến tính sẽ được thể hiện trực quan bằng
đồ thị. Ma trận là một khái niệm của Đại số tuyến tính. Ma trận có ứng dụng
trong hầu hết các lĩnh vực khoa học. Ma trận có vai trò khá quan trọng trong
lý thuyết đồ thị. Có thể nói ma trận là một công cụ kết nối giữa lý thuyết đồ
thị và đại số tuyến tính. Trong phạm vi của luận văn tốt nghiệp thạc sĩ chuyên
ngành phương pháp toán sơ cấp từ sự đề xuất hướng nghiên cứu và trực tiếp
hướng dẫn của GS.TSKH. Nguyễn Văn Mậu, chúng tôi xác định đề tài là “Một
số tính chất của ma trận và áp dụng vào đồ thị”.
Với đề tài này, tôi hy vọng rằng sẽ làm rõ mối liên hệ giữa đại số tuyến tính
và lý thuyết đồ thị dựa trên các biểu diễn ma trận của nó, từ đó tìm ra được
ứng dụng. Kết quả của đề tài cũng là sự thể hiện quá trình tập dượt nghiên
cứu của tôi.
Mục tiêu của luận văn là tìm hiểu sự liên hệ giữa ma trận và đồ thị, phổ


3

Chương 1
Kiến thức chuẩn bị
Trong chương này, chúng tôi trình bày một số kiến thức cơ sở cho chương
sau. Trước tiên là trình bày khái niệm đồ thị có hướng và đồ thị vô hướng, từ
đó biểu diễn đồ thị dưới dạng ma trận và ý nghĩa. Mục đích chính của chương
này nhằm giới thiệu một vài khái niệm cơ bản của lí thuyết đồ thị, đặc biệt là
phổ của đồ thị. Kiến thức trong chương này sử dụng tài liệu [1], [2] và [4].

1.1

Khái niệm của đồ thị và phổ của đồ thị

1.1.1

Khái niệm đồ thị

Định nghĩa 1.1.1. Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E),
ở đây V là một tập hữu hạn; còn E là tập với các phần tử là các tập con hai
phần tử trên V ,
E ⊆ {{u, v}|u, v ∈ V, u = v}.
Các phần tử của V được gọi là các đỉnh, tập đỉnh của G được ký hiệu là
V (G). Các phần tử của E được gọi là các cạnh, tập cạnh của đồ thị vô hướng
G được ký hiệu là E(G). Nhưng để đơn giản hơn ta có thể viết “đỉnh v ∈ V ”
hay “cạnh e ∈ E”. Cho a, b ∈ V , nếu tồn tại e ∈ {a, b} thì khi đó e là một cạnh
của G với hai đỉnh đầu mút là a, b hay a, b là hai đỉnh liên thuộc với e. Cạnh
e = {a, b} thường được ký hiệu ngắn gọn là ab hay ba. Trong luận văn này, ta
chỉ xét tới đơn đồ thị, không xét tới đồ thị có khuyên và đa đồ thị. Do vậy khi

Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi
là các cung của đồ thị vô hướng G. Nếu (a, b) ∈ E thì (a, b) được gọi là cung
của G với đỉnh đầu là a, đỉnh cuối là b và có hướng từ a tới b. Khi đã cho
G = (V, E) là đồ thị có hướng, cung (a, b) ∈ E thường được ký hiệu ngắn gọn
là ab với a là đỉnh đầu và b là đỉnh cuối; ba là cạnh với b là đỉnh đầu, a là đỉnh
cuối.
Biểu diễn một đồ thị có hướng trên mặt phẳng trực quan tương tự như biểu
diễn đồ thị vô hướng: Các đỉnh của V được biểu diễn bằng các vòng tròn nhỏ
(rỗng hoặc đặc), còn các cung được biểu diễn bằng một đường cong có hướng
(với mũi tên) từ đỉnh đầu tới đỉnh cuối.
Định nghĩa 1.1.4. Đồ thị có hướng hoặc vô hướng G = (V, E) được gọi là đồ
thị có trọng số (hay thường gọi tắt là trọng đồ) nếu có ít nhất một trong hai
hàm:
f : V → WV và g : E → WE
được xác định. Ở đây Wv và WE là các tập số. Giá trị f (v) cho v ∈ V được
gọi là trọng số của đỉnh v, còn giá trị g(e) cho e ∈ E được gọi là trọng số của
cung hay cạnh e. Người ta cũng thường ký hiệu trọng đồ bằng G = (V, E, f )
hay hay G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f , chỉ một hàm g hay
cả hai hàm f và g được xác định.
Trong khuôn khổ luận văn này, chúng ta chỉ sử dụng tới G = (V, E, g).
Biểu diễn một đồ thị G = (V, E, g) có trọng số trên mặt phẳng ta biểu diễn
đồ thị có hướng và gắn giá trị trọng số tương ứng lên trực tiếp sát phía bên
cạnh của cung mang giá trị đó.
Ví dụ 1.1.5. Cho đồ thị có hướng có trọng số với V = {a, b, c, d, f, g}, E =
{ad, db, dc, bc, cf, cg, gf }, g(ad) = g(dc) = g(gf ) = 3, g(db) = g(bc) = 2,
g(cf ) = g(cg) = 4.
Khi đó biểu diễn của đồ thị có trọng số G:

Hình 1.3: Đồ thị có trọng số G



trong đó tổng lấy qua tất cả các đỉnh kề v của đỉnh u. Chúng ta chú ý hai hệ
quả sau từ phương trình trên mà ta gọi là các phương trình giá trị riêng của
G.
Vì A là một ma trận đối xứng thực, các giá trị riêng là những số thực.
Chúng ta thường ký hiệu các giá trị riêng là λ1 , λ2 , . . . , λn và trừ khi chúng ta
chỉ ra trong những trường hợp khác, chúng ta giả sử rằng λ1 ≥ λ2 ≥ · · · ≥ λn .
Khi cần, chúng ta sử dụng ký hiệu λi = λi (G) (i = 1, 2, . . . , n).
Định nghĩa 1.1.6. Tập các giá trị riêng của ma trận kề A của đồ thị G được
gọi là phổ của đồ thị G.


7

Giá trị riêng lớn nhất λ1 (G) được gọi là chỉ số (index) của G. Với mọi số
nguyên k ≥ 0, moment phổ thứ k của G là ni=1 λki ký hiệu bởi sk . Chú ý rằng
sk là tổng đường chéo của Ak và n moment phổ đầu tiên xác định phổ của G.
Mệnh đề 1.1.7. ([2], [4]). Nếu đồ thị G có bậc lớn nhất là ∆(G) thì |λ| ≤ ∆(G)
với mọi giá trị riêng λ của G.
Chứng minh. Với ký hiệu ở trên, đặt u là một đỉnh mà |xu | là cực đại. Sử dụng
Phương trình (1.1), chúng ta có:
|xu | ≤ |∆(G)||xu |.

|λ||xu | ≤
v∼u

Vì xu = 0, mệnh đề được chứng minh.
Mệnh đề 1.1.8. ([2], [4]). Đồ thị G là chính quy bậc r nếu và chỉ nếu tất cả
các véc tơ 1 là một véc tơ riêng của G (với giá trị riêng tương ứng r).
Nếu λ là một giá trị riêng của A thì tập {x ∈ Rn : Ax = λx} là một không

√
x3 = (1, 0 − 1, 0, 0, )T , x4 = (1, 1, 1, 1, 1 − 5)T , x5 = (1, −1, 1, −1, 0)T . Chúng
√
√
ta có ε(1 + 5) = x1 , ε(0) = x2 , x3 , ε(1 − 5) = x4 và ε(−2) = x5 ,
trong đó các ngoặc là ký hiệu không gian con sinh bởi mỗi véc tơ trong ngoặc.
Ví dụ 1.1.10. Các giá trị riêng của chu trình có độ dài n là 2 cos 2πj
n (j =
0, 1, . . . , n − 1). Để thấy điều này, ta quan sát rằng một ma trận kề có dạng
A = P + P −1 trong đó P là một ma trận hoán vị xác định bởi một hoán vị
vòng độ dài n. Nếu ω căn bậc n của đơn vị thì (1, ω, ω 2 , . . . , ω n−1 )T là một véc
tơ riêng của P với giá trị riêng tương ứng ω. Vì vậy các giá trị riêng của A là
số ω + ω −1 trong đó ω n = 1. Vì vậy giá trị riêng lớn nhất là 2 (với bội 1) và giá
trị riêng lớn thứ hai là 2 cos 2π
n (với bội 2). Giá trị riêng nhỏ nhất là −2 (với
(n−1)π
bội 1) nếu n là chẵn và 2 cos n (với bội 2) nếu n lẻ.
Ví dụ 1.1.11. Đồ thị Petersen (Hình 1.5) có phổ là 31 , 15 , (−2)4 .

Hình 1.5: Đồ thị Petersen.

Chúng ta nói rằng hai đồ thị là đồng phổ nếu chúng có phổ giống nhau. Rõ
ràng, các đồ thị đẳng cấu là đồng phổ (nói cách khác, phổ là bất biến đồ thị).
Tuy nhiên các đồ thị có phổ giống nhau không nhất thiết là đẳng cấu: các đồ
thị không đẳng cấu trong Hình 1.6(a) có phổ là 21 , 03 , (−2)1 . Đây là ví dụ với
số đỉnh ít nhất. Hình 1.6(b) là đồ thị liên thông không đẳng cấu đồng phổ với
số đỉnh ít nhất: đa thức đặc trưng của chúng là (x−1)(x+1)2 (x3 −x2 −5x+1).
Các đồ thị khác nhau được đặc trưng bởi phổ của chúng hoặc cùng với các bất
biến đại số của chúng.


3,
3,
(9
−
17)
và
các
giá
trị
riêng
Seidel
là
3,
(−1
+
17), −1,
2
2
2
√
−1, 21 (−1 + 17).
Ma trận Seidel có liên quan đặc biệt tới graph switching (thường được gọi
là Seidel switching): cho một tập con U các đỉnh của đồ thị G. Đồ thị GU thu
được từ G như sau. Với u ∈ U, v ∈
/ U các đỉnh u, v kề nhau trong GU nếu và
chỉ nếu chúng không kề trong G. Giả sử rằng G có ma trận kề trong G là
A(G) =

AU B T
B C

hệ tương đương trên đồ thị. Chú ý rằng đồ thị tương đương switching có ma
trận Seidel tương tự và vì vậy có phổ Seidel giống nhau. Xét quan hệ giữa phổ
và phổ Seidel của các đồ thị chính quy, chúng ta có mệnh đề sau:
Mệnh đề 1.1.14. ([2], [4]). Nếu và G và GU là chính quy và cùng bậc thì G
và GU có phổ giống nhau.

1.2

Ma trận kề. Ma trận trọng số

Xét đồ thị vô hướng G = (V, E) với tập đỉnh V = {1, 2, . . . , n} và tập cạnh
E = {e1 , e2 , . . . , em }. Ta gọi ma trận kề của đồ thị G là (0;1) - ma trận
A = {aij : i, j = 1, 2, . . . , n}
với các phần tử được xác định theo quy tắc sau đây
aij = 0, nếu {i, j} ∈
/E
aij = 1, nếu {i, j} ∈ E, i, j = 1, 2, . . . , n.
Ví dụ 1.2.1. Cho đồ thị như hình vẽ:


11

Hình 1.7: Đồ thị vô hướng G và đồ thị có hướng G1

Lời giải.

Ma trận kề của đồ thị vô hướng G là:
1 2 3 4 5 6



1
1

1
1
0
1
0
1



0
0


0
.
1

1
0

Các tính chất của ma trận kề.
1) Rõ ràng ma trận kề của đồ thị vô hướng là đối xứng, tức là
aij = aji ,

i, j = 1, 2, . . . , n.

Ngược lại mỗi (0,1) - ma trận đối xứng cấp n sẽ tương ứng, chính xác đến

4 0

5 0
6 0

1
0
1
0
0
0

1
0
0
0
0
0

0
0
1
0
1
0

0
0
0
0

của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, ta luôn phải
sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó.


13

1.3

Ma trận liên thuộc

Xét G = (V, E), (V = {1, 2, . . . , n}, E = {e1 , e2 , . . . , em }) , là đồ thị có
hướng. Xây dựng ma trận B = (bij , i = 1, 2, . . . , n, j = 1, 2, . . . , m), trong đó

bij =




1

nếu tồn tại {i, j}, i < j



0

nếu không tồn tại {i, j}.

−1


Tính chất của ma trận biểu diễn đồ
thị và các phép toán đồ thị
Trong chương này, tôi trình bày khái niệm ma trận Laplace của đồ thị, ma
trận Laplace của một cạnh, ứng dụng của định lý Kirchhoff về đếm số cây bao
trùm thông qua các giá trị riêng của ma trận Laplace của đồ thị cùng các kết
quả liên quan đếm bài toán đếm, sau cùng là một phép toán trên đồ thị. Tôi
tham khảo từ tài liệu [2], [4] - [6].

2.1

Tính chất của ma trận biểu diễn đồ thị

2.1.1

Ma trận Laplace của đồ thị và một số tính chất cơ bản

Định nghĩa 2.1.1. Cho một đồ thị vô hướng G = (V, E) với tập đỉnh V và
tập hợp cạnh E.
+ Ma trận kề AG = aij của đồ thị G được xác định bởi
aij :=

1

khi {i, j} ∈ E,

0

khi {i, j} ∈
/ E.





1
0
1
0

1
1
0
1



1

0

1
0



3
0

DG = 
0
0

Nhận xét 2.1.3. Nếu một đỉnh i ∈ G là đỉnh cô lập thì hàng và cột tương
ứng của ma trận Laplace đều bằng 0.
[LG ]ij = 0, ∀i
[LG ]ji = 0, ∀j.
Nhận xét 2.1.4. Nếu G và H là hai đồ thị với cùng một tập đỉnh và tập cạnh
rời nhau thì
LG∪H = LG + LH .


16

Bổ đề 2.1.5. ([2], [4]) Ma trận Laplace của hai đồ thị G và H bằng tổng trực
tiếp của LG và LH
LG∪H = LG ⊕ LH =

LG 0
0 LH

.

Chứng minh. Xét đồ thị G ∪ v(H) = (VG ∪ VH , EG ) và định nghĩa tương tự
cho v(G) ∪ H.
Theo Nhận xét 2.1.3 ta có
LG 0
0 LH

LG∪v(H) =

0 0
0 LH

suy ra
LG∪H ∗ (v1 ⊕ 0) =

LG 0
0 LH

v1
0

=

λ1 v1
0

.


17

2.1.2

Ma trận Laplace của một cạnh

Định nghĩa 2.1.7. Cho đồ thị G = (V, E), e ∈ E. Lấy Le là ma trận Laplace
của n đỉnh mà chỉ bao gồm một cạnh là e.
Ví dụ 2.1.8. Cho đồ thị G như hình vẽ với E = {v1 , v2 , . . . , vn }

Hình 2.2: Đồ thị G

Suy ra


1 −1
−1 1

⊕ 0.

Bởi tính cộng tính LG được xác định bởi công thức
Le .

LG =
e∈E

Ví dụ 2.1.9. Cho đồ thị G = (V, E), E = {1, 2, 3, 4}, V = {(1, 2), (1, 3), (1, 4)}
như hình vẽ:


18

Hình 2.3: Đồ thị G

Khi đó



1

−1

L(1,2) = 
0

0
1
0 0





1

0 0

L(1,3) = 
−1 0

1
0

=
0
−1

0
0
0
0



0


−1
1
0
0

0
0
0
0





0
1


0  0
+
0 −1
0
0



3 −1 −1 −1
−1 −1 0 0 




19

Nhận xét 2.1.10. L là nửa xác định dương. Thật vậy
1
√


1 −1 = 2  12 
−√
2





Le =

Vì vậy

1 −1
−1 1

1
−1
√ , √
2
2



x T Le x =

Le x =
e∈E

e∈E

(xi − xj )2 .
i,j∈E

Điều này có nghĩa LG là nửa xác định dương.
2.1.3

Phân tích ma trận Laplace

Nhận xét 2.1.12.
LG = B T · B.
Chứng minh. Giả sử
[B T B]ij = ( cột thứ i của B)( hàng thứ j của B)
(Bij )nj=1 = (Bij )ni=1 .

=
e

Điều này sẽ cho chúng ta ba trường hợp
• Khi i = j
[B T B]ij =

((Bij )nj=1 )2 =

Định lý Kirchhoff

Định lý 2.1.13. ([2], [4]). Giả sử L là một ma trận Laplace của một đơn đồ
thị liên thông G với n đỉnh. Khi đó, số lượng cây bao trùm của G, kí hiệu t(G)
được xác định bởi công thức
1
t(G) =
n

n

λi

hay

tG = Ckk (L)

i=1

với λi là các giá trị riêng không âm của LG (ma trận Laplace của đồ thị G).
Nhận xét 2.1.14. Ta thấy rằng tổng của mọi phần tử trên mỗi hàng của ma
trận Laplace G đều bằng 0. Do đó, vectơ [1, 1, . . . , 1]T là vectơ riêng của L với
giá trị riêng 0. Do đó mọi giá trị riêng của L đều không âm và 0 phải là giá trị
riêng nhỏ nhất của L.
2.1.4.1

Hạng của ma trận con của ma trận liên thuộc B

Chú ý rằng mỗi một cột của ma trận liên thuộc có chính xác một giá trị 1
và một giá trị (-1). Do đó, tổng các thành phần của mỗi cột bằng 0. Tên tổng