Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Hóa học Skkn lý thuyết đồ thị và ứng dụng ...

Tài liệu Skkn lý thuyết đồ thị và ứng dụng

.PDF
21
1093
71

Mô tả:

Lý thuyết đồ thị và ứng dụng LỜI NÓI ĐẦU. Lý thuyết đồ thị có vai trò rất quan trọng trong giải các bài toán khó, bài toán không mẫu mực. Nhằm bồi dưỡng tư duy toán học cho học sinh, tôi xin giới thiệu một vài kiến thức cơ bản về lý thuyết đồ thị và các ứng dụng của nó trong các bài toán không mẫu mực. Để giải toán thông qua đồ thị ta cần thực hiện theo hai bước: - Xây dựng đồ thị để mô tả các quan hệ, điều kiện được phát biểu trong bài toán. - Căn cứ vào các kết quả của lý thuyết đồ thị để suy ra đáp án. Bản thân tuy đã cố gắng nhiều nhưng chắc chắn vẫn còn những sai sót, tôi mong được sự góp ý của quý đồng nghiệp. Người viết Huỳnh Công Tráng Huỳnh Công Tráng Trang 1 Lý thuyết đồ thị và ứng dụng I. CÁC KHÁI NIỆM CƠ BẢN 1. Định nghĩa đồ thị. Tập hợp X   các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được ký hiệu bằng G(X,E) (hoặc G = (X, E) hoặc bằng G(X)) Các phần tử của X được gọi là các đỉnh. Cặp đỉnh không sắp thứ tự gọi là cạnh, cặp đỉnh sắp thứ tự gọi là cạnh có hướng hay cung. Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, còn đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung thì nó được gọi là đồ thị hỗn hợp hay đồ thị hỗn tạp Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh (hai hay nhiều hơn hai cung cùng một hướng). Các cạnh (cung) này gọi là các cạnh (cung) bội. Một cung (hay một cạnh) có thể bắt đầu và kết thúc tại cùng một đỉnh. Cung hay cạnh loại này được gọi là khuyên hay nút. Cặp đỉnh x, y được nối với nhau bằng cạnh (cung) a, thì x, y được gọi là các đỉnh hay hai đầu của cạnh (cung) a và a được gọi là cạnh (cung) thuộc đỉnh x, đỉnh y. Nếu cung b xuất phát từ đỉnh u đi vào đỉnh v, thì u được gọi là đỉnh đầu, còn v được gọi là đỉnh cuối của cung b. Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu x khác y và là hai đầu của cùng một cạnh hay một cung. Đối với mọi đỉnh x dùng D(x) để chỉ tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh; D+(x) để chỉ tập đỉnh, mà mỗi đỉnh này từ x có cung đi tới; D-(x) để chỉ tập đỉnh mà mỗi đỉnh này có cung đi tới x Hai cạnh (cung) a, b được gọi là kề nhau, nếu - Chúng khác nhau - Chúng có đỉnh chung (nếu a, b là cung, thì không phụ thuộc vào đỉnh Huỳnh Công Tráng Trang 2 Lý thuyết đồ thị và ứng dụng chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của cung b) 2. Một số dạng đồ thị đặc biệt. Trong những trường hợp không cần phân biệt giữa cạnh và cung ta quy ước dùng cạnh thay cho cả cung. Đồ thị G(X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường được gọi là đồ thị. Đồ thị G(X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị. Đồ thị vô hướng (có hướng) G(X, E) được gọi là đồ thị - đầy đủ, nếu mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (một cung với chiều tùy ý). Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) hai mảng nếu tập đỉnh X của nó được phân thành hai tập con rời nhau X1; X2  X1  X 2  X , X1  X 2   và mỗi cạnh đều có một đầu thuộc X1, còn đầu kia thuộc X2. Khi đó G(X, E) còn được ký hiệu bằng G(X1; X2; E) 3. Bậc của đỉnh. Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng hoặc không có hướng. Số cạnh và cung thuộc đỉnh x được gọi là bậc của đỉnh x và ký hiệu bằng m(x) 4. Một số tính chất. a. Tính chất 1. Trong một đồ thị hay đa đồ thị tùy ý, tổng số bậc của tất cả các đỉnh bao giờ cũng gấp đôi số cạnh Chứng minh. Thật vậy, khi tính bậc của các đỉnh mỗi cạnh vô hướng hoặc có hướng đều được tính mỗi đầu đúng một lần, nên ta có tính chất 1 đúng. b. Tính chất 2. Trong một đồ thị hay đa đồ thị tùy ý số đỉnh bậc lẻ luôn luôn là một số chẵn. Chứng minh. Giả sử đồ thị (đa đồ thị) G(X,E) có n đỉnh, m cạnh Huỳnh Công Tráng Trang 3 Lý thuyết đồ thị và ứng dụng X  x1; x2 ;...; xk ; xk 1;...; xn1; xn  Các đỉnh x1 , x2 ,..., xk bậc lẻ và xK 1 , xk 2 ,..., xn1; xn bậc chẵn. Theo tính chất 1 ta có m( x1 )  m( x2 )  ...  m( xk )  m( xk 1 )  m( xk  2 )  ...  m( xn1 )  m( xn )  2.m A B Vì B là tổng các số chẵn, nên B là một số chẵn. Do đó A = 2.m - B phải là một số chẵn Số chẵn A là tổng của k số lẻ, nên k phải chẵn. Bởi vậy số đỉnh bậc lẻ trong đồ thị hay đa đồ thị bất kỳ phải là một số chẵn. c. Tính chất 3. Trong một đồ thị với n ( n  2 ) đỉnh có ít nhất hai đỉnh cùng bậc Chứng minh. Giả sử G(X, E) là đồ thị tùy ý với X  n  2 . Xét hai khả năng: - Nếu đồ thị có đỉnh bậc 0, thì trong đồ thị không có một đỉnh nào kề với tất cả các đỉnh còn lại, nên mỗi đỉnh của đồ thị có bậc là một trong n – 1 số nguyên: 0;1;2;3;...; n-3; n-2 - Nếu đồ thị có đỉnh bậc n – 1, thì đồ thị không có đỉnh bậc 0. Bởi vậy bậc của mỗi đỉnh thuộc đồ thị là một trong n- 1 số nguyên 1; 2; ....; n-2; n-1. Từ kết quả trên khẳng định được rằng, đồ thị G(X, E) với n đỉnh, nhưng chỉ có không quá n-1 loại bậc. Do đó phải có ít nhất hai đỉnh cùng bậc. Khẳng định được chứng minh d. Tính chất 4. Nếu đồ thị với n ( n>2) đỉnh có đúng hai đỉnh cùng bậc thì hai đỉnh này không thể đồng thời có bậc 0 hoặc n-1. Chứng minh: Giả sử hai đỉnh x, y là hai đỉnh cùng bậc của đồ thị G(X, E) và đều có bậc 0 hoặc bậc n-1. Loại x, y và tất cả các cạnh thuộc chúng khỏi đồ thị G ta được đồ thị con G1 có n -2 đỉnh. Theo tính chất 3 trong G1 có hai đỉnh cùng bậc, chẳng hạn u, v. Huỳnh Công Tráng Trang 4 Lý thuyết đồ thị và ứng dụng - Nếu x, y cùng bậc 0, thì u,v trong G không kề với x, y nên u, v đồng thời 2 đỉnh cùng bậc trong đồ thị G. Như vậy, đồ thị G phải có ít nhất 2 cặp đỉnh cùng bậc - Nếu x, y đều có bậc n- 1. Khi đó, mỗi đỉnh u,v đều kề đồng thời với x, y nên trong đồ thị G các đỉnh u,v cũng cùng bậc. Như vậy, trong đồ thị G phải có ít nhất 2 cặp đỉnh cùng bậc. Cả hai trường hợp có thể đều dẫn đến mâu thuẫn với tính chất: Đồ thị G có duy nhất một cặp đỉnh cùng bậc, nên x, y không thể cùng bậc 0 hoặc cùng bậc n- 1. Khẳng định được chứng minh. e. Tính chất 5. Số đỉnh bậc n-1 trong đồ thị G với n ( n  4 ) đỉnh, mà 4 đỉnh tùy ý có ít nhất một đỉnh kề với 3 đỉnh còn lại, không nhỏ hơn n- 3 Chứng minh: - Nếu G đầy đủ, thì khẳng định trên đúng - Nếu G có cặp đỉnh duy nhất không kề nhau. Khi đó trong G có n- 2 đỉnh bậc n- 1 - Nếu G có hai cặp đỉnh không kề nhau, thì chúng phải có đỉnh chung. Thật vậy, giả sử A, B, I, D là hai cặp đỉnh không kề nhau. Nếu hai cặp đỉnh này không có đỉnh chung, thì trong 4 đỉnh A, B, I, D không có đỉnh nào kề với ba đỉnh còn lại, như vậy mâu thuẫn với giả thiết, nên hai cặp A, B; I, D phải có hai đỉnh trùng nhau chẳng hạn B trùng I Lấy đỉnh C tùy ý khác với A, B, D. Trong bộ bốn A, B, C, D đỉnh C kề với ba đỉnh A, B, D Loại D ra khỏi bộ bốn trên và thay vào đó là đỉnh E tùy ý khác với A, B, C, D. Trong bộ bốn A, B, C, E hoặc C hoặc E phải kề với ba đỉnh còn lại, nếu E kề với ba đỉnh còn lại, thì C kề với E. Do đó C kề với cả ba đỉnh A, B, E. Do E là đỉnh tùy ý trong n- 4 đỉnh còn lại ( khác các đỉnh A, B, C) nên C có bậc n-1. Do C là đỉnh tùy ý trong n – 3 đỉnh khác A, B, D nên đồ thị có n -3 đỉnh bậc n -1. Khẳng định được chứng minh. Huỳnh Công Tráng Trang 5 Lý thuyết đồ thị và ứng dụng f. Tính chất 6. Với mọi số tự nhiên n ( n > 2), luôn tồn tại đồ thị n đỉnh mà 3 đỉnh bất kỳ của đồ thị đều không cùng bậc. Chứng minh: Với n = 3 đồ thị G3 gồm 1 đỉnh bậc 0 và hai đỉnh bậc 1. Giả sử khẳng định đúng với đồ thị Gn có n đỉnh. Đồ thị Gn+1 có n +1 đỉnh được xây dựng như sau: - Nếu Gn có đỉnh bậc n- 1, thì không có đỉnh bậc 0, nếu ta ghép vào Gn đỉnh x bậc 0 và được Gn+1 gồm n +1 đỉnh việc ghép thêm đỉnh x vẫn bảo toàn tính chất của Gn: ba đỉnh bất kỳ đều không cùng bậc và đồ thị Gn không có đỉnh bậc 0, nên trong Gn+1 ba đỉnh bất kỳ đều không cùng bậc. - Nếu Gn không có đỉnh bậc n -1. Khi đó tất cả các đỉnh của Gn đều có bậc không vượt quá n -2. Thêm vào Gn đỉnh x (không thuộc Gn) và nối x với từng đỉnh của Gn bằng một cạnh được đồ thị Gn+1 có n +1 đỉnh. Đỉnh x có bậc bằng n, còn bậc của mỗi đỉnh thuộc Gn trong Gn+1 được tăng lên một đơn vị nhưng đều không vượt quá n- 1 và trong bậc mới ba đỉnh bất kỳ của Gn vẫn không cùng bậc. Khẳng định được chứng minh. g. Tính chất 7. Đồ thị hai mảng G(Y,Z,E) với mọi đỉnh y thuộc Y đều có m( y)  1 , đồng thời có tính chất: bất kỳ hai cặp đỉnh y1; y2; z1; z2  nào cũng thỏa mãn điều kiện: Nếu y1 kề với z1; y2 kề với z2 thì trong hai cặp đỉnh y1,z2; y2,z1 có ít nhất một cặp đỉnh kề nhau. Khi đó trong tập Z có ít nhất một đỉnh kề với tất cả các đỉnh thuộc Y. Chứng minh: Ký hiệu Y  m, Z  n . Xét ba khả năng sau: *) m =1: Do Y có phần tử duy nhất y, mà m( y)  1 , trong tập Z có ít nhất phần tử z kề với y. Do đó m( z )  1  Y *) m > 1, n = 1 theo giả thiết với mọi y thuộc Y đều có m( y)  1 nên đỉnh z duy nhất của tập Z phải kề với tất cả các đỉnh thuộc Y hay m( z )  Y . *) m > 1, n >1. Gọi z là đỉnh có bậc lớn nhất trong tập Z. +) Nếu m( z )  Y khẳng định được chứng minh Huỳnh Công Tráng Trang 6 Lý thuyết đồ thị và ứng dụng +) Giả sử m( z)  k  m  Y . Ký hiệu y1; y2; …;yk là các đỉnh kề với z và yk+1 phải kề với đỉnh t  Z , t  z . Xét hai cặp đỉnh ( z; yi ),(t , yk 1 ) với i = 1;2;…;k. ngoài ra t còn kề với yk+1, nên m(t )  k  1  k  m( z ) . Điều này mâu thuẫn với giả thiết m(z) cực đại. Khẳng định dược chứng minh. h) Tính chất 8. Trong đồ thị G(X, E) với ít nhất kn +1 đỉnh, mỗi đỉnh có bậc không nhỏ hơn (k -1)n +1, luôn luôn tồn tại đồ thị con đầy đủ gồm k +1 đỉnh. Chứng minh. Chứng minh bằng quy nạp. Với k =1, khẳng định trên đúng Với k = 2 có thể làm chặt hơn giả thiết: Nếu đồ thị 2n +1 đỉnh, mà mỗi đỉnh có bậc không nhỏ hơn n, thì có đồ thị con 3 đỉnh đầy đủ. Thật vậy, xét đỉnh x tùy ý, còn y là một trong các đỉnh kề với x. Tổng số đỉnh kề với x và y không nhỏ hơn 2n, nhưng số đỉnh khác x và y chỉ là 2n -1. Vậy phải có ít nhất 1 đỉnh z được tính 2 lần. Khi đó, x, y, z tạo thành một đồ thị con đầy đủ 3 đỉnh Giả sử, khẳng định đúng với k. Cần chứng minh khẳng định đúng với k + 1. Theo giả thiết, trong đồ thị G gồm (k+1)n +1 đỉnh, số đỉnh kề với đỉnh x tùy ý không nhỏ hơn kn + 1, nên số đỉnh của G không kề với x sẽ không vượt quá n. Bởi vậy, mỗi đỉnh y kề với x, thì nó kề với nhiều nhất n đỉnh không kề với đỉnh x. Do đó đỉnh y phải kề với ít nhất kn +1 – n = (k-1)n+1 đỉnh kề với x. Xét đồ thị con G1 gồm các đỉnh kề với x. Đồ thị con G1 có ít nhất kn +1 đỉnh và mỗi đỉnh của nó kề với ít nhất (k -1)n +1 đỉnh thuộc G1, nên theo giả thiết quy nạp, trong G1 có đồ thị con đầy đủ G2 gồm k+1 đỉnh. Vì đỉnh x kề với từng đỉnh thuộc G2, nên đỉnh x kết hợp với các đỉnh thuộc G2 lập thành một đồ thị đầy đủ gồm k+2 đỉnh trong đồ thị G Khẳng định được chứng minh. Huỳnh Công Tráng Trang 7 Lý thuyết đồ thị và ứng dụng II. Ứng dụng các tính chất trên Bài 1. Chứng minh rằng trong một lớp học tùy ý số học sinh mà mỗi người có một số lẻ bạn thân trong lớp, luôn luôn là một số chẵn. Bài 2. Chứng minh rằng số người mà mỗi người đã có một số lẻ lần bắt tay trên trái đất là một số chẵn. Bài 3. Chứng minh rằng trong một cuộc họp tùy ý gồm từ 2 đại biểu trở lên, luôn luôn có ít nhất 2 đại biểu, mà họ có số người quen bằng nhau trong các đại biểu đến dự họp. Bài 4. Chứng minh rằng nếu trong một nhóm tùy ý gồm ít nhất ba người, mà có đúng hai người có số người quen bằng nhau, thì họ không thể đồng thời không quen ai hoặc đồng thời quen tất cả những người còn lại ttrong nhóm. Bài 5. Một cuộc hội thảo quốc tế với n,(n  4) đại biểu tham gia. Cứ bốn đại biểu đến dự có ít nhất một người nói chuyện trực tiếp được với ba người còn lại. Chứng minh rằng có ít nhất n -3 đại biểu mà mỗi người có thể nói chuyện trực tiếp với tất cả những người còn lại. Bài 6. Chứng minh rằng với mọi số tự nhiên n(n  2) luôn luôn tìm được một nhóm gồm n người, mà ba người bất kỳ trong nhóm đều không có số người quen bằng nhau. Bài 7. Hai xã A, B ở cạnh nhau. Mỗi gia đình ở xã A quen với ít nhất một gia đình ở xã B, đồng thời bất kỳ hai gia đình y1, y2 nào thuộc xã A, hai gia đình túy ý z1; z2 thuộc xã B cùng thỏa mãn điều kiện: Nếu gia đình y1 quen với gia đình z1, gia đình y2 quen với gia đình z2 thì trong hai cặp gia đình y1,z2; y2,z1 có ít nhất một cặp gia đình quen nhau. Chứng minh rằng trong xã B có ít nhất một gia đình quen với tất cả các gia đình thuộc xã A Bài 8. Chứng minh rằng trong một quần đảo tùy ý gồm kn + 1 hòn đảo (k, n là các số nguyên dương) và mỗi hòn đảo có đường ngầm nối với ít nhất (k-1)n +1 hòn đảo thuộc quần đảo này, luôn luôn tồn tại một nhóm gồm k+1 hòn đảo, mà mỗi hòn đảo có đường hầm đi đến từng hòn đảo thuộc nhóm. Huỳnh Công Tráng Trang 8 Lý thuyết đồ thị và ứng dụng Để giải các bài toán trên trước hết ta chuyển chúng về các bài toán trên đồ thị, rồi dựa vào các tính chất để suy ra kết luận trong các bài toán tương ứng. Bài 1. Xây dựng đồ thị G. - Đỉnh: Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các học sinh trong lớp, đồng thời dùng luôn mã số của các em, để ghi trên các điểm tương ứng. - Cạnh: Trong đồ thị G các đỉnh x, y được nối bằng một cạnh khi và chỉ khi hai học sinh x, y thân nhau. Với cách xây dựng đồ thị như trên, bậc của mỗi đỉnh thuộc G bằng đúng số người quen của học sinh tương ứng với đỉnh này. Theo tính chất 2 số đỉnh bậc lẻ trong G là một số lẻ, nên số học sinh mà mỗi người có một số lẻ bạn thân trong lớp phải là một số chẵn. Các bài tập 2, 3, 4, 5, 6, 7, 8 giải tương tự nhờ các tính chất c,d,e,f,g,h. III. Xích, chu trình, sắc số và đồ thị màu. 1. Xích, chu trình. Giả sử G(X, E) là một đồ thị hay đa đồ thị vô hướng. Dãy  các đỉnh của G(X, E):    x1 , x2 ,..., xi ; xi 1 ,..., xn1 , xn  được gọi là một xích hay một dây chuyền, nếu i (1  i  n 1) cặp đỉnh xi , xi 1 kề nhau. Các đỉnh x0; xn được gọi là hai đỉnh đầu của xích  . Một xích với hai đầu trùng nhau, được gọi là một chu trình. Xích (chu trình)  , được gọi là xích (chu trình) đơn (sơ cấp hay cơ bản), nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần. 2. Sắc số và đồ thị màu. a. Định nghĩa: Cho trước một số nguyên dương p. Ta nói rằng đồ thị G là p sắc, nếu bằng p màu khác nhau có thể tô trên các đỉnh (mỗi đỉnh một màu), sao cho hai đỉnh kề nhau tùy ý đều có màu khác nhau. Huỳnh Công Tráng Trang 9 Lý thuyết đồ thị và ứng dụng b. Sắc số: Số p nhỏ nhất, mà đối với số đó đồ thị G là p sắc, được gọi là sắc số của đồ thị G và ký hiệu bằng  (G) . Nói một cách khác, sắc số của một đồ thị là số màu ít nhất cần dùng để tô trên các đỉnh của đồ thị (mỗi đỉnh một màu), sao cho hai đỉnh kề nhau tùy ý được tô bằng hai màu khác nhau. c. Sắc lớp: Số màu ít nhất cần dùng để tô trên các cạnh của đồ thị (mỗi cạnh một màu), sao cho hai cạnh kề nhau tùy ý đều có màu khác nhau. 3. Lớp đồ thị có chu trình tam giác cùng màu. Để phục vụ cho việc giải quyết một lớp các bài toán nào đó cần xem xét những dãy số đặc biệt và đưa ra các khẳng định thích hợp, chẳng hạn, để xây dựng một lớp đồ thị có chu trình tam giác cùng màu người ta đưa ra các dãy số nguyên dương: a1  2; a2  5;...; an1  (n  1)an  1 b2  3; b3  6;...; bn1  (bn  1)n  2 a) Khẳng định 1. Một đồ thị đầy đủ vô hướng với an + 1 đỉnh, các cạnh được tô bằng n màu luôn có chu trình tam giác cùng màu. Chứng minh bằng quy nạp Khi n =1. Đồ thị đầy đủ tương ứng gồm a1 +1 = 2+1 =3 đỉnh lập thành một chu trình tam giác. Các cạnh của đồ thị này được tô bằng một màu, nên chu trình tam giác lập nên G1 cùng màu. Giả sử khẳng định đúng với n = k, nghĩa là, đồ thị đầy đủ bất kỳ Gk gồm ak+1 đỉnh với các cạnh được tô bằng k màu đã có chu trình tam giác cùng màu. Cần chứng minh khẳng định đúng với n = k+1 Xét đồ thị đầy đủ tùy ý Gk+1 với ak+1 + 1 đỉnh và các cạnh được tô bằng k+1 màu. Giả sử P là một đỉnh tùy ý của Gk+1. Khi đó P được nối với ak+1=(k+1)ak + 1 đỉnh bằng các cạnh được tô bằng không quá k +1 màu, nên xuất phát từ P phải có ít nhất ak + 1 cạnh được tô cùng một màu. Giả sử màu này là màu đỏ và các cạnh PA1; PA2; ...; PAa ; PAa 1 được tô màu đỏ. Có hai khả năng xảy ra: k Huỳnh Công Tráng k Trang 10 Lý thuyết đồ thị và ứng dụng - Nếu một trong các cạnh nối giữa Ai; Aj 1  i, j  ak  1 được tô màu đỏ, chẳng hạn (A1,A2) màu đỏ. Khi đó chu trình tam giác A1PA2 màu đỏ, nên đồ thị Gk+1 có chu trình tam giác màu đỏ. - Trường hợp ngược lại, không có cạnh nào trong các cạnh(AiAj) 1  i, j  ak  1 được tô màu đỏ, Khi đó tồn tại đồ thị con đầy đủ Gk với tập đỉnh {A1; A2 ;...; Aak ; Aa } có các cạnh được tô bằng không quá k màu, nên theo giả k 1 thiết quy nạp Gk có chu trình tam giác cùng màu. Bởi vậy Gk+1 có chu trình tam giác cùng màu b) Khẳng định 2. Một đồ thị đầy đủ vô hướng với bn+1 đỉnh, các cạnh được tô bằng n màu luôn luôn có chu trình ta giác cùng màu. Chứng minh bằng quy nạp 4. Các ví dụ. a.Ví dụ 1. Trên mặt phẳng lấy 6 điểm, không có ba điểm nào thẳng hàng, khoảng cách giữa các cặp điểm khác nhau từng đôi một. Chứng minh rằng tồn tại ít nhất một cặp điểm, mà đoạn thẳng nối giữa chúng là cạnh ngắn nhất thuộc một tam giác nào đó, đồng thời là cạnh dài nhất của một tam giác khác trong các tam giác có đỉnh là các điểm đã cho? Giải. Để giải bài toán trên trước hết dùng màu xanh để tô mỗi đoạn thẳng là cạnh ngắn nhất của một tam giác nào đó trong các tam giác có đỉnh là các điểm đã cho. Phần còn lại được tô màu đỏ. Khi đó được đồ thị G gồm 6 đỉnh, các cạnh được tô bằng hai màu. Theo khẳng định 1, đồ thị G có chu trình tam giác cùng màu. Do khoảng cách giữa các cặp điểm đã cho khác nhau từng đôi một nên tam giác bất kỳ với đỉnh là các điểm đã cho đều có cạnh ngắn nhất mà cạnh này được dùng màu xanh để tô trước. Bởi vậy chu trình tam giác cùng màu phải là tam giác xanh. Khi đó cạnh dài nhất trong tam giác này chính là đoạn thẳng cần tìm. Huỳnh Công Tráng Trang 11 Lý thuyết đồ thị và ứng dụng b.Ví dụ 2. Mười bảy nhà khoa học đến dự hội nghị quốc tế, mỗi người trong số họ chỉ biết một trong ba ngoại ngữ: Anh, Nga, Pháp. Chứng minh rằng có ít nhất ba nhà khoa học cùng biết một trong ba ngoại ngữ nói trên. Giải. Lấy 17 điểm, không có ba điểm nào thẳng hàng và tương ứng với 17 nhà khoa học đến dự họp. Đoạn thẳng nối giữa hai điểm tương ứng với hai nhà khoa học. Cùng biết tiếng Anh được tô màu xanh Cùng biết tiếng Nga được tô màu đỏ Cùng biết tiếng Pháp được tô màu vàng. Khi đó được đồ thị G3 gồm 17 đỉnh, các cạnh được tô bằng 3 màu, nên theo khẳng định 2 tương ứng với n = 3, đồ thị G 3 có chu trình tam giác cùng màu. Do đó ba nhà khoa học tương ứng với ba đỉnh thuộc chu trình này biết cùng một ngoại ngữ. IV. Một số bài tập khác. Bài 1. Trong một cuộc thi đấu bóng bàn An và Bình quy ước với nhau: Người thắng cuộc là người đầu tiên thắng ba ván hoặc thắng hai ván liên tiếp. Hãy xác định số khả năng có thể xảy ra? Giải. Dùng A để ký hiệu An thắng, B để ký hiệu Bình thắng Dùng cây đồ thị để mô tả toàn bộ hiện trạng có khả năng xảy ra. Xây dựng cây: Xuất phát từ đỉnh S Ván đầu tiên có hai khả năng: An thắng hoặc Bình thắng, nên lấy hai điểm sao cho hai điểm này với S không thẳng hang. Một trong hai điểm này ghi A, còn điểm kia ghi B. Nối S với A bằng bằng một đoạn thẳng hoặc một đoạn cong để biểu thị A thắng. Tương tự để biểu thị B thắng nối S với B bằng một đoạn thẳng hoặc một đoạn cong. Ván thứ hai lại có hai khả năng: An thắng hoặc Bình thắng nên xuất phát từ A cũng lấy hai điểm mới và ghi các ký hiệu tương ứng A, B và từ A kẻ hai đoạn thẳng hoặc hai đoạn cong tới hai điểm mới them. Đối với điểm B cũng chọn Huỳnh Công Tráng Trang 12 Lý thuyết đồ thị và ứng dụng thêm hai đỉnh mới ghi A và B, rồi từ B kẻ hai đoạn thẳng hay hai đoạn cong đi tới hai điểm mới thêm. Tiếp tục thực hiện kéo dài các đường một cách tương tự, nhưng do quy ước của An và Bình những đường mà trên đó xuất hiện hoặc hai đỉnh liên tiếp ghi cùng bằng một ký hiệu hoặc có ba đỉnh được ghi bằng cùng một ký hiệu đều không được kéo dài A A A A A B B B B S B B B B B A A A A Hình 1 Vì An và Bình đấu với nhau 5 ván, thì hoặc có người thắng 2 ván liên tiếp hoặc có người thắng ba ván. Do đó những đường xuất phát từ S đều không có qua 5 cạnh (hình 1). Cây có 10 đỉnh ngọn, nên có 10 khả năng xảy ra. Bài toán 2. Trên đảo có một số cụm dân cư. Mỗi cum dân cư có hai đường lớn và ba đường mòn đi ra. Mỗi đường lớn cũng như đường mòn đều dẫn tới một cụm dân cư khác. Hai cụm dân cư khác nhau bất kỳ được nối liền bằng hoặc đường lớn hoặc đường mòn. Hỏi trên đảo này có bao nhiêu đường mòn bao nhiêu đường lớn? Giải. Trước hết ta cần khẳng định rằng trên đảo có 6 cụm dân cư. Thật vậy, mỗi cụm dân cư ta biểu diễn bằng một điểm. Hai cụm dân cư có đường lớn (đường mòn) nối với nhau, thi hai cụm tương ứng được nối bằng một đường nét liền (đường nét đứt). Vì xuất phát từ mỗi cụm dân cư có hai Huỳnh Công Tráng Trang 13 Lý thuyết đồ thị và ứng dụng đường lớn và ba đường mòn đi ra, nên xuất phát từ mỗi điểm đã chọn chẳng hạn A, có hai đường nét liền và ba đường nét đứt. Bởi vậy với mỗi điểm đã chọn (A) được nối với các điểm khác B, C, D, E, F bằng một đường nét liền hay một đường nét đứt. Như vậy phải có ít nhất 6 cụm dân cư (6 điểm đã chọn). Mặt khác hai cụm dân cư tùy ý đều phải có đường nối với nhau nên mỗi điểm chỉ có thể nối tới với 5 điểm. Do đó không còn điểm nào ngoài 6 điểm A, B, C, D, E, F. Bởi vậy có 6 đường lớn và 9 đường nhỏ Căn cứ vào yêu cầu bài toán có thể đơn cử một vài khả năng xảy ra như sau: A A F B E C F B E C D D Bài toán 3. Trong một giải bóng đá có 4 đội Anh, Đan Mạch, Hà Lan; Thụy Điển vào bán kết. Có các dự đoán xếp hạng như sau - Đan Mạch vô địch, Thụy Điển nhì - Đan Mạch nhì, Hà Lan ba - Anh nhì, Hà Lan tư. Kết quả là mỗi dự đón đúng được một đội. Hãy cho biết kết quả xếp hạng của các đội? Giải. Dùng xi để ký hiệu đội x được xếp hạng i (1  i  4) Ta vẽ cây, hai nhánh đầu tiên ứng với dự đón thứ nhất là Đ1, T2 Từ mỗi nhánh này lại có hai nhánh ứng với dự đón thứ hai. Tiếp tục rẽ nhánh ứng với dự đón thứ ba Ta chọn đường đi từ gốc O tới các điểm thỏa mãn các điều kiện: - Một đội không thể được xếp hai hạng khác nhau. - Hai đội không thể xếp cùng một hạng. Huỳnh Công Tráng Trang 14 Lý thuyết đồ thị và ứng dụng Suy ra chỉ có đường đi Đ1H3A2 thỏa mãn Đường tô đậm Đ1H3A2 thỏa mãn điều kiện mỗi dự đón đúng được một đội mà thứ tự ghi trên đường Vậy kết quả xếp hạng như sau: Đan Mach vô địch; Anh nhì; Hà Lan ba; Thụy Điển tư A2 A2 H4 A2 H4 A2 H4 Đ2 H3 H4 T2 Đ2 H3 Đ1 O Bài toán 4. Một quần đảo có 2n(n  1) hòn đảo. Mỗi hòn đảo có đường ngầm nối trực tiếp với ít nhất n hòn đảo khác. Chứng minh rằng từ một hòn đảo bất kỳ thuộc quần đảo đều có thể đi tới bất kỳ hòn đảo nào thuộc quần đảo này bằng đường ngầm. Giải. *) Xây dựng đồ thị mô tả các quan hệ Đỉnh: Lấy 2n điểm tương ứng với 2n hòn đảo. Dùng ngay tên các hòn đảo để ghi các điểm tương ứng. Cạnh: Cặp điểm x, y được nối bằng một đoạn thẳng hoặc một đọan cong không đi qua các điểm trung gian khác khi và chỉ khi hai hòn đảo tương ứng có đường ngầm nối với nhau. Đồ thị nhận được ký hiệu bằng G. Nó mô tả toàn bộ mối liên hệ bằng đường ngầm của quần đảo. *) Suy ra bài giải. Huỳnh Công Tráng Trang 15 Lý thuyết đồ thị và ứng dụng Đối với mỗi đỉnh x của đồ thị G số cạnh xuất phát từ nó bằng đúng số đường ngầm xuất phát từ hòn đảo tương ứng. Bởi vậy, bậc của mỗi đỉnh không nhỏ hơn n, nên tổng bậc của hai đỉnh tùy ý không nhỏ hơn số đỉnh của đồ thị (2n). Khi đó, hai đỉnh tùy ý x, y của đồ thị G có đường nối với nhau. Mặt khác, mỗi cạnh của đường này biểu thị một đường ngầm nối trực tiếp giữa hai hòn đảo, nên đường nối giữa hai điểm x, y biểu thị đường ngầm nối giữa hai hòn đảo tương ứng với x và y. Do đó từ hòn đảo bất kỳ đều có thể đi bằng đường ngầm tới từng hòn đảo còn lại. Bài 5. Trong một cuộc họp có đúng hai đại biểu không quen nhau và mỗi đại biểu này có một số lẻ người quen đến dự. Chứng minh rằng luôn luôn có thể xế một số đại biểu chen giữa hai đại biểu nói trên, để mỗi người ngồi giữa hai người mà anh (chị ) ta quen. Giải. *) Xây dựng đồ thị mô tả các quan hệ Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các đại biểu đến dự hội nghị. Dùng ngay tên các đại biểu để ghi trên các điểm tương ứng. Hai điểm tùy ý x, y được nối bằng một đoạn thẳng khi và chỉ khi các đại biểu x, y quen nhau. Đồ thị nhận được ký hiệu bằng G. *) Suy ra bài giải. Hai đại biểu hông quen nhau, thì hai đỉnh tương ứng không kề nhau. Mỗi đại biểu này lại có một số lẻ người quen đến họp, nên trong đồ thị G có đúng hai đỉnh bậc lẻ và hai đỉnh này lại không kề nhau. Khi đó thì hai đỉnh này lien thong, nên có ít nhất một đường nối giữa hai đỉnh bậc lẻ này. Giả sử d là một trong những đường nối giữa hai đỉnh bậc lẻ đó. Dựa vào d ta sắp xếp các đại biểu tương ứng ngồi giữa hai đại biểu của hai đỉnh bậc lẻ, thì mỗi đại biểu này sẽ ngồi giữa hai người mà anh (chị) ta quen. Huỳnh Công Tráng Trang 16 Lý thuyết đồ thị và ứng dụng Bài tập Bài 1. Để mừng con đạt giải trong kỳ thi toán quốc gia. Một gia đình dự định mời tiệc. Trong số khách mời: a) Người chồng muốn có ít nhất ba người từng đôi một quen nhau. b) Người vợ lại muốn có ít nhất 4 người từng đôi một chưa quen nhau. Hỏi họ phải mời bao nhiêu bạn, để mong muốn của chồng hoặc vợ được thỏa mãn. Bài 2. Cho 6 số nguyên dương tùy ý. Chứng minh rằng luôn có thể chọn ra được 2 bộ 3 số mà trong mỗi bộ, từng đôi một đều là nguyên tố cùng nhau hoặc đều không là nguyên tố cùng nhau. Bài 3. Có 20 đội bóng thi đấu với nhau, mỗi đội phải đấu một trận với các đội khác. Chứng minh rằng vào bất cứ lúc nào cũng có hai đội đã đấu một số trận như nhau? Bài 4. Có 16 em thi đấu bóng bàn. Theo lịch mỗi em phải thi đấu với các bạn khác một trận. Hiện nay mỗi em thi đấu 11 trận. Chứng minh rằng, khi đó tìm được 4 em mà mỗi em đều đã đấu với ba em còn lại. Bài 5. Có n số tự nhiên tùy ý  n  3 mỗi số đều có ước chung với ít nhất 2 số. Chứng minh rằng có thể ghi một phần của tập số này lên một vòng tròn để mỗi số có ước chung với hai số bên cạnh. Bài 6. Cho 7 điểm trên mặt phẳng, không có ba điểm nào thẳng hàng. Một số cặp điểm được nối với nhau bằng các đoạn thẳng. Dùng n để chỉ số đoạn thẳng đã nối giữ các cặp điểm. Mỗi đoạn thẳng được tô bằng màu xanh hoặc màu đỏ. Tìm giá trị nhỏ nhất của n, sao cho với mọi cách tô màu cho n đoạn thẳng đã nối luôn luôn tồn tại một tam giác có các cạnh cùng màu. Bài 7. Một cuộc họp có ít nhất 3 đại biểu đến dự, mỗi người quen ít nhất hai đại biểu khác, chứng minh rằng có thể xếp được một số đại biểu ngồi xung quanh một bàn tròn để mỗi người ngồi giữa hai đại biểu mà người ấy quen. Bài 8. Trong thành phố có một số tuyến xe buýt thỏa mãn với các điều kiện san: Trên mỗi tuyến có ba bến đỗ. Hai tuyến bất kỳ có chung duy nhất một Huỳnh Công Tráng Trang 17 Lý thuyết đồ thị và ứng dụng bến đỗ. Từ bến này sang bến bất kỳ khác có thể đi bằng một xe buýt mà không phải chuyển xe. Hỏi có bao nhiêu tuyến xe buýt và bao nhiêu bến đỗ. Huỳnh Công Tráng Trang 18 Lý thuyết đồ thị và ứng dụng Kết luận. Rất nhiều bài toán không mẫu mực có thể giải bằng cách thông qua đồ thị mà suy ra đáp án. Phương pháp này gọi là phương pháp graph (hay phương pháp đồ thị) Để giải bài toán thông qua đồ thị ta cần thực hiện theo hai bước: - Xây dưng đồ thị để mô tả các quan hệ, điều kiện được phát biểu trong bài toán - Căn cứ vào kết quả của lý thuyết đồ thị để suy ra đáp án. Trong sáng kiến kinh nghiệm này, tôi xin giới thiệu một số khái niệm cơ bản về lý thuyết đồ thị, và một số kết quả vận dụng các kết quả đó vào giải một số bài toán không mẫu mực. Huỳnh Công Tráng Trang 19 Lý thuyết đồ thị và ứng dụng Tài liệu tham khảo. 1. Lý thuyết đồ thị và ứng dụng - Tác giả: Đặng Huy Ruận 2. Các đề thi vô địch toán các nước tập I, II, - Nguyễn Đễ - Nguyễn Khánh Nguyên (dịch) 3. Nguồn tài liệu trên Internet. Huỳnh Công Tráng Trang 20
- Xem thêm -

Tài liệu liên quan