Luận văn Nghiên cứu và xây dựng các mô hình chứng thực dựa trên các bài toán khó của lý thuyết đồ thị

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ó