Phép chia Euclid: Cho trước 2 số nguyên a và b với b # 0, tồn tại duy nhất 2 số nguyên q (thương số) và r (dư số) sao cho:
a = qb + r, với 0 ≤r < |b|
Khi r = 0, ta nói rằng a chia hết cho b và b là ước số của a, ký hiệu b|a.
16 trang |
Chia sẻ: vietpd | Lượt xem: 1738 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Cơ sở toán học, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
16
Chương 2. CƠ SỞ TOÁN HỌC
2.1. Lý thuyết số học và đại số ma trận
2.1.1. Một số khái niệm cơ bản
Phép chia Euclid: Cho trước 2 số nguyên a và b với b # 0, tồn tại duy nhất 2
số nguyên q (thương số) và r (dư số) sao cho:
a = qb + r, với 0 ≤ r < |b|
Khi r = 0, ta nói rằng a chia hết cho b và b là ước số của a, ký hiệu b|a.
Định nghĩa 2.1: Số nguyên d được gọi là ước số chung của hai số nguyên a và
b nếu d|a và d|b.
Ví dụ 2.1: 2 là ước số chung của 4 và 10.
Định nghĩa 2.2: Số nguyên d ≥ 0 được gọi là ước số chung lớn nhất của hai số
nguyên a và b, ký hiệu d = (a, b) nếu d là ước số chung của a, b và với mọi ước số
chung e của a, b ta đều có e|d.
Ví dụ 2.2: 3 = (6, 9); 6 = (12, 18)
Định nghĩa 2.3: Số nguyên tố là số nguyên dương lớn hơn 1 chỉ chia hết cho 1
và chính nó.
Ví dụ 2.3: 2, 3, 5 là các số nguyên tố.
Định nghĩa 2.4: Các số nguyên a và b được gọi là nguyên tố cùng nhau nếu
(a, b) = 1, ký hiệu là a ⊥ b.
Ví dụ 2.4: 2 ⊥ 5 , 4 ⊥ 9
Định nghĩa 2.5: Nếu a và b là các số nguyên, thì tổ hợp tuyến tính của a và b
là một tổng có dạng ma + nb, trong đó m, n là các số nguyên.
Định lý 2.1: Ước chung lớn nhất của các số nguyên a và b không đồng thời
bằng 0 là số nguyên dương nhỏ nhất biểu diễn được tổ hợp tuyến tính của a và b.
Chứng minh:
Giả sử d là số nguyên dương nhỏ nhất biểu diễn bởi một tổ hợp tuyến tính của
a và b: d = ma + nb, với m, n là các số nguyên.
17
Gọi q, r ∈ Z là phần nguyên và phần dư khi chia a cho d, ta có:
a = qd + r, 0 ≤ r ≤ d
⇒ r = a – qd = a – q(ma + nb) = (1 – qm)a – qnb
Như vậy, r cũng là một tổ hợp tuyến tính của a và b. Vì 0 ≤ r ≤ d, mà d là tổ
hợp tuyến tính dương nhỏ nhất của a và b nên r = 0, tức d|a. Tương tự, d|b.
Giả sử c là một ước chung tùy ý của a và b. Do c|a, c|b, mà d = ma + nb nên
suy ra c|d.
Vậy d là ước chung lớn nhất của a và b ⇒ đfcm!
Hệ quả 2.1: Hai số nguyên a và b nguyên tố cùng nhau khi và chỉ khi tồn tại
các số nguyên m và n sao cho:
ma + nb = 1
Chứng minh:
Giả sử a, b nguyên tố cùng nhau nên (a, b) = 1. Theo Định lý 2.1 tồn tại m, n
là các số nguyên dương sao cho ma + nb = 1.
Ngược lại, giả sử (a, b) = d và tồn tại các số nguyên m, n sao cho ma + nb = 1.
Vì d|a, d|b nên d|(ma + nb) hay d|1 ⇒ d = 1 (vì d là số nguyên dương) tức a ⊥ b
(đfcm!).
Hệ quả 2.2: Giả sử a, b, c là các số nguyên dương, đồng thời (a, b) = 1, a|bc.
Khi đó a|c.
Chứng minh:
Vì (a, b) = 1 nên tồn tại số nguyên dương x, y sao cho ax + by = 1. Nhân hai
vế phương trình này với c, ta có acx + bcy = c. Ta thấy a|(acx + bcy), vì đó là một tổ
hợp tuyến tính của a và bc nên a|c.
2.1.2. Phép chia dư trên mZ
Định nghĩa 2.6: Cho x, y ∈ Z , m ∈ *N , x được gọi là đồng dư của y mod m,
ký hiệu: x ≡ y (mod m)
nếu m là ước của x – y; m được gọi là mô-đun của phép đồng dư.
Tập các số nguyên mod m, ký hiệu mZ , là tập:
18
mZ = {0, 1, 2, … , m – 1}
Nếu x ∈ mZ , số nguyên x mod m của mZ được gọi là rút gọn mod của x theo
m.
Bổ đề 2.1: Cho số nguyên tố p và số nguyên dương m thỏa điều kiện (m, p) =
1. Khi đó ta luôn có:
i) 0 < k. p mod m < m
với ∀ số nguyên dương k ∈ (0, m)
ii) k.p mod m # k’.p mod m
với ∀ số nguyên dương k, k’∈ (0, m) ∧ k # k’
Chứng minh:
i) k. p mod m < m hiển nhiên.
Giả sử: k.p mod m = 0
Vì (p, m) = 1 ⇒ k mod m = 0
Mặt khác k ∈ (0, m) ⇒ k mod m > 0, trái với giả thiết ⇒ đfcm!
ii) Giả sử k.p = a.m + a1, k’.p = a’.m + a2 (1) và ∃ k, k’ ∈ (0, m) và k # k’ sao
cho kp mod m = k’p mod m
Từ (1) suy ra a1 = a2
⇒ k.p – k’.p = a.m – a’.m
⇒ p(k-k’) = m(a-a’)
⇒ m(a-a')k - k' =
p
(2)
Do (m, p) = 1 (gt), từ (2) ⇒ p|(a – a’) (Hệ quả 2.2)
hay a – a’ = t.p , với t ∈ Z (3)
Thế (3) vào (2) ta có: k – k’ = t.m với t ∈ Z
Vì k, k’ ∈ (0, m) nên –m < k- k’ < m
Do đó, k – k’ = t.m xảy ra khi và chỉ khi t = 0
⇒ k = k’ trái với giả thiết ⇒ đfcm!
19
2.1.3. Hàm phi-Euler
Định nghĩa 2.7: Một số nguyên a ∈ mZ được gọi là khả nghịch (mod m) nếu
tồn tại x ∈ mZ : ax ≡ 1 (mod m). Nếu tồn tại số x như thế, thì x là duy nhất, và được
gọi là nghịch đảo của a mod m, ký hiệu a-1 (mod m), hay a-1.
Tập tất cả các phần tử khả nghịch của mZ được ký hiệu
*
mZ .
Ví dụ 2.5: Nghịch đảo của 5 (mod 17), 5-1 (mod 17), là 7.
Thật vậy: 5.7 = 35 ≡ 1 (mod 17)
Định nghĩa 2.8: Cho n ≥ 1, đặt ϕ(n) là số các số nguyên trong khoảng [1, n]
nguyên tố cùng nhau với n. Hàm ϕ như thế được gọi là hàm phi-Euler.
Ví dụ 2.6: ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2
Định lý 2.2: Cho x, y ∈ mZ , m ≥ 2.
a) x ∈ *mZ ⇔ x ⊥ m.
Đặc biệt, khi m là số nguyên tố, thì ∀ x ∈ mZ , x # 0, đều khả nghịch (mod
m), và ϕ(m) = m - 1.
b) x ∈ *mZ ⇒ x-1 ∈ *mZ .
Chứng minh:
a) Với x ∈ *mZ , luôn tồn tại x’∈ *mZ : x.x’ ≡ 1 mod m.
⇒ x.x’ = k.m + 1 với k ∈ Z hay x.x’ - k.m = 1 với k ∈ Z
Vì x.x’ – k.m là tổ hợp tuyến tính của x và m nên suy ra (x, m) = 1 (Hệ quả
2.1).
Ngược lại, nếu (x, m) = 1, tồn tại x’, k ∈ Z : x.x’ + k.m = 1 (Hệ quả 2.1).
⇒ x.x’ ≡ 1 mod m hay x ∈ *mZ .
Tóm lại, x ∈ *mZ ⇔ x ⊥ m.
Khi m là số nguyên tố, ∀ x ∈ mZ , ta có: x ⊥ m ⇔ x # 0
Vậy ϕ(m) = m – 1.
20
b) Nếu x ∈ *mZ , thì luôn tồn tại x’ ∈ *mZ sao cho : x.x’ ≡ 1 mod m. Vì thế:
x = (x’)-1 = (x-1)-1
⇒ x là nghịch đảo của x-1 trong *mZ .
Định lý 2.3: Nếu p, q là hai số nguyên tố khác nhau và n = p.q, thì:
ϕ(n) = (p-1).(q-1)
Chứng minh:
Có tất cả n – 1 số nguyên nhỏ hơn n; trong số đó, (q-1) số là bội của p, 2p, …,
(q-1)p; (p-1) số là bội của q, 2q,.., (p-1)q và đều không nguyên tố cùng nhau với pq.
Do các số nguyên này chỉ trong khoảng [1, n) và không nguyên tố cùng nhau
với n, nên:
ϕ(n) = (pq-1) – (q-1) – (p-1) = pq – q – p + 1 = (p-1)(q-1).
2.1.4. Một số kết quả về đại số ma trận
Định nghĩa 2.9: Cho ma trận vuông A = (aij)m×m trên K ( K =N ,Z , R ). Định
thức của ma trận A là tổng đại số của m! số hạng, mỗi số hạng là tích của m phần tử
lấy trên các hàng và các cột khác nhau của ma trận A, mỗi tích được nhân với phần
tử dấu là +1 hoặc -1 theo phép thế tạo bởi các chỉ số hàng và chỉ số cột của các phần
tử trong tích. Gọi Sm là nhóm các hoán vị của m phần tử 1, 2, ..., m ta có công thức
Leibniz:
)()2(2)1(1 ...)()det( mm
S
i ii
mi
i
aaasA σσ
σ
σσ∑
∈
=
Định lý 2.4: Cho ma trận vuông A = (aij)m×m trên K ( K = N ,Z , R ). Ma trận A
được gọi là ma trận khả nghịch nếu và chỉ nếu det(A) # 0.
Chứng minh:
Giả sử B là ma trận nghịch đảo của A
⇒ A.B = I ⇒ det(A.B) = det(I) ⇒ det(A).det(B) = det(I) = 1
⇒ det(A) # 0.
21
Giả sử det(A) # 0, đặt ma trận
)det(A
AadjB = , trong đó adj A là phần phụ đại số
của ma trận A ⇒ B là ma trận nghịch đảo của A.
Định lý 2.5 [5]: Cho ma trận vuông A = (aij)m×m trên nZ , trong đó n = pq là
tích của 2 số nguyên tố phân biệt nhau, giả sử mỗi hàng và mỗi cột của ma trận A
chỉ có duy nhất một giá trị thuộc *nZ (tức khác 0) và các giá trị còn lại đều bằng 0,
lúc đó với ∀ m ∈ +N ta có det(A) ∈ *nZ .
Chứng minh:
Theo Định nghĩa 2.9 ta có :
)()2(2)1(1 ...)()det( mm
S
i ii
mi
i
aaasA σσ
σ
σσ∑
∈
=
)()2(2)1(11)()2(2)1(11 111111 ...)(...)( mmmm aaasaaas σσσσσσ σσ += +
)()2(2)1(1!)()2(2)1(12 !!!222 ...)(......)( mmmmm mmm aaasaaas σσσσσσ σσ ++
Do mỗi hàng và mỗi cột của ma trận A chỉ có duy nhất một giá trị khác 0,
không mất tính tổng quát giả sử )()2(2)1(1 ,...,, mm ttt aaa σσσ , t ∈ [1, m!] là các
số khác 0 trong ma trận A ( *( )1, 2, .., : ti i ni m a σ∀ = ∈Z ).
Cho nên trong biểu thức tính định thức ma trận chỉ có duy nhất biểu thức
)()2(2)1(1 ... mm ttt aaa σσσ khác 0 (tương ứng với tích của các số khác 0), các biểu
thức khác đều bằng 0, tức :
0#...],m![1,! )()2(2)1(1 mm ttt aaat σσσ∈∃
0... t # j ],m![1, )()2(2)1(1 =⇒∈∀ mm jjj aaaj σσσ
)()2(2)1(1)()2(2)1(1 ...)(...)()det( mmtmm
S
i tttii
mi
i
aaasaaasA σσσσσσ σ
σσ ==⇒ ∑
∈
*
( )Vì 1, 2, .., : ti i ni m a σ∀ = ∈Z nên:
*
1 (1) 2 (2) ( )det( ) mod ( ) ... modt t tt m m nA n s a a a n uσ σ σσ= = ∈Z
22
Ví dụ 2.7: Cho n = p × q = 3 × 5 = 15
⇒ Z15 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
và *15Z = {1, 2, 4, 7, 8, 11, 13, 14}
Ma trận A = (aij)3×3 =
11 12 13
21 22 23
31 32 33
0 8 0
0 0 7
2 0 0
a a a
a a a
a a a
⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥=⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦⎣ ⎦
⇒ Tập S3 có 3! = 6 phần tử, đó là:
1 2 3 1 2 3 1 2 3
, ,
1 2 3 3 1 2 2 3 1
⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
1 2 3 1 2 3 1 2 3
, ,
2 1 3 3 2 1 1 3 2
⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
3
1 (1) 2 (2) (3)det( ) ( ) i i i
i
i m
S
A s a a aσ σ σ
σ
σ
∈
⇒ = ∑ = a11a22a33 +a13a21a32 + a12a23a31
– a12a21a33 – a13a22a31 – a11a23a32 = 0×0×0 + 0×0×0 + 8×7×2 - 8×0×0 -
0×0×2 - 0×7×0 = 112
⇒ det(A) mod 15 = 112 mod 15 = 7 ∈ *15Z
Hệ quả 2.3: Cho ma trận vuông A = (aij)m×m trên nZ , trong đó n = pq là tích
của 2 số nguyên tố phân biệt nhau, giả sử mỗi hàng và mỗi cột của ma trận A chỉ có
duy nhất một giá trị thuộc *nZ (tức khác 0) và các giá trị còn lại đều bằng 0, lúc đó
với ∀ m ∈ +N thì A là ma trận khả nghịch.
Chứng minh:
Theo Định lý 2.5 ta có det(A) ∈ *nZ ⇒ det(A) # 0
Từ Định lý 2.4 suy ra A là ma trận khả nghịch.
Ví dụ 2.8: Cho ma trận A như ở Ví dụ 2.7
A = (aij)3×3 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
333231
232221
131211
aaa
aaa
aaa
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
002
700
080
23
Ma trận nghịch đảo của ma trận A trên trường nZ = 15Z là:
A-1 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
0130
002
800
Định lý 2.6 [5]: Cho n = pq là tích của hai số nguyên tố phân biệt nhau và ma
trận vuông A = (aij)m×m , B = (bij)m×m = ((aij)k mod n)m×m (k ∈ ( )nϕZ ) trên nZ . Giả
sử mỗi hàng, mỗi cột của ma trận A có duy nhất một giá trị thuộc *nZ (tức khác 0)
và các giá trị còn lại đều bằng 0 thì ma trận B sẽ là ma trận khả nghịch.
Chứng minh:
Theo giả thiết: ∀i, j ∈ [1, m], bij = (aij)k mod n (k ∈ ( )nϕZ )
- Giả sử aij ∈ *nZ ⇒ (aij)k mod n = (aij × aij ×... × aij) mod n = u ∈ *nZ
⇒ bij = (aij)k mod n ∈ *nZ (1)
- Giả sử aij = 0 ⇒ (aij)k = (0)k = 0
⇒ bij = (aij)k mod n = 0 (2)
Từ (1) và (2) ta có:
- Nếu aij ∈ *nZ thì bij = (aij)k mod n ∈ *nZ
- Nếu aij = 0 thì bij = (aij)k mod n = 0
Do đó, nếu mỗi hàng và mỗi cột của ma trận A = (aij)n×n có duy nhất một giá
trị thuộc *nZ thì mỗi hàng và mỗi cột của ma trận B = (bij)n×n = ((aij)
k mod n)n×n (k ∈
( )nϕZ ) cũng có duy nhất một giá trị thuộc *nZ .
Theo Định lý 2.5 và Hệ quả 2.3 ta có đfcm!
Ví dụ 2.9: Cho ma trận A như Ví dụ 2.7:
A = (aij)3×3 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
333231
232221
131211
aaa
aaa
aaa
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
002
700
080
24
với k = 3 ∈ ϕ(n) = ϕ(15) = {0, 1, 2, 3, 4, 5, 6, 7}, ta có:
B = (bij)3×3 = ((aij)k mod n)3×3
B =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
008
1300
020
thì ma trận nghịch đảo của B trên nZ = 15Z là:
B-1 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
070
008
200
Định lý 2.7 [5]: Cho ma trận vuông A = (aij)m×m trên nZ , với n = pq là tích của
hai số nguyên tố phân biệt nhau. Giả sử mỗi hàng và mỗi cột của ma trận A chỉ có
duy nhất một giá trị thuộc *nZ , các giá trị còn lại đều bằng 0; và nghịch đảo của ma
trận A, ký hiệu: A-1 = (a’ij)m×m thì ta luôn có:
0 , aji = 0 a’ij = 0, aji = 0
((aji)-1)mod n , aji ∈ *nZ (a’ij × aji) ≡ 1 (mod n), aji ∈ *nZ
Chứng minh:
Đặt B = (bij)m×m = A × A-1
∑
=
×++×+×=×=⇒ m
t
mjimjijitjitij aaaaaaaab
1
2211 '...'''
Giả sử ∃ t ∈ [1, m]: ait ∈ *nZ
ait × a’ti ≡ 1 (mod n)
∀ u # t ∈ [1,m], aiu = a’ui = 0
a’ti ∈ Z*n
∀ i # j ∈ [1,m], a’tj = 0
- Trường hợp 1: i = j
+×+×++×+×==⇒ −− tiitittiiiiiiiij aaaaaaaabb ''...'' )1()1(2211
a’ij = ⇔
⇒ (3)
25
+ miimitti aaaa '...' )1()1( ×++× ++
Từ (3) suy ra:
tiittiitii aaaab '00...00'00...0000 ×=×++×+×+×++×+×=
mod ' mod 1 (*)ii it tib n a a n⇒ = × =
- Trường hợp 2: i # j
+×+×++×+×==⇒ −− tiitittiiiiiiiij aaaaaaaabb ''...'' )1()1(2211
( 1) ( 1)' ... 'i t t i im mia a a a+ ++ × + + ×
Từ (3) suy ra:
00...00'00...0000 ×++×+×+×++×+×= tiitii aab
00' =×=×= ittiit aaa
mod 0 mod 0 (**)iib n n⇒ = =
Từ (*) và (**) ta có:
0, i # j
1, i = j
⇒ B mod n = (A × A-1) mod n = Im×m
Tương tự, đặt C = (cij)m×m = A-1 × A, chúng ta cũng có:
C mod n = (A-1 × A) mod n = Im×m
Do đó, (A × A-1) mod n = (A-1 × A) mod n = Im×m ⇒ đfcm!
Ví dụ 2.10: Cho ma trận như ở Ví dụ 2.7
A = (aij)3×3 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
333231
232221
131211
aaa
aaa
aaa
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
002
700
080
Gọi A-1 là ma trận nghịch đảo của A trên nZ = 15Z :
A-1 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
333231
232221
131211
'''
'''
'''
aaa
aaa
aaa
Theo Định lý 2.7 ta có:
bij mod n =
26
a11 = 0 ⇒ a’11 = 0; a13 = 0 ⇒ a’31 = 0
a21 = 0 ⇒ a’12 = 0; a22 = 0 ⇒ a’22 = 0
a32 = 0 ⇒ a’23 = 0; a33 = 0 ⇒ a’33 = 0
a12 = 8 ∈ Z*15 ⇒ a’21 = (a12)-1 mod n = 8-1 mod 15 = 2
tương tự: a32 = 7-1 mod 15 = 13; a13 = 2-1 mod 15 = 8
Vậy:
A-1 =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
333231
232221
131211
'''
'''
'''
aaa
aaa
aaa
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
0130
002
800
Kết quả này giống với nghịch đảo của ma trận B ở Ví dụ 2.8
2.2. Lý thuyết đồ thị
2.2.1. Định nghĩa đồ thị
Đồ thị (graph) là một mô hình toán học được ứng dụng trong nhiều lĩnh vực
khoa học, kỹ thuật và được định nghĩa như sau:
Định nghĩa 2.10: Đồ thị là một cặp G = (V, E), trong đó:
i) V là tập hợp các đỉnh (vertex),
ii) E ⊆ V × V là tập hợp các cạnh (edge).
Ví dụ 2.11:
Đồ thị G = (V, E) cho ở hình vẽ trên có tập đỉnh V = {a, b, c, d, e}, tập cạnh E
= {(a, b), (a, d), (b, e), (c, a), (c, b), (d, b), (d, c), (d, e), (e, a)}.
a
e
d
b
c
27
Về bản chất, đồ thị là một tập hợp các đối tượng được biểu diễn bằng các đỉnh
và giữa các đối tượng này có một quan hệ hai ngôi biểu diễn bằng các cạnh.
Nếu (a, b) là một cạnh của đồ thị thì ta nói rằng đỉnh b kề với đỉnh a và cả hai
đỉnh a và b kề với cạnh (a, b). Hai cạnh có ít nhất một đỉnh chung được gọi là hai
cạnh kề nhau.
Trong Ví dụ 2.11, hai đỉnh a và b kề với đỉnh c; ba đỉnh b, c và e kề với đỉnh
d. Do vậy, ta có thể định nghĩa đồ thị bằng ánh xạ kề như sau.
Định nghĩa 2.11: Đồ thị là một cặp G = (V, F), trong đó:
i) V là tập hợp các đỉnh,
ii) F : V → 2V , được gọi là ánh xạ kề.
Ánh xạ kề của đồ thị trong Ví dụ 2.1 được xác định như sau:
F(a) = {b, d}, F(b) = {e}, F(c) = {a, b}, F(d) = {b, c, e}, F(e) = {a}
Hai định nghĩa của đồ thị là tương đương theo mệnh đề sau:
∀ u, v ∈ V : (u, v) ∈ E ⇔ v ∈ F(u).
Cặp đỉnh (u, v) ∈ E không quan tâm đến thứ tự được gọi là cạnh vô hướng,
còn nếu thứ tự là quan trọng thì được gọi là cạnh có hướng. Vì thế, người ta thường
phân các đồ thị thành hai lớp: đồ thị có hướng và đồ thị vô hướng như định nghĩa
sau.
Định nghĩa 2.12: Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị vô
hướng, còn đồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có hướng.
Hiển nhiên, mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng
bằng cách thay mỗi cạnh vô hướng bằng hai cạnh có hướng tương ứng.
2.2.2. Đường đi và chu trình Hamilton
Cho G = (V, E) là một đồ thị.
Định nghĩa 2.13: Đường đi là một dãy các đỉnh:
sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó
bằng một cạnh nào đó, nghĩa là: ∀ i = 2, 3, ... , k-1, k : (xi-1, xi) ∈ E.
28
Ta nói rằng đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk. Số cạnh của
đường đi được gọi là độ dài của đường đi đó.
Đường đi được gọi là đường đi đơn (đường đi sơ cấp) nếu các đỉnh trên nó đôi
một khác nhau.
Định nghĩa 2.14: Chu trình là một đường đi khép kín (tức đỉnh cuối và đỉnh
đầu của đường đi trùng nhau). Ta thường ký hiệu chu trình là:
[x1, x2, ... , xi, xi+1, ... xk-1, xk] , trong đó x1 = xk
Chu trình được gọi là chu trình đơn (chu trình sơ cấp) nếu các đỉnh trên nó đôi
một khác nhau.
Định nghĩa 2.15: Chu trình α trong đồ thị G = (V, E) được gọi là chu trình
Hamilton, nếu nó đi qua tất cả các đỉnh của G, mỗi đỉnh đúng một lần. Nói cách
khác, chu trình Hamilton là một chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị.
Đồ thị G = (V, E) được gọi là đồ thị Hamilton, nếu nó có chu trình Hamilton.
Ví dụ 2.12
[4, hình 14.1]
Đồ thị Hamilton (hình thập nhị diện đều biểu diễn trong mặt phẳng) với chu
trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường
tô đậm).
C
B D
A E
J
L H
T
K I
O P
F
M G
S
R
N Q
29
Định nghĩa 2.16: Đường β trong đồ thị G = (V, E) được gọi là đường
Hamilton, nếu nó đi qua tất cả các đỉnh của G, mỗi đỉnh đúng một lần. Nói cách
khác, đường Hamilton là một đường sơ cấp đi qua tất cả các đỉnh của đồ thị.
Đồ thị G = (V, E) được gọi là đồ thị nửa Hamilton, nếu nó có đường
Hamilton.
Hiển nhiên, nếu G có chu trình Hamilton thì G cũng có đường Hamilton. Thật
vậy, ta chỉ cần hủy đi một cạnh trong chu trình Hamilton thì sẽ nhận được đường đi
Hamilton. Điều ngược lại không đúng: có những đồ thị có đường Hamilton nhưng
không có chu trình Hamilton.
2.2.3. Đồ thị đủ có hướng
- Định nghĩa 2.17: Đồ thị đủ có hướng m đỉnh, ký hiệu Km, là đồ thị mà mỗi
cặp đỉnh phân biệt bất kỳ của nó luôn có một đường đi có hướng.
Như vậy, Km có m(m-1) cạnh và mỗi đỉnh của Km có bậc vào (bậc ra) là m−1.
Ví dụ 2.13:
Đồ thị đủ có hướng K3
Định lý 2.8 : Nếu Km là một đồ thị đủ có hướng thì Km là đồ thị Hamilton.
Chứng minh:
Giả sử Km = (V, E) là đồ thị đủ có hướng và α = là đường đi
sơ cấp bất kỳ trong đồ thị Km.
- Nếu α đã đi qua tất cả các đỉnh của Km thì nó là một đường đi Hamilton của
Km.
- Nếu trong Km còn có đỉnh nằm ngoài α, thì ta có thể bổ sung dần các đỉnh
này vào α và cuối cùng nhận được đường đi Hamilton.
Thật vậy, giả sử v là đỉnh tuỳ ý không nằm trên α.
v1
v2v3
30
a) Nếu có cạnh nối v với v1 thì bổ sung v vào đầu của đường đi α để được α1 =
.
b) Nếu tồn tại chỉ số i (1 ≤ i ≤ k-1) mà từ vi có cung nối tới v và từ v có cung
nối tới vi+1 thì ta chen v vào giữa vi và vi+1 để được đường đi sơ cấp α2 = <v1, v2, ...,
vi, v, vi+1, ..., vk>.
c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1 ≤ i ≤ k) vi
đều có cung đi tới v. Khi đó bổ sung v vào cuối của đường đi α và được đường đi
α3 = .
Nếu đồ thị Km có m đỉnh thì sau m - k bổ sung ta sẽ nhận được đường đi
Hamilton.
Vì luôn có đường đi giữa hai đỉnh phân biệt bất kỳ trong Km nên thêm đỉnh
cuối cùng trong đường đi α là đỉnh đầu tiên ta sẽ được chu trình Hamilton.
Định lý 2.9: Đồ thị đủ có hướng Km có đúng m! chu trình Hamilton phân biệt.
Chứng minh:
Giả sử Km = (V, E), với V = {v1, v2,..., vm-1, vm}, |V| = m
Gọi
1 2 1
{ , ,..., , }
m m
v v v vα α α αα −= là một hoán vị của V với αi ∈ [1, m] và αi #
αj , ∀i, j ∈ [1, m] ∧ i # j.
Vì giữa 2 đỉnh bất kỳ của đồ thị đủ có hướng Km luôn có một đường đi nên α
sẽ là 1 đường đi sơ cấp trong Km. Thêm đỉnh cuối cùng là đỉnh đầu tiên trong đường
đi, ta có α là một chu trình Hamilton.
Do tập V có m! các hoán vị khác nhau nên đồ thị Km sẽ có m! chu trình
Hamilton khác nhau (đfcm!).
Bổ đề 2.2: Cho đồ thị đủ có hướng Km = (V, E), với:
+ V = {v1, v2, …, vm} = {1, 2, … , m} là tập đỉnh của đồ thị, |V| = m, m > 1
+ E là tập cạnh, được biểu diễn bởi ma trận kề Am×m = (aij)m×m , aij ∈ *nZ , n =
p.q là tích của 2 số nguyên tố phân biệt nhau, và:
aij = 0 nếu không có cạnh (vi, vj)
aij ≠ 0 nếu có cạnh (vi, vj)
∀ i, j ∈ [1, m]
31
Gọi CH = [c1, c2, ..., ci-1, ci,..., cm, c1] trong đó ci # cj với ∀i, j ∈ [1, m] ∧ i # j là
một chu trình Hamilton trong Km, được biểu diễn bằng ma trận kề Bm×m = (bij)m×m,
với:
bij = 0 nếu (i, j) ∉ CH
bij ≠ 0 nếu (i, j) ∈ CH
Khi đó, mỗi hàng và mỗi cột của ma trận B chỉ có duy nhất một giá trị thuộc
*
nZ (tức khác 0), các giá trị còn lại đều bằng 0.
Chứng minh:
Gọi Bm×m là ma trận biểu diễn chu trình Hamilton CH trong đồ thị đủ có hướng
Km. Do aij ∈ *nZ với ∀i, j ∈[1, m] và mỗi đỉnh trong CH chỉ có duy nhất một đường
đi đến một trong các đỉnh còn lại nên mỗi hàng của ma trận Bm×m chỉ có duy nhất
một giá trị thuộc *nZ (tức khác 0), các giá trị còn lại đều bằng 0. Tương tự, ta cũng
có mỗi cột của ma trận Bm×m chỉ có