Trên đồ thị có cạnh màu

49

Giới thiệu về biểu đồ
với sườn màu
L. Yu. Berezina

Nếu có một số điểm và một đường thẳng trên mặt phẳng, mỗi điểm đó nối một cặp điểm của chúng ta thì ta nói rằng có một đồ thị. Các điểm được gọi là các đỉnh của đồ thị và đường thẳng là các cạnh của nó. Các cạnh của đồ thị có thể được tô bằng nhiều màu, do đó nó được gọi là đồ thị có các cạnh được tô màu. Hình 1a hiển thị một đồ thị có năm đỉnh và các cạnh có hai màu. Biểu đồ này có thể được mô tả bằng các hình khác nhau, ví dụ: 16 và 1c*).

Bài viết này chỉ xem xét những biểu đồ trong đó mỗi

*) Thật vậy, một biểu đồ có các cạnh được tô màu có thể được chỉ định bằng một bảng có $n$ hàng và $n$ cột, trong đó $n$ là số đỉnh. Để thực hiện, bạn cần đánh số các đỉnh, tại giao điểm của hàng $i$ và cột thứ $j$ của bảng ghi màu của cạnh nối đỉnh $i$ và $j$. Dễ dàng tưởng tượng rằng có thể đánh số các đỉnh của đồ thị trong Hình 1a, 6 và c sao cho các bảng giống nhau. Đó là lý do tại sao chúng ta nói rằng đây là cùng một biểu đồ.

Cặp đỉnh này được nối với nhau bằng một cạnh. Đồ thị như vậy được gọi là hoàn chỉnh. Tuy nhiên, vì các biểu đồ khác không được xem xét ở đây nên chúng tôi sẽ không viết từ “hoàn thành” mọi lúc.

Việc sử dụng biểu đồ có các cạnh được tô màu sẽ đơn giản hóa lời giải của một số bài toán và làm cho chúng có ý nghĩa hơn.

Bây giờ chúng ta chuyển sang lời giải bài toán.

Nhiệm vụ 1. Sáu người đi xe đạp tham gia một ván cờ được chơi một vòng. Chứng minh rằng trong số họ sẽ luôn có một người tham gia Murire đã tổ chức tất cả các cuộc họp với nhau hoặc chưa gặp nhau của bất kỳ bên nào.

Lời giải. Bất kỳ hai người tham gia chuyến tham quan nào cũng luôn có một trong hai mối quan hệ với nhau: họ đã chơi một trò chơi với nhau hoặc chưa chơi. Chúng tôi chỉ định mỗi người tham gia một đỉnh của đồ thị. Nối các đỉnh theo cặp với các cạnh có hai màu

Cơm. 1a. Cơm. 16. Hình. Thế kỷ 1

50

Đồng chí Để cạnh màu đỏ là hai người đã chơi với nhau, còn cạnh màu xanh là chưa chơi. Chúng ta có một biểu đồ có sáu đỉnh và các cạnh có hai màu. Bây giờ với lời giải bài toán, chỉ cần chứng minh rằng trong đồ thị như vậy cần phải tìm một “tam giác” có các cạnh bằng một điểm là đủ.

Lưu ý rằng từ một đỉnh tùy ý của đồ thị của chúng ta, ít nhất ba cạnh cùng màu chắc chắn sẽ nằm ở gót của các cạnh còn lại (chứng minh điều này). Ví dụ: giả sử có ba cạnh màu đỏ đi ra từ đỉnh A (Hình 2). Những cạnh màu nào có thể nối các đỉnh B, C và D? Nếu ít nhất một trong số chúng có màu đỏ, như trong Hình 3, thì bạn sẽ có một hình tam giác có các cạnh màu đỏ. Nếu tất cả các cạnh này đều có màu xanh lam, như trong Hình 4 thì chúng tạo thành một hình tam giác có các cạnh màu xanh lam.

Nhiệm vụ hoàn toàn là lời giải. Ngoài ra, với lời giải hai tính chất của nó đã được chứng minh.

Tính chất 1. Bất kỳ đỉnh nào trong đồ thị có sáu đỉnh trở lên và các cạnh có hai màu sẽ tạo ra ít nhất ba cạnh cùng màu.

Tính chất 2. Trong bất kỳ đồ thị nào có từ sáu đỉnh trở lên và các cạnh hai màu đều có ít nhất một hình tam giác có các cạnh bằng một điểm.

