Tài liệu ứng dụng của đại số tuyến tính trong tổ hợp

Header Page 1 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Phan Thị Sim ỨNG DỤNG CỦA ĐẠI SỐ TUYẾN TÍNH TRONG TỔ HỢP KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2016 Footer Page 1 of 161. Header Page 2 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Phan Thị Sim ỨNG DỤNG CỦA ĐẠI SỐ TUYẾN TÍNH TRONG TỔ HỢP Chuyên ngành: Toán ứng dụng KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Trần Vĩnh Đức Hà Nội – Năm 2016 Footer Page 2 of 161. Header Page 3 of 161. LỜI CẢM ƠN Trước khi trình bày nội dung chính của bản khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới T.S Trần Vĩnh Đức đã tận tình hướng dẫn để em có thể hoàn thành đề tài này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện đề tài thực tập này. Hà Nội, ngày tháng 05 năm 2016 Sinh viên Phan Thị Sim Footer Page 3 of 161. Header Page 4 of 161. LỜI CAM ĐOAN Khóa luận này là kết quả nghiên cứu của bản thân em dưới sự hướng dẫn tận tình của thầy giáo T.S Trần Vĩnh Đức. Trong khi nghiên cứu hoàn thành đề tài nghiên cứu này em đã tham khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Em xin khẳng định kết quả của đề tài "Ứng dụng của đại số tuyến tính trong tổ hợp" là kết quả của việc nghiên cứu, học tập và nỗ lực của bản thân, không có sự trùng lặp với kết quả của các đề tài khác. Nếu sai em xin chịu hoàn toàn trách nhiệm. Hà Nội, tháng 05 năm 2016 Sinh viên Phan Thị Sim Footer Page 4 of 161. Header Page 5 of 161. Mục lục Lời mở đầu 1 1 Một số kiến thức chuẩn bị 4 1.1 Một số khái niệm đại số tuyến tính . . . . . . . . . . . . 4 1.2 Một số khái niệm cơ bản của đồ thị . . . . . . . . . . . . 6 2 Thiết Kế Khối 10 2.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . 10 2.2 Một điều kiện đủ về sự tồn tại thiết kế khối . . . . . . . 13 2.3 Bất đẳng thức Fisher . . . . . . . . . . . . . . . . . . . . 16 3 Ứng Dụng Trong Lý thuyết Đồ thị 20 3.1 Phủ bằng đồ thị hai phần đầy đủ . . . . . . . . . . . . . 20 3.2 Không gian chu trình . . . . . . . . . . . . . . . . . . . . 23 3.3 Lưu thông và cắt: Xem xét lại không gian chu trình. 29 . . 4 Kiểm tra xác suất 35 4.1 Kiểm tra phép nhân ma trận . . . . . . . . . . . . . . . . 35 4.2 Kiểm tra xác suất cho tính chất kết hợp . . . . . . . . . 39 i Footer Page 5 of 161. Header Page 6 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Kết luận 45 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . ii Footer Page 6 of 161. 46 Header Page 7 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Lời mở đầu 1. Lý do chọn đề tài Cùng với sự phát triển với tốc độ nhanh của công nghệ thông tin, lý thuyết tổ hợp và lý thuyết đồ thị đã trở thành các lĩnh vực quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Đại số tuyến tính là một ngành toán học nghiên cứu về không gian vec-tơ, hệ phương trình tuyến tính và các phép biến đổi tuyến tính giữa chúng. Các khái niệm vec-tơ trong không gian vec-tơ, ma trận và các định thức là những công cụ rất quan trọng trong đại số tuyến tính. Nó có nhiều ứng dụng trong toán học và các ngành khoa học khác như khoa học tự nhiên, khoa học kinh tế,. . . Các công cụ của đại số tuyến tính giúp giải quyết rất hiệu quả nhiều bài toán trong tổ hợp. Ví dụ như, biểu diễn ma trận kề hoặc ma trận liên thuộc đã là những công cụ chuẩn cho tính toán trên đồ thị. Vì vậy, dưới sự định hướng của giáo viên hướng dẫn tôi chọn đề tài: “Ứng dụng của đại số tuyến tính trong tổ hợp.” cho khóa luận nhằm tìm hiểu về một số ứng dụng của đại số tuyến tính trong tổ hợp. 2. Mục đích nghiên cứu • Tìm hiểu về thiết kế khối, bất đẳng thức Fisher. Footer Page 7 of 161. 1 Header Page 8 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim • Tìm hiểu về khái niệm phủ bằng đồ thị hai phần đầy đủ. • Tìm hiểu về các khái niệm của không gian chu trình, lưu thông và cắt. • Tìm hiểu về kiểm tra xác suất cho phép nhân hai ma trận, kiểm tra xác suất cho tính kết hợp. 3. Nhiệm vụ nghiên cứu Đưa ra một số ứng dụng của đại số tuyến tính vào các bài toán tổ hợp, đồ thị. 4. Đối tượng và phạm vi nghiên cứu • Đối tượng nghiên cứu: Một số yếu tố của đại số tuyến tính và tổ hợp. • Phạm vi nghiên cứu: Đại số tuyến tính, lý thuyết tổ hợp, lý thuyết đồ thị. 5. Cấu trúc đề tài Ngoài phần mở đầu, kết luận, danh mục tài liệu tham khảo thì khóa luận bao gồm 4 chương: • Chương 1: Một số kiến thức chuẩn bị. • Chương 2: Thiết kế khối. Footer Page 8 of 161. 2 Header Page 9 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim • Chương 3: Ứng dụng trong lý thuyết đồ thị. • Chương 4: Kiểm tra xác suất. Phần lớn khóa luận được tham khảo từ chương 13 của cuốn sách Invitation to Discrete Mathematics của Jiri Matousek và Jaroslav Nesetril. Footer Page 9 of 161. 3 Header Page 10 of 161. Chương 1 Một số kiến thức chuẩn bị Chương này nêu lại một số khái niệm sẽ được thực dùng cho các chương sau. Mục đích của chương này không nhằm hệ thống các khái niệm của đại số tuyến tính và đồ thị. 1.1 Một số khái niệm đại số tuyến tính Định nghĩa 1.1 (Không gian vec-tơ). Cho V là một tập hợp khác rỗng ⃗ ⃗γ , . . . và K là một trường. Giả sử V được mà các phần tử kí hiệu α ⃗ , β, trang bị hai phép toán, gồm: (a) Phép cộng: ⃗ 7→ α ⃗ +: V × V → V, (⃗ α, β) ⃗ + β. (b) Phép nhân: .:K × V → V, (λ, α ⃗ ) 7→ λ.⃗ α. thỏa mãn những điều kiện (hoặc tiên đề) sau đây: Với mọi λ, µ ∈ K và ⃗ ⃗γ ∈ V : với mọi α ⃗ , β, (V1 ) ⃗ + ⃗γ = α (⃗ α + β) ⃗ + (β⃗ + ⃗γ ) (V2 ) ∃⃗0 ∈ V : ⃗0 + α ⃗ =α ⃗ + ⃗0 = α ⃗ (V3 ) ∀⃗ α ∈ V, ∃⃗ α′ ∈ V : α ⃗ +α ⃗′ = α ⃗′ + α ⃗ = ⃗0 Footer Page 10 of 161. 4 Header Page 11 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim (V4 ) α ⃗ + β⃗ = α ⃗ + β⃗ (V5 ) (λ + µ).⃗ α = λ.⃗ α + µ.⃗ α (V6 ) ⃗ = λ.⃗ λ.(⃗ α + β) α + λ.β⃗ (V7 ) (λ(µ.⃗ α)) = (λ.µ)⃗ α (V8 ) 1.⃗ α=α ⃗ Định nghĩa 1.2 (Độc lập tuyến tính). Trong không gian vec-tơ V, hệ vec-tơ (α⃗1 , α⃗2 , . . . , α⃗n ) được gọi là độc lập tuyến tính nếu hệ thức: λ1 α⃗1 + · · · + λn α⃗n = ⃗0 chỉ xảy ra khi λ1 = · · · = λn = 0. Định nghĩa 1.3 (Phụ thuộc tuyến tính). Hệ vec-tơ (α⃗1 , α⃗2 , . . . , α⃗n ) được gọi là phụ thuộc tuyến tính nếu hệ đó không độc lập tuyến tính. Định nghĩa 1.4 (Ma trận). Cho K là một trường và cho m, n là hai số nguyên dương. Ta gọi một ma trận A cấp m × n là một bảng gồm m.n phần tử aij ∈ K, i = 1, . . . , m; j = 1, . . . , n được sắp xếp thành m dòng và n cột như sau:   a a12  11   a21 a22 A=  .. ..  . .  am1 am2 . . . a1n   . . . a2n   . . . ...    . . . amn Kí hiệu A = (aij )m×n . Các phần tử ở dòng thứ i và cột thứ j được gọi là phần tử aij . Các phần tử ai1 , ai2 , . . . , ain được gọi là các phần tử thuộc dòng thứ i, các phần tử a1j , a2j , . . . , amj được gọi là các phần tử thuộc cột thứ j. Footer Page 11 of 161. 5 Header Page 12 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Định nghĩa 1.5 (Hạng của ma trận). Hạng của ma trận A là một số, kí hiệu: rankA. Hạng của ma trận A bằng cấp cao nhất của các định thức con khác 0 của A, nghĩa là rankA = r nếu có một định thức con cấp r của A khác 0 và mọi định thức con cấp lớn hơn r (nếu có) của A đều bằng 0. Định nghĩa 1.6 (Giá trị riêng, vec-tơ riêng). Cho A là một ma trận vuông cấp n, x = (x1 , x2 , . . . , xn ), x ∈ Kn , x ̸= (0, 0, . . . , 0). Nếu số λ ∈ K, thỏa mãn: A.x = λ.x tức A [x] = λ [x] thì λ được gọi là giá trị riêng của A, khi đó x được gọi là vec-tơ riêng của ma trận A ứng với giá trị riêng λ. 1.2 Một số khái niệm cơ bản của đồ thị Định nghĩa 1.7 (Đồ thị có hướng). G là một cặp có thứ tự (V, E), ở đây V là một tập hợp, còn E là một tập con của tích Đề-các V × V , tức là E là một quan hệ hai ngôi trên V . 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ị có hướng G. Cụ thể hơn, 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 đi từ a tới b. Footer Page 12 of 161. 6 Header Page 13 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Định nghĩa 1.8 (Đồ thị vô hướng). G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là tập với các phần tử là tập lực lượng 2 trên V. Các phần tử của V cũng được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị vô hướng G. Nếu e = {a, b} là một cạnh của G thì a và b được gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc với e. Ta cũng kí hiệu các cạnh {a, b} ngắn gọn là ab. Định nghĩa 1.9 (Hành trình, chu trình). Một hành trình trong G (Giả sử G=(V,E) là một đồ thị vô hướng) là một dãy các đỉnh v0 v1 v2 · · ·vn sao cho với mọi i = 0, 1, 2, . . . , n − 1, {vi , vi+1 } là một cạnh của G. Một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Chu trình: là một hành trình khép kín. Định nghĩa 1.10 (Liên thông và thành phần liên thông). Một đồ thị (có hướng, vô hướng) G = (V, E) được gọi là liên thông yếu hay cũng gọi tắt là liên thông, nếu với hai đỉnh vi và vj khác nhau bất kỳ của G tồn tại một hành trình vô hướng trong G với đỉnh đầu là vi và đỉnh là vj . Trong trường hợp ngược lại, đồ thị đồ thị được gọi là không liên thông. Đồ thị con liên thông G′ = (V ′ , E ′ ) của một đồ thị (có hướng, vô hướng) G = (V, E) được gọi là một thành phần liên thông của G. Định nghĩa 1.11 (Cây). Một đồ thị vô hướng không liên thông có khuyên và không có chu trình được gọi là cây. Định nghĩa 1.12 (Rừng). Một đồ thị vô hướng không có khuyên (không nhất thiết phải là liên thông) và không có chu trình được gọi là rừng. Footer Page 13 of 161. 7 Header Page 14 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Định nghĩa 1.13 (Đồ thị hai phần đầy đủ). Đơn đồ thị G = (V, E) sao cho V = V1 ∪ V2 , V1 ∩ V2 = ∅, V1 ̸= ∅, V2 ̸= ∅ và mỗi cạnh của G được nối bởi một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị hai phần. Nếu một đồ thị hai phần G = (V1 ∪ V2 , E) sao cho với mọi v1 ∈ V1 , v2 ∈ V2 , (v1 , v2 ) ∈ E thì G được gọi là đồ thị hai phần đầy đủ. Định nghĩa 1.14 (Ma trận kề). Giả sử G = (V, E) là một đồ thị có hướng V = {v1 , v2 , . . . , vn }. Khi đó ma trận kề của đồ thị G là ma trận  A = (aij )n×n ở đây a a  11 12   a21 a22 =  .. ..  . .  an1 an2   1, aij =  . . . a1n   . . . a2n   . . . ...    . . . ann nếu(vi , vj ) ∈ E  0, nếu(v , v ) ∈ i j / E Dễ thấy rằng ma trận kề A của đồ thị có hướng G hoàn toàn xác định G. Vì vậy, ma trận kề A được coi là một biểu diễn của G. Định nghĩa 1.15 (Ma trận liên thuộc). Giả sử G = (V, E) là đồ thị có hướng với V = {v1 , v2 , . . . , vn } và E = {e1 , e2 , . . . , em }. Khi đó ma trận Footer Page 14 of 161. 8 Header Page 15 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim liên thuộc của đồ thị G là ma trận  B = (bij )n×n b b  11 12   b21 b22 =  .. ..  . .  bn1 bn2  . . . b1n   . . . b2n   . . . ...    . . . bnn ở đây     1, nếu vi là đỉnh đầu của ej ,    bij = −1, nếu vi là đỉnh đầu nhưng không là đỉnh cuối của ej ,      0, nếu vi không liên thuộc với ej . Ma trận liên thuộc B cũng hoàn toàn xác định đồ thị có hướng G. Vì vậy, B cũng được coi là một biểu diễn của G. Footer Page 15 of 161. 9 Header Page 16 of 161. Chương 2 Thiết Kế Khối Trong chương này chúng ta xem xét một số ứng dụng của đại số tuyến tính trong thiết kế khối, một lĩnh vực quan trọng và có nhiều ứng dụng của tổ hợp. Công cụ chủ yếu được sử dụng ở đây là các kết quả về số chiều và hạng của ma trận. 2.1 Định nghĩa và ví dụ Cho V là tập hợp hữu hạn và cho B là hệ tập con của tập hợp V . Để nhấn mạnh hệ tập hợp B trên tập hợp V, ta viết nó như một cặp có thứ tự (V, B). (Chú ý cặp (V, B) như vậy có thể là được xem như tổng quát hoá của khái niệm của đồ thị, được gọi là siêu đồ thị; các điểm của V là thì gọi các đỉnh và các tập hợp của B được gọi là các siêu cạnh.) Nếu tất cả các tập hợp B ∈ B có cùng lực lượng là k, ta nói rằng (V, B) là k-đều. Định nghĩa 2.1. Cho v, k, t, và λ là các số nguyên. Chúng ta giả sử v > k ≥ t ≥ 1 và λ ≥ 1. Thiết kế khối kiểu t-(v, k, λ) là hệ tập hợp Footer Page 16 of 161. 10 Header Page 17 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim (V, B) thoả mãn các điều kiện sau : (1) Tập V có v phần tử. (2) Mỗi một tập hợp B ∈ B có k phần tử. Các tập hợp của B được gọi là các khối. (3) Mỗi tập hợp con gồm t phần tử của tập hợp V được chứa trong đúng λ khối của B. Dưới đây là một vài ví dụ cơ bản minh hoạ định nghĩa này. Ví dụ 2.1. Cho V là tập hợp hữu hạn và k là một số nguyên. Chúng ta ( ) đặt B = Vk (nói cách khác, B gồm mọi tập con k phần tử của tập V ). Cặp (V, B) này được gọi là thiết kế khối tầm thường. Dễ kiểm tra rằng (V, B) là một thiết kế khối t-(v, k, λ), trong đó (v−t) t ∈ {1, 2, . . . , k} có thể lựa chọn tùy ý, v = |V |, và λ = k−t . (Để thấy điều này rõ hơn, ta nhận xét rằng mọi tập con gồm t phần tử của V (v−t) được chứa trong chính xác B = k−t khối B ∈ B). Ví dụ 2.2. Cho V là 1 tâp hợp với lực lượng v; và k ≥ 1 là một số nguyên dương và là một ước của v. Ta phân hoạch các phần tử của V thành các tập con gồm k phần tử rời nhau B1 , B2 , · · · , Bv/k và đặt { } B = B1 , B2 , . . . , Bv/k . Khi đó (V, B) là thiết kế khối kiểu 1-(v, k, 1). Ví dụ 2.3. Cho V = {0, 1, 3, 4, 5} và B chứa các bộ ba sau: {0, 1, 2}, {0, 2, 3}, {0, 3, 4}, {0, 4, 5}, {0, 1, 5}, {1, 2, 4}, {2, 3, 5}, {1, 3, 4}, {2, 4, 5}, {1, 3, 5}. Khi đó (V, B) một thiết kế khối kiểu 2-(6, 3, 2). Thiết kế khối này có thể định nghĩa một cách xây dựng hơn như sau. Xét một đồ thị chu trình với các đỉnh 1, 2, . . . , 5; và thêm một đỉnh 0. Footer Page 17 of 161. 11 Header Page 18 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim Hệ B gồm tất cả các tập 3 đỉnh chứa đúng một cạnh của chu trình; xem hình dưới đây: Ví dụ này thể hiện trực quan rằng thiết kế khối tạo thành tính đều nào đó. Thường không dễ xây dựng thiết kế khối của kiểu đã cho, và câu hỏi cơ bản trong lĩnh vực này là câu hỏi tồn tại. Bài toán 2.1. Cho các số v, k, λ, t, hãy quyết định xem liệu có tồn tại thiết kế khối kiểu t-(v, k, λ) hay không? Thiết kế khối vẫn đang được sử dụng rộng rãi bởi các nhà thống kê trong thiết kế thí nghiệm. Đây là động cơ của những khái niệm được giới thiệu ở trên. Hãy tưởng tượng ta muốn đánh giá các cách xử lý một loại cây nào đó (để diệt sâu bệnh chẳng hạn). Có v kiểu xử lý. Chúng ta sẽ so sánh các cách xử lý bằng một loạt các thí nghiệm. Trong mỗi thí nghiệm chúng ta có k kiểu xử lý; được cho bởi yêu cầu kỹ thuật thí nghiệm. Mỗi thí nghiệm sẽ tạo ra một khối các xử lý được cần kiểm tra. Về nguyên tắc chúng ta phải kiểm tra tất cả các k-bộ, hoặc khối xử lý có thể, nhưng trong điều kiện thí nghiệm, cách kiểm tra tầm thường này (vì thế có tên là "thiết kế khối tầm thường") là quá tốn kém ngay cả cho những giá trị nhỏ của k và v. Vì lý do này, các nhà thống kê bắt đầu sử dụng thiết kế khối, ở đó không cần kiểm tra tất cả mọi k-bộ có thể mà chỉ một số Footer Page 18 of 161. 12 Header Page 19 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim khối được lựa chọn. Tất nhiên điều này sẽ dẫn đến lỗi, vì thử nghiệm là không đầy đủ: một vài khối không được xem xét, và vì thế một số ảnh hưởng lẫn nhau của các xử lý sẽ bị bỏ qua. Để bù đắp cho thiếu sót của phương pháp thử nghiệm không đầy đủ này, chúng ta yêu cầu rằng ít nhất mỗi cặp cách xử lý xuất hiện cùng nhau trong cùng một số thử nghiệm- khối. Sơ đồ cho chuỗi các thí nghiệm này đúng là một thiết kế khối kiểu 2-(v, k, λ). Nếu chúng ta yêu cầu rằng mỗi bộ ba cách xử lý phải xuất hiện trong cùng một số, λ, thử nghiệm, ta được một thiết kế khối kiểu 3-(v, k, λ), và v.v. . . Thiết kế khối khác nhau xuất hiện dưới tên gọi khác nhau trong tài liệu: chẳng hạn như, thiết kế khối không đầy đủ được cân bằng (hay còn gọi là BIBD) cho thiết kế của kiểu 2-(v, k, λ), hệ Steiner (cho λ = 1), cấu hình chiến thuật (cho t > 2), v.v . . . 2.2 Một điều kiện đủ về sự tồn tại thiết kế khối Ta dẫn ra dưới đây một điều kiện cần dùng đại số. Điều kiện nguyên. Rõ ràng không phải luôn tồn tại một thiết kế khối kiểu t-(v, k, λ) trên mọi tập, cụ thể cho mọi giá trị của v. Ví dụ, thiết kế kiểu 1-(v, k, 1) là một phân hoạch tập V thành các tập k phần tử, và vì thế v phải là bội của k. Định lý sau mô tả điều kiện cần quan trọng cho sự tồn tại của thiết kế khối của kiểu t-(v, k, λ). Định lý 2.1 (Điều kiện đủ). Nếu thiết kế khối kiểu t − (v, k, λ) tồn tại, Footer Page 19 of 161. 13 Header Page 20 of 161. Khóa luận tốt nghiệp Đại học Phan Thị Sim vậy thì các phân số sau phải là những số nguyên: λ v(v − 1) · · · (v − t + 1) (v − 1) · · · (v − t + 1) v−t+1 , λ , ··· , λ . k(k − 1) · · · (k − t + 1) (k − 1) · · · (k − t + 1) k−t+1 Chứng minh. Đây là ứng dụng của phép đếm bằng hai cách. Cho (V, B) là một thiết kế khối kiểu t − (v, k, λ). Cố định một số nguyên s với 0 ≤ s ≤ t và một tập hợp s phần tử S ⊆ V . Ta cùng đếm số N là số các ( ) cặp (T, B) với S ⊆ T ∈ Vt và T ⊆ B ∈ B: Một mặt, T có thể chọn trong (v−s) cách, và mỗi T là một tập con (v−s) có đúng λ khối B ∈ B; do đó N = λ t−s . t−s Mặt khác, cho M là số của khối chứa tập hợp S. Vì mỗi khối B chứa ( ) (k−s) có chứa k−s tập t phần tử T với S ⊆ T , ta cũng có N = M t−s t−s . Do đó (v−s) t−s M = λ (k−s ) =λ t−s (v − s) · · · (v − t + 1) (k − s) · · · (k − t + 1) và vì thế phân số bên phải phải là số nguyên như khẳng định của định lý. Ví dụ 2.4 (Hệ bộ ba Steiner). Đây là ví dụ "đầu tiên" không tầm thường của thiết kế khối kiểu t-(v, k, λ) thu được cho t = 2, λ = 1, k = 3. Đây là hệ bộ ba trong đó mỗi cặp của điểm chứa trong chính xác một bộ ba. Nói cách khác, đó là cách phủ tất cả các cạnh của đồ thị đầy đủ bằng các tam giác không chung cạnh. Footer Page 20 of 161. 14