ĐỒ THỊ
Các khái niệm cơ bản
Đồ thị, hay còn gọi là graph, là một khái niệm quan trọng trong toán học và cuộc sống hàng ngày Trong các giờ học toán, đồ thị được sử dụng để biểu diễn hàm số, trong khi các biểu đồ kinh tế cũng được gọi là đồ thị Tóm lại, đồ thị là công cụ toán học giúp thể hiện mối quan hệ giữa hai hoặc nhiều đối tượng khác nhau.
1.1.1 Định nghĩa Một đồ thị được hiểu là một cặp hai tập hợp hữu hạn Tập hợp đỉnh và tập hợp cạnh nối các đỉnh này với nhau, hay định nghĩa cụ thể là: Đồ thị G có tập hợp đỉnh V và có tập hợp cạnh E là G = (V, E)
1.1.2 Một số khái niệm liên quan đến đồ thị
1.1.2.1 Đồ thị có hướng, đồ thị vô hướng, đố thị đơn và đồ thị kép
- Cho hai đỉnh a và b, đoạn thẳng nối a và b được gọi là cạnh vô hướng
- Cho hai đỉnh a và b, đoạn thẳng nối a và b đồng thời chỉ rõ hướng của đoạn thẳng đó (từ a đến b hay từ b đến a) được gọi là cạnh có hướng
- Đồ thị mà có tất cả các cạnh đều vô hướng thì được gọi là đồ thị vô hướng, thường được kí hiệu là G=(V,E)
- Đồ thị mà có tất cả các cạnh đều có hướng thì được gọi là đồ thị có hướng, thường được kí hiệu là G=[V,E]
- Đồ thị có cả cạnh vô hướng và cạnh có hướng được gọi là đồ thị hỗn hợp
Đồ thị đơn là loại đồ thị không có khuyên, tức là không có cạnh nối một đỉnh với chính nó, và giữa hai đỉnh chỉ có tối đa một cạnh nối chúng.
- Đồ thị kép là đồ thị hoặc có khuyên hoặc tồn tại hai đỉnh nào đó mà giữa chúng có ít nhất hai cạnh nối chúng
- Đồ thị G 1 =(V 1 ,E 1 ) được gọi là đồ thị con của G 2 =(V 2 ,E 2 ) nếu V 1 V 2 và E 1 E 2
Trong lý thuyết đồ thị, một đường đi từ đỉnh A1 đến đỉnh An được xác định bởi một dãy cạnh nối tiếp, trong đó hai cạnh nối tiếp có chung một đầu mút Đường đi này được ký hiệu là A1A2 An, với A1 được gọi là đỉnh đầu và An là đỉnh cuối.
- Một đường khép kín (có đỉnh đầu và đỉnh cuối trùng nhau) được gọi là một chu trình
- Đường chứa tất cả các cạnh của đồ thị được gọi là đường Euler trong đồ thị
- Đường chứa tất cả các đỉnh trong đồ thị được gọi là đường Hamiton
- Một dãy cạnh được gọi là dãy cạnh đơn nếu ta bỏ hướng các cạnh (nếu có) thì nó trở thành một con đường
- Đồ thị G được gọi là liên thông nếu hai đỉnh bất kỳ của nó được nối bởi một dãy cạnh đơn
- Đồ thị G được gọi là đồ thị đủ nếu mỗi cặp gồm hai đỉnh bất kỳ khác nhau được nối với nhau bằng một và chỉ một cạnh
Nếu một đồ thị chưa đủ ta có thể thêm vào nó một số đoạn thẳng để đồ thị thu được là đồ thị đủ
Đồ thị bù của đồ thị G được định nghĩa là một đồ thị có số đỉnh tương đương với G, trong đó hai đỉnh được nối với nhau bằng một cạnh nếu và chỉ nếu chúng không có cạnh nối trong đồ thị G.
Nếu S là tập con của tập đỉnh của đồ thị G, thì đồ thị được sinh ra từ S sẽ là đồ thị con lớn nhất của G với tập đỉnh S, được ký hiệu là G S.
Ta có : G S là đồ thị thành phần của G
Nếu G là đồ thị đầy đủ thì G S cũng là đồ thị đầy đủ
Ví dụ: Hình 1.1 là đồ thị đủ 5 đỉnh
S = { B, C, D, E} Đồ thị sinh bởi S chính là phần đồ thị được tô đậm và đây cũng là đồ thị đủ
- Cây là một đồ thị đơn vô hướng không có chu trình với ít nhất một đỉnh (hình 1.2: hai cây)
- Một đồ thị mà mỗi thành phần liên thông của nó đều là cây được gọi là bụi (hình 1.3: một bụi gồm hai cây)
Sắc số
Trong đồ thị G, việc tô màu các đỉnh là rất quan trọng Một đỉnh a được coi là tô màu ổn định khi không có đỉnh láng giềng nào của a cùng màu với nó Hai đỉnh được gọi là láng giềng nếu chúng được nối với nhau bằng một cạnh.
Cách tô màu các đỉnh của đồ thị G được gọi là tô màu ổn định khi mỗi đỉnh trong đồ thị đều được tô màu theo cách ổn định.
Giả sử G là một đồ thị đã được tô màu ổn định Số lượng màu tối thiểu cần thiết để tô các đỉnh của G một cách ổn định được gọi là sắc số, ký hiệu là χ(G).
- Đồ thị có khuyên thì không có cách tô màu ổn định các đỉnh của nó
- Đồ thị có cạnh kép G * có G * = G với G là đồ thị đơn thu được từ cách thay cạnh kép của G * bằng một cạnh đơn
- Với mỗi đồ thị đơn G với n đỉnh ta có thể tô màu ổn định của chúng bởi n màu, với mỗi đỉnh ta gán cho một màu
- Đồ thị điểm có sắc số bằng 1
- Đồ thị rỗng có sắc số bằng 0
- Đồ thị đủ n đỉnh có sắc số bằng n
Bài toán tô màu bản đồ, một thách thức thú vị đã tồn tại từ cuối thế kỷ 18, cho thấy rằng chỉ cần 4 màu để tô màu các quốc gia sao cho những nước có biên giới chung không cùng màu Mặc dù bài toán này được giải quyết vào năm 1975 bởi Kenneth Appel và Wolfgang Haken, lời giải dài gần 200 trang cùng với một chương trình máy tính đã khiến nhiều người vẫn mong chờ một lời giải ngắn gọn và chính xác hơn.
Cho mỗi đồ thị G với bậc lớn nhất ta có: G 1
(Bậc của một đỉnh là số láng giềng của đỉnh đó)
Đồ thị G có bậc lớn nhất , nghĩa là mỗi đỉnh của G không có quá láng giềng Với 1 màu khác nhau, ta có thể tô màu ổn định n đỉnh của đồ thị từ đỉnh 1 đến đỉnh n Cụ thể, đỉnh đầu tiên sẽ được tô một trong 1 màu, và số màu được chọn cho đỉnh này sẽ là số láng giềng của nó trong số màu còn lại Sau đó, từ một đỉnh kề của đỉnh thứ nhất, ta tiếp tục tô màu các đỉnh láng giềng sao cho màu của chúng khác với màu của đỉnh kề đó.
Quá trình tô màu các đỉnh của đồ thị G sẽ tiếp tục cho đến khi tất cả các đỉnh được tô hoàn chỉnh Điều này là do mỗi đỉnh có thể được tô với một trong số màu, trong khi số lượng đỉnh không vượt quá .
Một đồ thị cho trước G với ít nhất một cạnh có sắc số bằng 2 khi và chỉ khi G không có chu trình lẻ cạnh
Chúng ta chỉ cần chứng minh định lý cho các đồ thị liên thông, vì nếu đồ thị có nhiều thành phần liên thông, thì sắc số của đồ thị sẽ bằng sắc số lớn nhất của các thành phần liên thông đó.
Nếu đồ thị G có ít nhất một cạnh có sắc số bằng 2, thì G không chứa chu trình lẻ cạnh Cụ thể, trong một chu trình bất kỳ C của G, các đỉnh được tô màu xen kẽ, dẫn đến việc chu trình phải có số đỉnh chẵn Do đó, số cạnh của chu trình cũng sẽ là số chẵn.
Giả sử G là đồ thị có ít nhất một cạnh và không có chu trình lẻ cạnh, thì G sẽ có sắc số bằng 2, tức là có thể tô màu ổn định đồ thị bằng 2 màu Bắt đầu từ một đỉnh P0 của G, mỗi đỉnh P trong đồ thị G đều có một con đường W nối với P0, nhờ vào tính liên thông của G.
Ta sẽ tô màu đỉnh P bởi màu đỏ nếu độ dài l(W) là chẵn, ngược lại tô đỉnh
P màu xanh nếu l(W) là lẻ
Màu sắc của đỉnh P không bị ảnh hưởng bởi việc lựa chọn con đường, vì bất kỳ con đường nào khác W' nối P0 với P cũng có độ dài chẵn hoặc lẻ tương tự.
W Thật vậy, giả sử W có độ dài chẵn cạnh, nếu tồn tại con đường W' nối P0 với
P mà có độ dài lẻ cạnh thì khi đó trong G có một chu trình lẻ cạnh Mâu thuẫn với giả thiết G không có chu trình lẻ cạnh
Tiếp theo, chúng ta sẽ tô màu các đỉnh láng giềng của đỉnh P Giả sử Q là một đỉnh láng giềng của P trong đồ thị G, được nối với P qua một cạnh k Chúng ta sẽ xem xét một con đường W0 có độ dài ngắn nhất nối P0 với P, nhằm phân tích con đường kết nối P0 với P.
Q trong các trường hợp Q thuộc và không thuộc đường W0
- Nếu Q nằm trên W 0 thì ta thu được một con đường nối P 0 và Q có độ dài là l(W0) - 1
- Nếu Q không nằm trên W 0 ta nối thêm cạnh k vào W 0 và thu được con đường nối P0 với Q có độ lài là l(W0) + 1
Do tính chẵn lẻ của con đường nối P0 với P và Q khác nhau, màu sắc của P và Q cũng sẽ khác nhau Điều này cho thấy tất cả các đỉnh láng giềng của P sẽ được tô màu khác với P Do đó, P được tô màu ổn định, và đây là một phương pháp tô màu ổn định.
Bài toán tô màu các cạnh
Nhiều bài toán thực tế có thể trở nên khó giải quyết nếu để nguyên trạng thái Tuy nhiên, khi chuyển đổi bài toán sang dạng đồ thị, trong đó các đối tượng là các đỉnh và các mối quan hệ là các cạnh, việc phân chia mối quan hệ giữa hai đối tượng thông qua việc tô màu các cạnh sẽ giúp đơn giản hóa quá trình giải quyết.
Vì vậy, các bài toán tô màu các cạnh có rất nhiều ứng dụng
“Nếu nhốt n chú thỏ vào n - 1 cái chuồng (n > 2) thì bao giờ cũng có hai chú thỏ bị nhốt vào cùng một chuồng”
Nguyên lý Dirichlet mở rộng được phát biểu như sau: “Nếu nhốt n con thỏ vào m cái chuồng thì tồn tại một chuồng có ít nhất n m
( a là kí hiệu số nguyên lớn nhất không lớn hơn số thực a)
Nguyên lý Dirichlet có thể được mở rộng với định nghĩa: “Cho n và k là hai số tự nhiên, số nhỏ nhất f(n,k) của các đồ vật cần có để khi chia vào n ngăn kéo, luôn tồn tại ít nhất một ngăn kéo chứa k+1 đồ vật.” Một khái niệm liên quan đến nguyên lý này là số Ramsey trong lý thuyết đồ thị.
1.3.2 Số Ramsey cho đồ thị đủ
Trong một đồ thị đầy đủ, ta có thể chia tập hợp các cạnh thành hai ngăn kéo bằng cách tô màu xanh và đỏ Với mỗi cặp số tự nhiên m và n, luôn tồn tại một số tự nhiên p, sao cho mọi cách tô màu các cạnh của đồ thị đủ Kp sẽ tạo ra một đồ thị đủ Kn với tất cả các cạnh màu xanh hoặc một đồ thị đủ Km với tất cả các cạnh màu đỏ.
Số p nhỏ nhất đó kí hiệu là R(m,n)
R(3,3) được xác định là lớn hơn hoặc bằng 6, vì trong đồ thị có 5 đỉnh, có thể thực hiện một cách tô màu mà không tạo ra đồ thị đủ 3 đỉnh nào có cùng màu.
Khi tô màu các cạnh của đồ thị đầy đủ 6 đỉnh K6 bằng hai màu xanh và đỏ, luôn tồn tại một đồ thị con đầy đủ 3 đỉnh K3 trong đồ thị này, với tất cả các cạnh của nó có cùng màu, hoặc là màu đỏ hoặc màu xanh.
Trong đồ thị K6, chọn một đỉnh a bất kỳ, từ đỉnh này có 5 đỉnh khác xuất phát, tạo thành 5 cạnh được tô màu xanh và đỏ Theo nguyên lý Dirichlet, sẽ tồn tại ít nhất 3 cạnh cùng màu Giả sử 3 cạnh này đều màu đỏ, cụ thể là (a,b), (a,c), và (a,d).
Nếu có một cạnh màu đỏ tồn tại, giả sử (c, d), thì cùng với các cạnh (a, c) và (a, d), chúng tạo thành một đồ thị đủ 3 đỉnh với tất cả các cạnh đều được tô màu đỏ.
Nếu cả ba cạnh cùng màu xanh, ta có một đồ thị đủ ba đỉnh với các cạnh cùng màu xanh Đối với các giá trị m và n nhỏ, chúng ta có thể xác định giá trị R(m, n) Tuy nhiên, trong hầu hết các trường hợp, chỉ có thể xác định được cận trên của R(m, n).
Bài toán Remsey có thể mở rộng cho trường hợp tô nhiều màu, với câu hỏi liệu có thể xác định số nhỏ nhất R(G1, G2, , Gk) sao cho khi tô màu các cạnh của đồ thị đầy đủ có R(G1, G2, , Gk) đỉnh bằng k màu, ta luôn thu được một đồ thị con Gi (i=1, ,n) có các cạnh cùng màu Tuy nhiên, trong trường hợp này, việc xác định số Remsey trở nên khó khăn hơn, và chỉ có thể xác định được cận trên của nó.
Bây giờ ta sẽ xác định cận trên của số Remsey R(G 1 , G 2 , , G k ) trong trường hợp Gi = K 3 (i= 1,2, ,k) Ta ký hiệu là R k (3) Ta có định lý sau: a b c d b d a c
Cho mỗi số tự nhiên k , ta có bất đẳng thức:
Đặt P = (k + 1)(R_k(3) - 1) + 2, chúng ta cần chứng minh rằng trong mọi cách tô màu đồ thị đủ Kp với k + 1 màu khác nhau, luôn tồn tại ít nhất một đồ thị đủ K3 mà các cạnh có cùng một màu trong k + 1 màu đã được sử dụng.
Giả sử ta có đồ thị đầy đủ G với p đỉnh và ta tô màu các cạnh của G bằng các màu 1, 2, 3, , k, k + 1 Chọn một đỉnh a bất kỳ của G, do G là đồ thị đầy đủ, số cạnh xuất phát từ đỉnh a là p - 1 = (k + 1)(Rk(3) - 1) + 1 Theo nguyên lý Dirichlet, với (k + 1)(Rk(3) - 1) + 1 cạnh được tô màu bởi k + 1 màu khác nhau, sẽ có ít nhất một số cạnh cùng màu.
R R k k cạnh được tô bởi cùng một màu Không mất tính tổng quát, giả sử Rk(3) cạnh là e 1 , e 2 , , e Rk(3) và được tô bởi cùng một màu thứ k + 1
Khi các đỉnh kề với đỉnh a được nối với a bởi các cạnh ei (i= 1, 2, , R k (3)), chúng sẽ tạo thành một đồ thị đầy đủ R k (3) Có hai trường hợp xảy ra: Trường hợp 1, nếu trong đồ thị đủ KRk(3) có một cạnh e được tô màu k+1, thì cạnh e này cùng với hai trong số các cạnh e1, e2, , eRk(3) sẽ tạo thành một đồ thị đủ 3 đỉnh với tất cả các cạnh đều được tô màu k + 1.
Trong trường hợp 2, nếu đồ thị KRk(3) có một cạnh e được tô bằng màu thứ k + 1, thì đồ thị đầy đủ KRk(3) sẽ được tô bằng k màu từ 1 đến k Theo định nghĩa về số Ramsey R k (3), trong đồ thị đầy đủ KRk(3) luôn tồn tại ít nhất một đồ thị đủ 3 đỉnh K3 mà tất cả các cạnh của nó đều được tô bằng một màu.
Chúng ta đã tìm hiểu những kiến thức cơ bản về cách tô màu các cạnh của đồ thị và cách xác định cận trên của số Remsey Trên thực tế, nhiều bài toán có thể được chuyển đổi thành dạng đồ thị, giúp việc giải quyết trở nên dễ dàng hơn.
1.3.5 Một số bài toán liên quan
Bài toán 1 Chứng minh rằng trong sáu người bất kỳ luôn tồn tại ba người đôi một quen nhau hoặc đôi một không quen nhau
Bài toán này là một biến thể của định lý 1, trong đó chúng ta chuyển đổi bài toán sang dạng đồ thị Mỗi người trong số 6 người sẽ được biểu diễn bằng một đỉnh, tạo thành đồ thị với 6 đỉnh Hai người quen nhau được nối bằng đoạn thẳng màu xanh, trong khi hai người không quen nhau được nối bằng đoạn thẳng màu đỏ Như vậy, chúng ta có một đồ thị đầy đủ K6 với các cạnh được tô màu xanh và đỏ Nhiệm vụ của bài toán là chứng minh sự tồn tại của một đồ thị K3 trong K6, trong đó tất cả các cạnh đều cùng màu xanh hoặc đỏ.
MẠNG LƯỚI Ô VUÔNG VÀ ĐIỂM NGUYÊN
Mạng lưới ô vuông
- Bảng ô vuông là một hình chữ nhật được chia thành nhiều ô vuông bằng nhau
Một lưới ô vuông là hệ thống gồm các đường thẳng dọc và ngang, chia mặt phẳng thành các ô vuông bằng nhau Các điểm giao nhau của các đường thẳng này được gọi là các nút lưới.
Nhận xét: Bảng ô vuông là một phần của lưới ô vuông
2 1.2 Một số bài toán liên quan
Trong một sân hình vuông chia thành 25 ô nhỏ, mỗi ô có một học sinh đứng Khi có hiệu lệnh, mỗi học sinh sẽ bước sang ô có cạnh chung với ô mình đang đứng Cần chứng minh rằng sẽ luôn có ít nhất một ô vuông trống sau khi các học sinh di chuyển.
Để giải bài toán, đầu tiên chúng ta sẽ tô 25 ô vuông bằng hai màu đen và trắng theo cách xen kẽ Kết quả là sẽ có 13 ô màu đen và 12 ô màu trắng, giữ nguyên tính tổng quát của bài toán.
(hình 2.1) Khi đánh trống thì những học sinh đứng ở ô màu đen thì bước sang ô màu trắng và ngược lại
Do có 13 ô đen mà chỉ có 12 ô trắng, vậy nên 12 em ở ô trắng không thể bước sang 13 ô đen, vậy nên ít nhất còn một ô đen bị trống
Tương tự ta cũng sẽ luôn có một ô có ít nhất 2 học sinh (Đpcm)
Bài toán 2 Chứng minh rằng, không thể dùng hai chữ I (có hai ô vuông) và hình chữ T (có 4 ô vuông) để xếp kín một hình ô vuông 4 4 gồm 16 ô vuông
Đầu tiên, chúng ta sẽ tô hình vuông 4x4 bằng hai màu đen và trắng xen kẽ, tạo ra 8 ô vuông màu đen và 8 ô vuông màu trắng Tiếp theo, chúng ta tô các ô vuông ở hình chữ I và hình chữ T Hình chữ I có 2 ô vuông, do đó sẽ có một ô đen và một ô trắng Trong khi đó, hình chữ T khi tô sẽ có một ô trắng và 3 ô đen hoặc một ô đen và 3 ô trắng, dẫn đến việc hình chữ T sẽ tạo ra một số lẻ ô đen.
Ba chữ T sẽ lấp một số lẻ ô đen, trong khi hai chữ I lấp một số chẵn ô đen Do đó, ba chữ T và hai chữ I sẽ tạo thành một tổng số ô đen chẵn, nhưng hình vuông 4x4 lại có 8 ô đen (số chẵn) Vì vậy, không thể sử dụng chữ I và chữ T để xếp vào ô vuông 4x4 như yêu cầu.
Bài toán 3 Trên tờ giấy kẻ ô vuông có kích thước 20 30, có thể kẻ được hay không một đường thẳng không đi qua các đỉnh mà cắt 50 ô vuông? Lời giải
Trong một bảng ô vuông, không tính đến đường biên, có 18 đoạn ngang và 28 đoạn dọc Một đường thẳng d có thể cắt tối đa 18 đoạn ngang và 28 đoạn dọc, dẫn đến 18 + 28F giao điểm không phải là nút lưới Khi đó, đường thẳng d sẽ cắt qua 47 ô vuông Do đó, không thể có đường thẳng nào cắt qua 50 ô vuông.
Cho bảng vuông kích thước 2n x 2n với 3n quân cờ được đặt trong 3n ô bất kỳ Cần chứng minh rằng có thể chọn n hàng và n cột sao cho tổng số quân cờ trong các hàng và cột đó là 3n.
Để chứng minh rằng có thể chọn ra n hàng và n cột chứa 3n quân cờ, ta cần chứng minh bổ đề: Khi chọn n hàng có số quân cờ nhiều nhất, số quân cờ còn lại sẽ không vượt quá n.
Chúng ta sử dụng phương pháp phản chứng: Giả sử sau khi chọn n hàng chứa nhiều quân cờ nhất mà vẫn còn lại nhiều hơn n quân cờ Theo nguyên lý Dirichlet, sẽ tồn tại ít nhất một hàng có ít nhất 2 quân cờ Vì đã chọn n hàng có số quân cờ lớn nhất, mỗi hàng đã chọn phải có số quân cờ lớn hơn hoặc bằng 2 Do đó, tổng số quân cờ đã chọn sẽ lớn hơn hoặc bằng 2n.
Sau khi chọn n hàng có số quân cờ lớn nhất, số quân cờ còn lại không vượt quá n, dẫn đến việc có thể chọn n cột chứa n quân cờ nữa, hoàn thành số quân cờ trên bàn Điều này chứng minh bổ đề đã được đưa ra.
Bài toán 5 đề cập đến một bảng hình chữ nhật kích thước 3x4, gồm 12 ô vuông, trong đó có một ô ghi số 0 Cần chứng minh rằng không thể điền 11 ô còn lại bằng các chữ số từ 0 đến 9 với các điều kiện: a) Mỗi số không được sử dụng quá 2 lần; b) Tổng các số ở mỗi cột phải bằng nhau và lớn hơn 15; c) Tổng các số ở mỗi hàng cũng phải bằng nhau.
Lời giải ( Chứng minh bằng phản chứng )
Giả sử tồn tại cách điền các số vào 11 ô vuông thỏa mãn cả 3 điều kiện Gọi n là tổng 12 số của bảng
Từ điều kiện b) ta có: n chia hết cho 4 và n lớn hơn 4.16 = 64
Từ điều kiện c) ta có: n chia hết cho 3 và do (3, 4) = 1 nên n chia hết 12
Từ điều kiện a) ta có: Tổng của 12 số không vượt quá :
Từ 64 n 74 và n chia hết 12 nên suy ra n = 72
Khi đó: Tổng mỗi hàng là: 72 : 3 = 24
Tổng mỗi cột là 18, được tính bằng cách chia 72 cho 4 Trong cột có chứa số 0, để đạt tổng 18, hai số còn lại phải là hai số 9 Vì không được phép lặp lại số, nên hai số 9 trong cột chứa 0 sẽ không xuất hiện ở hàng chứa số đó.
0 nữa Vậy tổng các số ở hàng chứa 0 là: 0 + 8 + 8 + 7 = 23 < 24
Vậy không thể có cách điền số thỏa mãn bài toán
Trên lưới ô vuông cạnh 1, các ô được tô màu đen và trắng xen kẽ Bài toán yêu cầu tính bán kính lớn nhất của các đường tròn đi qua ô trắng.
Nếu một đường tròn chỉ nằm trong một ô trắng có bán kính lớn nhất, thì đó chính là đường tròn nội tiếp ô vuông với bán kính bằng 1/2.
Xét các đường tròn đi qua nhiều ô trắng
Đường tròn chỉ đi qua các ô trắng, vì vậy nó không thể cắt các cạnh của ô vuông mà không đi qua ô đen Do đó, các đường tròn này phải đi qua các đỉnh của ô trắng Chúng ta xem xét trường hợp đường tròn đi qua đỉnh A của ô trắng.
ABCD Có 2 khả năng xảy ra (hình 2.3):
Khả năng 1: Đường tròn đi qua 2 đỉnh liên tiếp nhau của ô vuông chẳng hạn A và B Đường tròn xác định bởi 3 điểm Ta xét đỉnh E và G, có 2 trường hợp:
- Đường tròn đi qua A, B, E dễ dàng nhận thấy đường tròn này nhận I là tâm và có đường kính là AE = 2
- Đường tròn đi qua A, B, G Khi đó đường tròn có tâm K là tâm của một ô vuông trắng, có đường kính AH = 10
Phủ hình bằng mạng lưới ô vuông
Gốc tọa độ là tâm đối xứng của một hình lồi diện tích lớn hơn 4 Chứng minh rằng hình đó chứa một điểm nguyên khác tâm tọa độ
Xét tất cả các hình lồi được tạo ra từ hình đã cho thông qua phép tịnh tiến theo các vectơ có cả hai tọa độ đều chẵn Chúng ta sẽ chứng minh rằng có ít nhất hai hình trong số những hình thu được sẽ có giao điểm khác rỗng.
Hình ban đầu được giới hạn bởi hình tròn có tâm tại gốc tọa độ và bán kính R, với R là số thực dương Các hình được xem xét có tọa độ tâm đối xứng là các số không âm nhỏ hơn hoặc bằng 2n, dẫn đến việc có tổng cộng (n + 1)² hình Tất cả các hình này đều nằm trong một hình vuông có cạnh 2.(n + R).
Nếu các hình này không cắt nhau thì với mọi n ta có:
(n + 1) 2 S ≤ 4.(n + R) 2 , (*) trong đó S là diện tích của hình ban đầu
Nhưng S > 4, nên có thể chọn n sao cho:
Do (*) và (**) mâu thuẫn, cần có ít nhất hai hình có giao khác rỗng Giả sử hình H1 tâm O1 và hình H2 tâm O2 có điểm chung A Ta chứng minh rằng trung điểm M của O1O2 thuộc cả hai hình Xác định điểm B sao cho O B 1 = - O A 2, do hình có tâm đối xứng nên B thuộc hình H1 Vì A và B đều thuộc H1, trung điểm AB cũng thuộc H1 (do H1 lồi) Do đó, M thuộc H1 và không trùng với A.
O 1 Theo phép tịnh tiến O O 1 về hình ban đầu ta cũng có M' là ảnh của điểm M M' là điểm cần tìm (Đpcm)
Trên một tờ giấy có một vết mực có diện tích nhỏ hơn 1, có thể kẻ carô với các hình vuông đơn vị (cạnh 1) sao cho không có đỉnh nào của mạng lưới ô vuông rơi vào vết mực Điều này chứng minh rằng việc sắp xếp các hình vuông sao cho tránh xa vết mực là khả thi.
Để thực hiện thí nghiệm, đầu tiên, bạn cần một tờ giấy trắng và phủ lên đó một mạng lưới ô vuông đơn vị Sau đó, cắt các ô vuông này ra và xếp chồng lên nhau Giả sử mực có khả năng thấm từ ô này sang ô khác, nhưng diện tích vết mực nhỏ hơn 1, nên sẽ có ít nhất một điểm trong các ô vuông không bị thấm mực Khi bạn đặt lại các ô vuông về vị trí ban đầu, những điểm này sẽ tạo thành một hệ thống đỉnh của mạng lưới ô vuông đơn vị, và không có điểm nào nằm trong vết mực.
Trong quá trình nghiên cứu và tổng hợp các kiến thức từ tài liệu tham khảo, khoá luận đã đạt được những kết quả sau:
- Trình bày các khái niệm cơ bản về đồ thị và các khái niệm liên quan
- Trình bày các định lý về việc tô màu của đồ thị (định lý 3.3, định lý 3.4)
- Sưu tầm một hệ thống bài toán về đồ thị và tô màu cùng một hệ thống lời giải chi tiết
- Trình bày khái niệm mạng lưới ô vuông, điểm nguyên
- Trình bày định lý Ricard, định lý Minkowki cùng chứng minh chi tiết.
- Sưu tầm hệ thống các bài toán về mạng lưới ô vuông, điểm nguyên, các bài toán liên quan đến các định lý cùng hệ thống lời giải chi tiết
Bài viết này trình bày một số kết quả từ khoá luận mang tên “Một số vấn đề về đồ thị và mạng lưới ô vuông” Mặc dù đã nỗ lực nghiên cứu, nhưng do thời gian hạn chế và khó khăn trong việc tìm kiếm tài liệu, đề tài vẫn còn nhiều thiếu sót Tôi rất mong nhận được ý kiến đóng góp từ các thầy cô giáo và bạn đọc để hoàn thiện hơn Hy vọng luận văn này sẽ trở thành tài liệu tham khảo hữu ích cho sinh viên muốn tìm hiểu về vấn đề này.
[1] Vũ Hữu Bình (2005), Các bài toán hình học tổ hợp NXB GD
[2] Vũ Đình Hòa (2000), Một số kiến thức về hình học tổ hợp, NXB GD,
[3] Vũ Đình Hòa (2001), Định lý và vấn đề về đồ thị hữu hạn NXB
[4] Vũ Đình Hòa (2002), Lý thuyết tổ hợp và các bài toán ứng dụng, NXB
[5] Vũ Đình Hòa (2002), Một số kiến thức cơ sở về Graph hữu hạn, NXB GD, Đà Nẵng
1.1 Các khái niệm cơ bản 3
1.1.2 Một số khái niệm liên quan về đồ thị 3
1.3 Bài toán tô màu các cạnh 8
1.3.2 Số Rensey của đồ thị đủ 9
1.3.5 Một số bài toán liên quan 11
Chương II MẠNG LƯỚI Ô VUÔNG VÀ ĐIỂM NGUYÊN 17
2.1.2 Các bài toán liên quan 17
2.2 Các điểm toạ độ nguyên trong mặt phẳng 22
2.2.3 Các bài toán liên quan 24
2.3.3 Một số bài toán liên quan 31
2.4 Phủ hình bằng mạng lưới ô vuông 33