Nhiệm vụ 2. Năm thành phố được chọn trên bản đồ địa lý. Được biết, trong ba cái bất kỳ sẽ có hai cái được kết nối bằng avalinium và hai cái không được kết nối. Chứng minh rằng nó đúng:

1. Mỗi thành phố được kết nối bằng avalinium với hai và chỉ hai thành phố khác.
2. Sau khi khởi hành từ bất kỳ thành phố nào, bạn có thể làm cho đường đi của các thành phố còn lại trở nên dễ dàng hơn bằng cách tăng từng thành phố một lần và quay trở lại.

Đã giải quyết và e. Hai thành phố đều có một trong hai mối quan hệ - chúng được kết nối bằng avalinium hoặc không được kết nối. Đặt các đỉnh của đồ thị tương ứng với các thành phố, cạnh màu đỏ là sự hiện diện của avalinia và cạnh màu xanh là sự vắng mặt. Theo điều kiện, trong ba cạnh nối ba đỉnh bất kỳ, một cạnh màu đỏ, cạnh thứ hai màu xanh, nghĩa là đồ thị không có một tam giác đơn cạnh nào. Vẫn còn phải chứng minh rằng trong một đồ thị có đỉnh thứ năm và các cạnh có hai màu, mỗi đỉnh thuộc về hai cạnh màu đỏ và hai cạnh màu xanh, và các cạnh màu đỏ tạo thành một đường khép kín đi qua mỗi đỉnh chỉ một lần, hoặc nói cách khác, trong đồ thị như vậy có một “ngũ giác”, tất cả các cạnh đều màu đỏ và tất cả các đường chéo của nó đều màu xanh.

Rõ ràng là từ mỗi đỉnh của đồ thị có hai cạnh màu đỏ và hai cạnh màu xanh, vì nếu không thì một tam giác có một cạnh

51

mặt không màu. Do đó, mỗi thành phố được kết nối bằng aunalia với hai và chỉ hai thành phố.

Bây giờ, hãy chọn một trong các đỉnh, ví dụ $A$, và giả sử các cạnh $AB$ và $AC$ sẽ có màu đỏ (Hình 5). Cạnh $CB$ không thể có màu đỏ, do đó một trong các cạnh $CD$ hoặc $CE$ có màu đỏ. Đặt màu đỏ là $CD$. Nếu bây giờ chúng ta kết nối các đỉnh $B$ và $D$ với một cạnh màu đỏ, thì đỉnh $E$ phải được nối bằng các cạnh màu đỏ với các đỉnh đã thuộc về hai cạnh màu đỏ. Theo điều kiện, điều này là không thể. Việc còn lại là kết nối các đỉnh $D$ và $E$, $B$ và $E$ với các cạnh màu đỏ. Các đường gân còn lại phải có màu xanh lam (Hình 1a).

Cùng với lời giải bài toán người ta thu được thêm một thuộc tính nữa của đồ thị.

Tính chất 3. Nếu một đồ thị có đỉnh thứ năm và các cạnh có hai màu không có tam giác có các cạnh một điểm thì đồ thị có thể được biểu diễn dưới dạng “ngũ giác” với các cạnh màu đỏ và các đường chéo màu xanh.

Nhiệm vụ 3. Chưa đến một nửa trong số sáu thuê bao melephone có thể hoặc không thể tin tưởng lẫn nhau qua melephone. Chứng minh rằng luôn có thể tìm được hai bộ ba đăng ký, trong đó mỗi bộ đều có người đã nói chuyện với nhau hoặc không có người nào nói chuyện. (Chúng tôi khái quát hóa nhiệm vụ này bài toán 1).

Lời giải. Cho một biểu đồ có sáu đỉnh $A, B, C, D, E, F$ có các cạnh màu đỏ tương ứng với những thông số đã nói chuyện với nhau trên điện thoại và các cạnh màu xanh tương ứng với những người không nói chuyện. Khi đó, có ít nhất một hình tam giác có một cạnh, ví dụ: tam giác $ABF$ có ​​cạnh màu đỏ. Tạm thời loại trừ khỏi việc xem xét một trong các đỉnh của nó, chẳng hạn như $A$, cùng với các cạnh nổi lên từ nó. Có tam giác nào có cạnh bằng một điểm trong đồ thị còn lại có năm đỉnh không? Nếu tìm thấy thì nó cũng có trong biểu đồ gốc. Nếu không, chúng ta sẽ có một hình tam giác thứ năm với các cạnh màu đỏ và các đường chéo màu xanh lam (Hình 6). Bây giờ khôi phục đỉnh thứ sáu $A$ với các cạnh của nó. Xương sườn $AF$ và $AB$ có màu đỏ. Nếu cạnh $AE$ hoặc $AC$ cũng có màu đỏ thì ít nhất một hình tam giác nữa có cạnh màu đỏ $AEF$ hoặc $ABC$ được hình thành. Nếu các cạnh này có màu xanh lam thì một hình tam giác $ACE$ có cạnh màu xanh lam sẽ xuất hiện.

