Chuyên đề Toán 11 CTST Bài 1. Đồ thị có đáp án

Sau các bài học của chuyên đề này, chúng ta sẽ giải quyết được bài toán trên như sau:

Biểu thị mỗi vùng đất bằng một đỉnh, mỗi cây cầu bằng một cạnh nối hai đỉnh, ta được đồ thị như hình vẽ.

Ta thấy d(A) = 5; d(B) = d(C) = d(D) = 3.

Suy ra tất cả các đỉnh của đồ thị trên đều có bậc lẻ.

Do đó đồ thị không có chu trình Euler.

Vậy nói cách khác, không thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.

Để giải đáp thắc mắc trên, ta nên dùng sơ đồ ở Hình 1, vì sơ đồ của Hình 1 giúp ta có cái nhìn bao quát về mối liên hệ giữa các đường bay từ thành phố này đến thành phố kia.

a) Quan sát sơ đồ ở Hình 1, ta thấy:

⦁ Có 1 đường bay từ thành phố A đến thành phố B;

⦁ Có 1 đường bay từ thành phố A đến thành phố D;

⦁ Có 1 đường bay từ thành phố A đến thành phố E;

⦁ Có 1 đường bay từ thành phố A đến thành phố F.

Vậy từ thành phố A, hãng X có tất cả 4 đường bay đến năm thành phố còn lại.

b) Vì đường bay của hãng X là đường bay hai chiều nên đường bay từ thành phố B đến thành phố A đã được tính vào đường bay từ thành phố A đến thành phố B.

Do đó từ thành phố B, hãng X có thêm:

⦁ 1 đường bay đến thành phố C;

⦁ 1 đường bay đến thành phố D;

⦁ 1 đường bay đến thành phố F.

Khi đó, từ thành phố B, hãng X có thêm 3 đường bay đến năm thành phố còn lại.

Tương tự như vậy, ta được:

– Từ thành phố C, hãng X có thêm 2 đường bay đến năm thành phố còn lại;

– Từ thành phố D, hãng X có thêm 1 đường bay đến năm thành phố còn lại;

– Từ thành phố E, hãng X có thêm 1 đường bay đến năm thành phố còn lại.

Vì đường bay của hãng X là đường bay hai chiều nên đường bay từ thành phố F đến năm thành phố còn lại đã được tính vào các đường bay kể trên.

Vậy giữa sáu thành phố trên, có tất cả 4 + 3 + 2 + 1 + 1 = 11 đường bay của hãng X.

Chú ý: Ngoài cách trên, ta có thể đếm số đường cong và đường thẳng (thể hiện đường bay) trên Hình 1 (hoặc Bảng 1) để kết luận về số đường bay của hãng X.

c) Ta có thể giải đáp thắc mắc ở Hoạt động khởi động như sau:

Bước 1: Từ thành phố A bay đến thành phố B;

Bước 2: Từ thành phố B bay đến thành phố C;

Bước 3: Từ thành phố C bay đến thành phố D;

Bước 4: Từ thành phố D bay đến thành phố F;

Bước 5: Từ thành phố F bay đến thành phố E;

Bước 6: Từ thành phố E bay về thành phố A.

Vậy từ thành phố A, ta có thể thăm năm thành phố B, C, D, E và F bằng các chuyến bay của hãng X sao cho mỗi thành phố chỉ qua đúng một lần, rồi quay trở về A.

Chú ý: Ta có thể thay đổi thứ tự bay đến các thành phố chỉ cần hãng X có chuyến bay giữa hai thành phố liền kề.

Ta vẽ đồ thị G có 7 đỉnh A, B, C, D, E, F, G lần lượt biểu diễn bảy máy tính 1; 2; 3; 4; 5; 6 và 7.

Hai đỉnh được nối bằng một cạnh nếu giữa hai máy tính có kết nối trực tiếp với nhau.

Ta có đồ thị G như sau: