Chủ đề này có 12 trả lời

[lehoan]

Có 101 thành phố. Biết giữa hai thành phố bất kì có 1 đường bay một chiều hoặc không có đường bay nào.

a) Biết mỗi thành có 50 đường bay đến, 50 đường bay đi. CMR với 2 thành phố bất kì A và B thì ta có thể bay từ A đến B mà chỉ phải dừng quá giang tại nhiều nhất là 1 thành phố C.

b) Biết mỗi thành phố có đúng 40 đường bay đến, 40 đường bay đi. CMR với 2 thành phố bất kì thì ta có thể bay từ A đến B mà phải quá giang không nhiều hơn 2 thành phố.

c) Hỏi kết luận ở câu b) còn đúng không nếu thay 40 bởi 39.

[HaiDang]

Câu 1 thì dễ: Gọi thành phố xuất phát là E, thành phố đến là G.
Gọi Ee là tập hợp của 50 thành phố mà E có thể đi đến. Gg là tập hợp 50 thành phố mà có thể đi đến G. Vì số thành phố là 101 suy ra Ee và Gg giao nhau ít nhất 1 phần tử. suy ra tối đa là đi qua 1 thành phố.
Câu 2 : Ý tưởng cũng hơi tương tự
Ở đây là 40 thành phố. Ta cũng chia tương tự, Ee là 40 thành phố, Gg là 40
Ta thấy nếu E có thể đến 1 thành phố trong Gg hoặc trong các thành phố của Ee có 1 thành phố đến được G thì số thành phố trung gian là 1.
Hoặc nếu Ee Gg ít nhất 1 thành phố thì số thành phố trung gian cũng là 1.
Nếu Ee Gg = thì ta gọi tập TG(trung gian) là tập các thành phố còn lại, tập này có 19 thành phố (101 -40-40 -2 =19), số các thành phố từ Ee đến TG là : 19*40 =760. Số các thành phố tự đến với nhau trong Ee là : 40*(40-1) /2 =780.
số các thành phố từ Ee có thể đến là : 780 + 760 =1540(1). Mặt khác mỗi thành phố có đến được 40 thành phố khác và có 40 thành phố khác đến nó nến số thành phố Ee có thể đến là: 40*40 =1600(2).
(1) và (2) suy ra mâu thuẩn Ee Gg = sai. Vậy E đến G nhiều nhất là 2 thành phố.
Trường hợp 39 cũng tương tự nhưng với 38 thì ở (1) =1600 và trường hợp này nhiều nhất là 3 thành phố trung gian

Bài viết đã được chỉnh sửa nội dung bởi HaiDang: 01-01-2006 - 15:25

[chuyentoan]

Mình nghĩ bạn nhầm rồi, vì trường hợp 39 có một đồ thị không thỏa mãn, bạn nên nghĩ lại đi

[HaiDang]

Bạn có lộn không đấy, chỉ có 38 mới không được, 39 vẫn chạy tốt

[chuyentoan]

Trước hết ta xây dựng đồ thị như sau:

Hình gửi kèm

• 

[chuyentoan]

Tiếp theo ta xây dựng các mối quan hệ còn lại giữa các tập X,Y,Z và trong chính nó sao cho đồ thị thu được thỏa mãn tại mỗi đỉnh có 39 cạnh tới và 39 cạnh đi nhưng đi từ A đến B phải chuyển ít nhất 3 lần.
Mình đang ở quán nên kô nhớ chính xác được các con số, nhưng sử dụng thêm nhận xét là: ta có thể xây dựng đồ thị 2n+1 đỉnh với mỗi đỉnh có m cạnh tới và m cạnh đi, với m không vượt quá n

[chuyentoan]

Thì mình đã xây dựng xong đâu, đó chỉ mới là của hai đỉnh A, B còn có quan hệ giữa X, Y, Z và tự trong mỗi tập mà.

[chuyentoan]

Bạn nên nhớ chúng ta đang nói về đồ thị có hướng.
Còn ý bạn chỉ đúng cho đồ thì vô hướng thôi. Vì trong đồ thị vô hướng có một kết quả là: Số đỉnh bậc lẻ của một đồ thị là một số chẵn

[chuyentoan]

Đây là ví dụ cho n=4 và m=3

Hình gửi kèm

• 

[chuyentoan]

Với hình như dưới, ta xây dựng đồ thị như sau:

1) A đi tới tất cả các đỉnh ở X
2) Mỗi đỉnh trong X đều đi tới tất cả các đỉnh trong Z
2) Mỗi đỉnh trong Z đều đi tới tất cả các đỉnh trong Y
( Tức là các cặp (X,Z) và (Y,Z) là đồ thị lưỡng phân đầy đủ)
3) Với mọi http://dientuvietnam...gi?i=1,2,...,39, ta xậy dựng các đoạn như sau, các chỉ số lấy theo http://dientuvietnam...tex.cgi?2.18<39)
http://dientuvietnam.net/cgi-bin/mimetex.cgi?39 đường tới và http://dientuvietnam.../mimetex.cgi?39 đường ra nhưng từ A đến B phải chuyển $3$ lần.

------------
Chú ý giả thiết của bài toán thì đồ thị phải có hướng và giũa hai đỉnh thì có không quá một cạnh, không có cạnh nào vô hướng.

Hình gửi kèm

• 

[lehoan]

Ta chứng minh 39 không thỏa mãn.

Xét các tập hợp sau: http://dientuvietnam...n/mimetex.cgi?X là tập gồm 39 thành phố http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{A_0;A_1;..;A_{38}\}. http://dientuvietnam...n/mimetex.cgi?Y là tập gồm 39 thành phố http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{B_0;B_1;...;B_{38}\}.

http://dientuvietnam.net/cgi-bin/mimetex.cgi?Z là tập gồm 21 thành phố http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{C_0;C_1;...;C_{20}\}. Và 2 thành phố http://dientuvietnam...n/mimetex.cgi?A và http://dientuvietnam.../mimetex.cgi?B.

Ta kí hiệu http://dientuvietnam...n/mimetex.cgi?A đến http://dientuvietnam.../mimetex.cgi?B. Ta xây dựng đồ thị như sau:

.
( lấy theo mod 39)
.
.
.
.
.

[chuyentoan]

HaiDang đâu rồi nhỉ

[HaiDang]

Dạo này bận nên ít lên mạng lắm, ừh, tui đã xem cách xây dựng đồ thị của lehoan và chuyentoan rồi, 39 không đúng nhiều nhất là 2 đường. hihihi