Thuộc tính đồ thị đã được thiết lập, đây là dạng tổng quát của thuộc tính 2.

Tính chất 4. Trong bất kỳ đồ thị nào có sáu đỉnh trở lên và các cạnh có hai màu, sẽ luôn có hai hình tam giác có cạnh một điểm. Hai tam giác này có thể có một đỉnh chung hoặc thậm chí có một cạnh chung.

Nếu hai tam giác có một đỉnh hoặc một cạnh chung thì chúng được gọi là liên kết.

Nhiệm vụ 4. Một nhóm thực vật đồng đẳng được coi là “đồng nhất” nếu có hai thực vật trong nhóm này quen thuộc, hoặc

52

Cơm. 8. Ngược lại, họ không hề biết nhau. Chứng minh rằng trong số những người tình cờ gặp nhau sẽ luôn có hai nhóm đồng nhất, mỗi nhóm gồm ba người, và không có ai thuộc nhóm thứ nhất được xếp vào nhóm thứ hai.

Nói cách khác, chúng ta đang cố gắng chứng minh rằng trong một đồ thị có tám đỉnh và các cạnh cùng màu sẽ luôn có hai hình tam giác không nối nhau với các cạnh đồng nhất.

Lời giải. Hãy xem xét một trong các hình tam giác trong biểu đồ, ví dụ KLM, có cạnh một năm. Nếu năm đỉnh còn lại và các cạnh nối chúng theo cặp chứa một tam giác có cạnh một năm thì đó sẽ là tam giác bắt buộc thứ hai. Nếu năm đỉnh còn lại A, B, C, D, E không chứa tam giác có cạnh một năm thì tạo thành ngũ giác có cạnh đỏ và đường chéo xanh (tính chất 3). Hình 7 không hiển thị tất cả các cạnh của đồ thị mà chỉ hiển thị tam giác KLM có cạnh màu đỏ và hình ngũ giác ABCDE có cạnh màu đỏ và các đường chéo màu xanh. Hãy chứng minh rằng nếu bất kỳ đỉnh nào của tam giác KLM nối với hai đỉnh của ngũ giác, đi qua một đỉnh, ví dụ K với A và C (Hình 8), thì có một tam giác có cạnh một năm không tích phân với tam giác ACK. Thật vậy, chúng ta hãy xét hình ngũ giác BDELM. Rõ ràng là không thể tô màu các cạnh BL và BM để nó biến thành hình ngũ giác có cạnh màu đỏ và các đường chéo màu xanh. Do đó, nó nhất thiết phải chứa một tam giác một phần tử, không thẳng hàng với tam giác ACK (Hình 9).

Vẫn còn phải xét trường hợp mỗi đỉnh của tam giác KLM được nối bằng cạnh màu đỏ với ít nhất ba đỉnh liên tiếp của ngũ giác ABCDE. Ví dụ: Giả sử đỉnh K được nối bằng các cạnh màu đỏ với các đỉnh A, B và C. Khi đó các đỉnh L và M được nối bằng các cạnh màu đỏ với A, B và C. Ngược lại, có hai tam giác không đều có các đỉnh K, L hoặc M và các đáy - các cạnh của hình ngũ giác ABCDE. Nhưng sau đó (xem Hình 10) chúng ta tìm thấy hai tam giác CLM và ABK có cạnh màu đỏ. Như vậy, trong mọi trường hợp đều có hai tam giác không bằng nhau có cạnh một năm.

Bây giờ chúng ta hãy giải bài toán, được đề xuất tại Olympic Toán học Quốc tế lần thứ sáu.

Bài toán 5. Nhà khoa học nào trong số 17 nhà khoa học tương ứng với những nhà khoa học còn lại. Trong quá trình tìm kiếm xương sườn, chúng ta sẽ tìm thấy ba địa điểm. Cặp nhà khoa học nào tương ứng với nhau chỉ ở một nơi. Chứng minh rằng có ít nhất ba nhà khoa học tương ứng với nhau ở cùng một nơi.

Lời giải. Điều kiện bài toán tương ứng với một đồ thị có mười bảy đỉnh và cạnh là các điểm màu.