Đăng ký Đăng nhập
Trang chủ Giải pháp lưu vết và thu hồi thiết bị thu bất hợp pháp...

Tài liệu Giải pháp lưu vết và thu hồi thiết bị thu bất hợp pháp

.PDF
120
98
101

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Ngọc Mai Giải pháp lưu vết và thu hồi thiết bị thu bất hợp pháp LUẬN VĂN THẠC SĨ Hà Nội - 2007 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Ngọc Mai Giải pháp lưu vết và thu hồi thiết bị thu bất hợp pháp LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Trịnh Nhật Tiến Hà Nội - 2007 1 MỤC LỤC MỤC LỤC ...................................................................................................................1 DANH MỤC CÁC HÌNH VẼ.....................................................................................4 MỞ ĐẦU .....................................................................................................................5 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN ....................................................................7 1.1 MỘT SỐ KHÁI NIỆM ......................................................................................7 1.2 KHUNG PHỦ TẬP CON ..................................................................................9 1.3 GIẢI PHÁP LƢU VẾT TBTDL LÀM RÕ RỈ KHÓA ...................................12 1.4 GIẢI PHÁP THU HỒI THIẾT BỊ THU BẤT HỢP PHÁP ............................13 1.5 MỘT SỐ CÔNG CỤ .......................................................................................14 1.5.1 Đồ thị ........................................................................................................14 1.5.2 Cây nhị phân .............................................................................................15 1.5.3 Cây Steiner ................................................................................................20 Chƣơng 2: GIẢI PHÁP LƢU VẾT TBTDL LÀM RÕ RỈ KHÓA ...........................21 2.1 KHÁI NIỆM LƢU VẾT TBTDL LÀM RÕ RỈ KHÓA..................................21 2.2 GIẢI THUẬT LƢU VẾT SỬ DỤNG TẬP CON ...........................................24 2.2.1 Giải thuật lƣu vết sử dụng tập con (Subset Tracing) ................................24 2.2.2 Hàm tìm tập con chứa TBTDL làm rò rỉ khóa .........................................28 2.3 LƢU VẾT VỚI NHIỀU BỘ KHÓA NHÁI ....................................................33 2.4 VÍ DỤ VỀ GIẢI THUẬT LƢU VẾT .............................................................34 Chƣơng 3: GIẢI PHÁP THU HỒI TBTDL BẤT HỢP PHÁP ................................56 3.1 MỘT SỐ KHÁI NIỆM ....................................................................................56 3.2 GIẢI THUẬT CÂY NHỊ PHÂN CON ĐẦY ĐỦ (Complete Subtree) ..........59 3.2.1 Ví dụ về giải thuật CS ...............................................................................59 3.2.2 Giải thuật CS .............................................................................................63 3.2.3 Hiệu năng của giải thuật CS .....................................................................65 2 3.3 GIẢI THUẬT HIỆU HAI TẬP CON (Subset Difference) .............................67 3.3.1 Bộ sinh số ngẫu nhiên G ...........................................................................68 3.3.1 Ví dụ về giải thuật SD ..............................................................................70 3.3.2 Giải thuật SD ............................................................................................78 3.3.3 Hiệu năng của giải thuật SD .....................................................................83 3.4 SO SÁNH GIẢI THUẬT CS VÀ SD .............................................................84 Chƣơng 4: ĐỘ AN TOÀN CỦA GIẢI THUẬT KHUNG PHỦ TẬP CON ............85 4.1 CÀI ĐẶT GIẢI THUẬT E MÃ HÓA KHÓA PHIÊN K ...............................86 4.1.1 Phƣơng pháp “Cắt phần đầu bản mã” (Prefix Truncation) .......................86 4.1.2 Phƣơng pháp mã hóa khóa công khai cho E .............................................87 4.2 CÀI ĐẶT GIẢI THUẬT F MÃ HÓA BẢN TIN M .......................................97 4.3 ĐỘ AN TOÀN CỦA GIẢI THUẬT SCF .......................................................99 4.3.1 Độ an toàn của giải thuật E, F và giải thuật thiết lập khóa. ......................99 4.3.2 Khái niệm độ an toàn của giải thuật SCF ...............................................104 Chƣơng 5: MỘT SỐ ỨNG DỤNG .........................................................................110 5.1.1 Khái niệm truyền hình Internet (Internet Protocol Television - IPTV) ..110 5.1.2 Sơ đồ kiến trúc mạng IPTV ....................................................................113 5.2 TRUYỀN HÌNH DI ĐỘNG ..........................................................................115 5.2.1 Khái niệm truyền hình di động (Mobile Television- MobileTV)...........115 5.2.2 Sơ đồ kiến trúc mạng MobileTV ............................................................115 5.2.4 So sánh truyền hình di động và truyền hình kỹ thuật số mặt đất ............117 KẾT LUẬN .............................................................................................................118 TÀI LIỆU THAM KHẢO .......................................................................................119 4 DANH MỤC CÁC HÌNH VẼ Hình 1. 1: Đồ thị G ....................................................................................................14 Hình 1. 2: Cây nhị phân ............................................................................................16 Hình 1. 3: Cây nhị phân đầy đủ.................................................................................17 Hình 1. 4: Cha chung thấp nhất của a và b ...............................................................17 Hình 1. 5: Minh họa thuộc tính rẽ nhánh ..................................................................19 Hình 1. 6: Cây Steiner của 3 nút (a,b,c) ....................................................................20 Hình 2. 1: Cây nhị phân T biểu diễn n TBTDL .......................................................22 Hình 2. 2: Mô hình lưu vết TBTDL làm rò rỉ khóa “dài” .........................................23 Hình 2. 3: Cây nhị phân T biểu diễn 8 TBTDL ........................................................34 Hình 3. 1: Mô hình thu hồi TBTDL bất hợp pháp ....................................................56 Hình 3. 2: Cây nhị phân biểu diễn 8 TBTDL............................................................58 Hình 3. 3: Minh họa giải thuật CS với P={ u1 , u 3 , u 5 , u 6 }, R={ u 2 , u 4 , u 7 , u 8 } .......59 Hình 3. 4: Cây Steiner ST({ u 2 , u 4 , u 7 , u 8 }) và các nút kề nó. .................................61 Hình 3. 5: Cây nhị phân T biểu diễn n TBTDL ........................................................63 Hình 3. 6: Si,j chứa các lá của cây gốc vi , nhưng không thuộc cây gốc vj ...............67 Hình 3. 7: Bộ sinh số ngẫu nhiên G với mầm sinh Labeli ........................................68 Hình 3. 8: Tính L1,5 dựa vào Label1..........................................................................69 Hình 3. 9: Minh họa phân hoạch P thành các tập con của giải thuật SD ..................70 Hình 3. 10: Cây T biểu diễn toàn bộ 8 TBTDL ........................................................71 Hình 3. 11: Minh họa cây ST(u3) và các nút KeV(ST(u3)) .......................................72 Hình 3. 12: Cây Steiner ST(R) với R={v9, v11, v14, v15}...........................................74 Hình 3. 13 Cây Steiner ST(R) với R={v14, v15, v2} ..................................................75 Hình 3. 14: Cây Steiner ST(R) với R={v2, v7} .........................................................76 Hình 3. 15: Cây T biểu diễn toàn bộ n TBTDL ........................................................78 Hình 3. 16: Minh họa cây ST(u) và các nút KeV(ST(u)) .........................................79 Hình 4. 1: Cây nhị phân T và các định danh tương ứng các nút ...............................91 Hình 4. 2: Cây nhị phân T và cách tính định dang theo HIBE .................................94 Hình 5. 1: Sơ đồ mạng IPTV ............................................................................................. 113 Hình 5. 2: Sơ đồ mạng MobileTV ..................................................................................... 115 5 MỞ ĐẦU Hiện nay vấn đề bảo vệ bản quyền đang là vấn đề nhức nhối của Việt Nam cũng như trên thế giới. Vấn đề bảo vệ bản quyền với các tác phẩm công nghệ số là vấn đề mà luật bản quyền phải đương đầu do: công nghệ số tạo khả năng cho việc truyền phát và sử dụng tất cả các đối tượng bảo hộ của bản quyền và quyền kế cận dưới dạng số dễ dàng. Quy trình số hóa cho phép biến đổi các tác phẩm này thành dạng nhị phân, khiến cho chúng dễ dàng được truyền qua mạng Internet và sau đó được phân phối, sao chép, và cất giữ một cách hoàn hảo dưới dạng số. Các thách thức trên diễn ra đối với ngành công nghiệp bản quyền, khi mà số tiền thu được từ bản quyền trong nền kinh tế quốc dân đang đạt tới mức khó dự đoán trước. Giá trị kinh tế của riêng ngành công nghiệp bản quyền tại Mỹ ước tính đạt 91,2 tỷ đô la Mỹ (theo thông tin từ Liên minh Sở hữu trí tuệ thế giới (IIPA)) chiếm tới 5,24% tổng sản phẩm quốc nội của Mỹ, tăng nhanh gấp 2 lần phần còn lại của nền kinh tế. Giá trị của ngành công nghiệp bản quyền chiếm 6% giá trị tăng thêm của nền kinh tế Uruguay vào năm 1997, chiếm 6,7% giá trị tăng thêm của nền kinh tế Braxin vào năm 1998, thu hút 1.3 triệu việc làm tại quốc gia này. Tại Việt Nam, tỷ lệ vi phạm bản quyền đối với các tác phẩm nghe nhìn rất nghiêm trọng gây tổn thất cho nền kinh tế, gây khó khăn trong quá trình hội nhập với thế giới. Chính vì vậy, việc tìm kiếm các giải pháp kỹ thuật và luật pháp để bảo hộ bản quyền khỏi sự sao chép “số” bất hợp pháp là vô cùng cấp thiết. Nhiệm vụ của luận văn này là trình bày các giải pháp kỹ thuật về lưu vết và thu hồi các thiết bị thu bất hợp pháp, nhằm bảo vệ bản quyền, bảo vệ nội dung của các tác phẩm được truyền phát qua các kênh quảng bá (broadcast channels). 6 LUẬN VĂN GỒM CÁC NỘI DUNG SAU: MỞ ĐẦU Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN Giới thiệu các khái niệm cơ bản sử dụng trong luận văn. Chương này cũng nêu lên các thành phần cơ bản của một hệ thống phát dữ liệu quảng bá. Chƣơng 2: GIẢI PHÁP LƢU VẾT THIẾT BỊ THU LÀM RÕ RỈ KHÓA Chương này trình bày giải pháp lưu vết thiết bị thu làm rò rỉ khóa bí mật, sử dụng phương pháp phân hoạch tập TBTDL thành các tập con. Chƣơng 3: GIẢI PHÁP THU HỒI THIẾT BỊ THU BẤT HỢP PHÁP Trình bày giải pháp thu hồi thiết bị thu bất hợp pháp sử dụng khung phủ tập con (Subset Cover Framework). Sau đó sẽ trình bày các giải pháp áp dụng khung phủ tập con là: Cây nhị phân đầy đủ (Complete Subtree), Hiệu hai tập con (Subset Difference). Chƣơng 4: ĐỘ AN TOÀN CỦA KHUNG PHỦ TẬP CON Chƣơng 5: MỘT SỐ ỨNG DỤNG KẾT LUẬN 7 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN 1.1 MỘT SỐ KHÁI NIỆM  Trung tâm quảng bá (Center, Broadcast Center), nhà cung cấp dữ liệu (NCCDL – Data Provider) [6]: Trung tâm có các kênh phát thông tin quảng bá tới các thiết bị thu dữ liệu.  Thiết bị thu dữ liệu (TBTDL - User) [3]: thu dữ liệu phát ra từ NCCDL và dùng các khóa bí mật của nó để giải mã dữ liệu thu được.  Thông điệp hay bản tin (Message) [6]: là thông tin hoặc đoạn thông tin được NCCDL gửi đến TBTDL qua các kênh quảng bá.  Khóa thời gian tồn tại ít (short-lived key - session key) [3]: là khóa được duy trì trong một phiên truyền dữ liệu gọi tắt là khóa phiên.  Khóa thời gian tồn tại dài (long-lived key) [3]: là khóa tồn tại trong thời gian dài của hệ thống, gọi tắt là khóa thời gian dài hay khóa “dài”.  Bộ khóa nhái [2]: Là bộ khóa mà kẻ gian đã thu được từ tập khóa của một số TBTDL (bằng phương pháp nào đó, ví dụ thám khóa).  Thiết bị thu bất hợp pháp (Traitor) [2]: là TBTDL làm rò rỉ khóa hoặc TBTDL sử dụng bộ khóa nhái để giải mã bản tin nhận được từ NCCDL.  Truyền tin quảng bá (Broadcast, Transmistion) [6]: quá trình NCCDL phát định kỳ thông điệp đã mã hóa tới TBTDL.  Giải pháp lưu vết TBTDL làm rò rỉ khóa (Tracing Traitor) [2]: xác định định danh TBTDL làm rò rỉ khóa.  Giải pháp thu hồi TBTDL bất hợp pháp (Revocation Traitor) [3]: là giải pháp phân hoạch các TBTDL hợp pháp thành các tập con, dựa vào đó NCCDL mã hóa thông điệp, để TBTDL bất hợp pháp không giải mã chính xác thông điệp NCCDL phát quảng bá. 8 Các ký hiệu dùng trong luận văn:  N: tập tất cả các TBTDL do NCCDL quản lý, |N|= n.  u1 ,..., u n : ký hiệu các TBTDL thuộc N.  R: tập các TBTDL làm rò rỉ khóa, |R|= r.  P: tập các TBTDL hợp pháp, P=N - R.  K: khóa phiên (session key hay short-lived key).  L: khóa “dài” (long-lived key).  M: thông điệp hay bản tin.  CM: bản mã của thông điệp M.  tM: bản tin thử nghiệm (test message).  L ui : tập các khóa “dài” của TBTDL u i , i=1, 2,…, n.  | L ui |: số lượng các khóa “dài” của TBTDL u i .  Si : tập các TBTDL dùng chung một khóa “dài” L i .  Si, j  Si  S j : chứa các TBTDL thuộc phần bù của tập Si so với tập S j . Các TBTDL trong tập Si, j dùng chung khóa “dài” L i, j . Định nghĩa phủ [6] Cho một họ các tập con khác rỗng S  {S1 , S2 ,..., Sw }, S j  N, j  1,..., w . Cho tập khác rỗng P  N ; phủ của tập P là tập Si1 , Si2 ,..Sit , {i1, i 2 ,...i t }  {1,..., w} và thỏa mãn điều kiện: t P   Si j , j1 Si j  Sik  ,  i j  ik Kích thước của một phủ là số lượng các tập con tạo nên phủ đó. Ví dụ ở đây, kích thước của phủ P là t. 9 1.2 KHUNG PHỦ TẬP CON Phần này giới thiệu khung phủ tập con (Subset Cover Framework - SCF) được sử dụng trong giải thuật lưu vết và giải thuật thu hồi TBTDL bất hợp pháp [3]. w Trong SCF, có giải thuật xác định các tập con S1 , S2 ,..., Sw  N ,  Si  N . i 1 Mỗi tập Si có khóa “dài” L i . Tập P phải được phân hoạch thành các tập con rời rạc Si1 , Si2 ,..., Sim sao cho: m P   Si j . j1 Các khóa “dài” tương ứng với các tập Si1 , Si2 ,..., Sim là Li1 , Li2 ,..., Lim . Lưu ý: Các TBTDL u  Si j sử dụng chung khóa “dài” L i j , j=1, 2,…, m Mỗi u  Si đều tính được L i từ tập khóa L u của mình. SCF sử dụng hai giải thuật mã hóa E và F:  Giải thuật E : {0,1}*  {0,1}* , mã hóa khóa phiên K, lần lượt với từng khóa “dài” Li1 , Li2 ,..., Lim , nhận được các bản mã: E(K, Li1 ), E(K, Li2 ), …, E(K, Lim ) .  Giải thuật F : {0,1}*  {0,1}* , mã hóa thông điệp M sử dụng khóa phiên K, nhận được bản mã: FK (M) . 10 SCF gồm ba phần [3]: 1) Khởi tạo w  NCCDL có giải thuật xác định các tập con S1 , S2 ,...,Sw  N ,  Si  N . Mỗi tập i 1 Si có khóa “dài” L i . L i có thể là: + Hoặc là số độc lập, ngẫu nhiên: L i = G. + Hoặc là hàm của số độc lập, ngẫu nhiên: L i = f(G). Trong đó G là số được sinh từ bộ sinh số ngẫu nhiên.  Mỗi TBTDL u  Si được NCCDL cấp một tập các khóa “dài” Lu. L u có thể là: + Hoặc là L u  {Li } , 1  i  w . + Hoặc là L u  {f (Li )} , 1  i  w , f là ánh xạ 1-1. 2) Mã hóa: Thực hiện tại NCCDL  NCCDL chọn khóa phiên K ngẫu nhiên.  NCCDL phân hoạch P thành các tập con rời rạc Si1 , Si2 ,..., Sim . Li1 , Li2 ,..., Lim là các khóa “dài” tương ứng với các tập con đó.  NCCDL mã hóa khóa phiên K, một lần với từng khóa Li1 , Li2 ,..., Lim và phát quảng bá bản mã:  [i1 , i 2 ,..., i m , E(K, Li1 ), E(K, Li2 ),..., E(K, Lim )], FK (M)  Phần trong dấu [ ] gọi là phần đầu (header), FK(M) gọi là phần thân (body). 11 3) Giải mã: Thực hiện tại TBTDL u.  TBTDL u nhận được bản mã:  [i1 , i 2 ,..., i m , Ci1 , Ci2 ,.., Cim ], M'  m  u tìm i j sao cho u  Si j , trong đó tập các TBTDL hợp pháp là P   Si j . j1 Nếu u  R thì không tìm được i j .  u tính khóa L i j từ tập khóa Lu.  Giải mã D Li (Ci j ) để thu được K, j  1,2,..., m . j  Giải mã D K (M' ) để thu được M. 12 1.3 GIẢI PHÁP LƢU VẾT TBTDL LÀM RÕ RỈ KHÓA a. Bài toán lƣu vết NCCDL truyền thông điệp M qua các kênh quảng bá tới tập N gồm các TBTDL (|N|=n). Mỗi TBTDL u i có một tập khóa “dài” (bí mật) L ui (i=1, 2,…, n). Trong tập N có tập R các TBTDL làm rò rỉ khóa bí mật (rò rỉ toàn bộ hoặc một vài khóa trong tập khóa “dài” L ui ) và tập P các TBTDL hợp pháp. P, R thỏa mãn: P  R  N, P  R   . Yêu cầu NCCDL xác định được định danh các TBTDL thuộc R và phân hoạch P thành các tập con chứa các TBTDL hợp pháp. b. Giải pháp lƣu vết Có nhiều giải pháp để lưu vết TBTDL làm rò rỉ khóa bí mật. Giải pháp lưu vết TBTDL làm rò rỉ khóa trong luận văn sử dụng khung phủ tập con (SCF - xem 1.2) [3]. Giải pháp đó gồm các phần: Khởi tạo, Mã hóa, Giải mã và Thuật toán lưu vết TBTDL làm rò rỉ khóa bí mật.  Thuật toán lưu vết TBTDL làm rò rỉ khóa bí mật: Xác định định danh của TBTDL làm rò rỉ khóa bí mật dựa trên sự phân hoạch tập TBTDL thành các tập con. Giải thuật này sẽ được trình bày trong chương 2. 13 1.4 GIẢI PHÁP THU HỒI THIẾT BỊ THU BẤT HỢP PHÁP a. Bài toán thu hồi NCCDL truyền thông điệp M qua các kênh quảng bá tới tập N gồm các TBTDL (|N|=n). Mỗi TBTDL u i có một tập khóa “dài” L ui (i=1, 2,…, n). NCCDL đã biết tập R các TBTDL làm rò rỉ khóa và tập P các TBTDL hợp pháp. P, R thỏa mãn: P  R  N, P  R   . Yêu cầu: Mọi TBTDL thuộc P giải mã chính xác thông điệp M. Mọi TBTDL thuộc R giải mã chỉ thu được MR  M. Mọi TBTDL sử dụng bộ khóa nhái chỉ thu được M’  M. b. Giải pháp thu hồi Có nhiều giải pháp để thu hồi TBTDL bất hợp pháp. Trong luận văn trình bày giải pháp thu hồi TBTDL bất hợp pháp sử dụng khung phủ tập con (SCF - xem 1.2) [3]. Giải pháp đó gồm các phần: Khởi tạo, Mã hóa, Giải mã.  Hiệu năng của giải thuật thu hồi TBTDL bất hợp pháp Hiệu năng của giải thuật thu hồi thể hiện trên ba tham số sau [3]:  Số lượng khóa “dài” cần lưu trữ tối đa tại mỗi TBTDL u là: |Lu|.  Độ dài phần đầu bản mã (header) trong thông điệp đã mã hóa.  Thời gian giải mã bản mã thông điệp tại TBTDL. 14 1.5 MỘT SỐ CÔNG CỤ 1.5.1 Đồ thị Đồ thị vô hƣớng G (hình 1.1 a) là một cặp (V, E) [6], trong đó: + V là tập các đỉnh hoặc nút, ký hiệu V(G). + E là tập các cạnh nối hai đỉnh không phân biệt thứ tự, ký hiệu E(G). Đồ thị có hƣớng G (hình 1.1 b) là một cặp (V, E) [6], trong đó: + V là tập các đỉnh hoặc nút, ký hiệu V(G). + E là tập các cạnh nối hai đỉnh có phân biệt thứ tự. Một cạnh bắt đầu ở một nút và kết thúc ở một nút khác, ký hiệu E(G). Hình 1. 1: Đồ thị G Đường đi trong đồ thị G là một dãy: v1, e1, v2, e2,…,ei, vi+1, trong đó: vi  V(G) và ei  E(G), ei là cạnh nối nút vi và vi+1. Đường đi trong đồ thị G không lặp lại các nút hoặc các cạnh. Độ dài của đường đi là số cạnh trong dãy xác định đường đi. Đồ thị liên thông là đồ thị có ít nhất một đường đi giữa 2 nút bất kỳ. Đồ thị đơn là đồ thị mà giữa hai đỉnh chỉ có tối đa một cạnh. Đồ thị có chu trình (cyclic) là đồ thị tồn tại một đường đi theo dạng: v1, e1, v2, e2,…, ei, v1 (nút kết thúc trùng nút bắt đầu đường đi). Vòng là một cạnh mà nối từ một nút tới chính nó (e=(v,v)). Đồ thị con G’ của đồ thị G là đồ thị có: V(G’)  V(G), E(G’)  E(G) và mỗi cặp trong E(G’) nối một cặp nút trong V(G’). 15 1.5.2 Cây nhị phân a. Khái niệm cây Cây là đồ thị đơn, vô hướng, liên thông và không có chu trình [6]. Khi nói cây, nghĩa là có đường đi giữa hai nút bất kỳ. Vì không có chu trình, nên đường đi, hay các cạnh là duy nhất. Thông thường cây được vẽ với gốc ở đỉnh trên, ta nói nút y ở dưới nút x nếu x nằm trên đường từ y tới gốc. Một nút trên cây có thể là gốc, nút trong hoặc lá. Mỗi nút v, trừ gốc, đều có duy nhất một nút trên nó, được gọi là cha của nó. Các nút ngay bên dưới nút v được gọi là con của nó. Nút có cùng cha với v được gọi là nút anh em của v. Các nút không có con được gọi là nút lá hoặc nút ngoài. Các nút có ít nhất một con thì được gọi là nút trong. Bất kỳ nút nào cũng là gốc của một cây con bao gồm chính nút đó và các nút dưới nó. Các nút trong của một cây được chia thành các tầng: tầng của một nút là số nút trên đường đi từ nó tới gốc (không kể chính nút đó). Chiều cao của cây là tầng cao nhất trong số tất cả các tầng của các nút trong cây. Cây được gọi là cây được sắp, nếu thứ tự các con của mỗi nút được quy định. 16 b. Khái niệm cây nhị phân Cây nhị phân (hình 1.2) là cây có hai dạng nút:  Nút ngoài: nút lá, không có con.  Nút trong: có chính xác hai con là con trái và con phải. Hình 1. 2: Cây nhị phân Cây nhị phân đầy đủ (hình 1.3) là cây nhị phân, trong đó tất cả các lá có cùng khoảng cách tới gốc. Số lượng các lá trong cây nhị phân đầy đủ có chiều cao k là h  2 k . Cha chung thấp nhất của hai nút (kể cả lá) a, b (hình 1.4) là nút giao nhau giữa đường đi từ a tới gốc và từ b tới gốc. Cây con của cây T là đồ thị con của T và thỏa mãn các tính chất của một cây. 17 Hình 1. 3: Cây nhị phân đầy đủ Hình 1. 4: Cha chung thấp nhất của a và b 18 c. Tính chất cây nhị phân 1) Cây nhị phân có r lá thì có chiều cao ít nhất là log 2 (r) Chứng minh Đầu tiên, chứng minh a   a  1 với mọi a là số thực. Nếu a là số nguyên, thì a   a . Ngược lại, a  a ' trong đó 0    1 và a’ Z. Vì a   a '1 và a  a '  a  a ' (>0) Suy ra a  1  a '1 (cộng 1 vào cả 2 vế)  a  1  a  . Chứng minh tính chất trên bằng phản chứng: Giả sử T có r lá và chiều cao  log 2 (r)  1 . Do T là cây nhị phân nên số lá là: 2 log2 ( r ) 1 . Như vậy số lượng lá nhiều nhất trong cây T là: 2 log2 ( r ) 1  2log2 ( r )11  2log2 (r )  r (cộng 1 vào mũ của 2 vế) Điều này mâu thuẫn với giả thiết là cây T có r lá, suy ra điều phải chứng minh. 2) Thuộc tính rẽ nhánh Một cây nhị phân luôn có thể chia thành hai nhánh trái và phải (hình 1.5). Thuộc tính này được gọi là thuộc tính rẽ nhánh của cây nhị phân [3]. 19 Hình 1. 5: Minh họa thuộc tính rẽ nhánh
- Xem thêm -

Tài liệu liên quan