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ề.

a) Các đỉnh của đồ thị G là: A, B, C, D, E và F. Đồ thị có 6 đỉnh.

Các cạnh của đồ thị G là: AC, AD, AE, a, b, c, BD, CD, CF, DE. Đồ thị có 10 cạnh.

b) Các đỉnh kề đỉnh D là: A, B, C, E.

Các đỉnh kề đỉnh B là: C, D.

c) Đồ thị G không có đỉnh cô lập.

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:

a) Do ta có 3 con đường để ra, vào ngôi làng A nên ngôi làng A có 3 cổng chào.

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

⦁ Ngôi làng B có 5 cổng chào;

⦁ Ngôi làng C có 2 cổng chào;

⦁ Ngôi làng D có 3 cổng chào;

⦁ Ngôi làng E có 3 cổng chào.

Vậy ngôi làng có ít cổng chào nhất là ngôi làng C (với 2 cổng chào); ngôi làng có nhiều cổng chào nhất là ngôi làng B (với 5 cổng chào).

b) Quan sát Hình 6, đồ thị có tất cả 8 cạnh (mỗi cạnh biểu diễn 1 con đường giữa hai ngôi làng) nên năm ngôi làng có tất cả 8 cổng chào.

a) Số cạnh của đồ thị có A là đầu mút là: 4. Suy ra bậc của đỉnh A là: d(A) = 4.

Tương tự như vậy, ta có: d(B) = 4; d(C) = 5; d(D) = 4; d(E) = 2; d(F) = 1.

Tổng các bậc của các đỉnh của đồ thị là: 4 + 4 + 5 + 4 + 2 + 1 = 20.

b) Tất cả các đỉnh kề với đỉnh B là: A, C, D. Suy ra có 3 đỉnh kề với đỉnh B.

Mà bậc của đỉnh B là: d(B) = 4.

Vì 3 ≠ 4 nên 3 ≠ d(B).

Vậy số đỉnh kề với đỉnh B không bằng bậc của đỉnh B.

Không có, vì tổng tất cả các bậc của các đỉnh là 2 + 2 + 3 = 7 là một số lẻ.

⦁ Hình 12a:

Các đỉnh của đồ thị là: A, B, C, D. Số đỉnh của đồ thị là: 4.

Các cạnh của đồ thị là: AB, AC, AD, BC, BD, CD. Số cạnh của đồ thị là: 6.

⦁ Hình 12b:

Các đỉnh của đồ thị là: A, B, C, D, E, F. Số đỉnh của đồ thị là: 6.

Các cạnh của đồ thị là: m, n, AC, AD, BC, CD, CE, DF, EF. Số cạnh của đồ thị là: 9.

a) Số cạnh của đồ thị có A là đầu mút là: 2. Suy ra bậc của đỉnh A là: d(A) = 2.

Tương tự như vậy, ta có: d(B) = 3; d(C) = 5; d(D) = 5; d(E) = 1; d(F) = 0.

b) Từ kết quả câu a), ta có các đỉnh bậc lẻ của đồ thị là: B, C, D, E.

c) Tổng tất cả các bậc của các đỉnh của đồ thị là: 2 + 3 + 5 + 5 + 1 + 0 = 16.

Tổng tất cả các bậc của bốn đỉnh của đồ thị là: 2 + 3 + 4 + 3 = 12.

Vậy số cạnh của đồ thị là: 122=6.

Ta vẽ đồ thị như sau:

– Gọi 4 đỉnh của đồ thị là A, B, C, D có bậc của mỗi đỉnh lần lượt là 2; 3; 4; 3.

– Ta bắt đầu vẽ từ đỉnh có số bậc cao nhất là đỉnh C: Xuất phát từ đỉnh C, ta nối một cạnh tới đỉnh A; hai cạnh tới đỉnh B và một cạnh tới đỉnh D.

– Tiếp theo, do có hai đỉnh B, D có số bậc là 3 nên ta tùy ý chọn một đỉnh là đỉnh B để vẽ tiếp. Lúc này, ta thấy đỉnh B đã có sẵn hai cạnh nên ta nối thêm một cạnh từ đỉnh B đến đỉnh D.

– Cuối cùng, vì đỉnh D, A có số cạnh lần lượt là 3, 2 (tức là đỉnh D còn thiếu một cạnh và đỉnh A cũng còn thiếu một cạnh) nên ta nối một cạnh giữa hai đỉnh D và A.

Đồ thị thỏa mãn yêu cầu bài toán là:

Chú ý: Ngoài đồ thị đã vẽ ở trên, ta có thể vẽ thêm các đồ thị khác cũng thỏa mãn yêu cầu đề bài.

Theo Định lí, ta có tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh của đồ thị.

Suy ra tổng tất cả các bậc của các đỉnh là: 2.8 = 16.

Theo đề, ta có đồ thị G có 6 đỉnh và các đỉnh của đồ thị G có bậc 2 hoặc 4.

Mà 2 + 2 + 2 + 2 + 4 + 4 = 16.

Vậy đồ thị G có 2 đỉnh bậc 4 và 4 đỉnh bậc 2.

Ta vẽ đồ thị như sau:

– Gọi 6 đỉnh của đồ thị là A, B, C, D, E, F có bậc của mỗi đỉnh lần lượt là 4; 4; 2; 2; 2; 2.

– Do có hai đỉnh A, B có số bậc cao nhất là 4 nên ta tùy ý chọn một đỉnh là đỉnh A để bắt đầu vẽ. Xuất phát từ đỉnh A, ta lần lượt nối tới các đỉnh B, C, D, E, mỗi đỉnh một cạnh.

– Tiếp theo, ta vẽ từ đỉnh có số bậc cao nhất còn lại là đỉnh B. Do từ đỉnh B đã có sẵn một cạnh đã vẽ ở trên nên xuất phát từ đỉnh B, ta lần lượt vẽ thêm đến các đỉnh C, D, F, mỗi đỉnh một cạnh.

– Cuối cùng, ta thấy các đỉnh C, D đều có số bậc là 2. Mà hai đỉnh này ta đã vẽ xong hai cạnh cho mỗi đỉnh nên kế tiếp ta sẽ xét đến hai điểm còn lại là E, F.

Ta thấy với các đỉnh E, F, mỗi đỉnh đều đã có sẵn một cạnh đã vẽ trước đó nên ta nối một cạnh giữa hai đỉnh E và F.

Một đồ thị thỏa mãn yêu cầu bài toán là:

Chú ý: Ngoài đồ thị đã vẽ ở trên, ta có thể vẽ thêm các đồ thị khác cũng thỏa mãn yêu cầu đề bài.

Ta vẽ đồ thị G có 5 đỉnh A, B, M, Q, X lần lượt biểu diễn năm học sinh An, Bình, Mai, Quang, Xuân.

Hai đỉnh được nối bằng một cạnh nếu giữa hai người mà chúng biểu diễn quen nhau.

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

Trong tập hợp số V, ta có các cặp số sau nguyên tố cùng nhau:

• (2 và 3); (2 và 5); (2 và 7); (2 và 11);

• (3 và 4); (3 và 5); (3 và 7); (3 và 11);

• (4 và 5); (4 và 7); (4 và 11);

• (5 và 6); (5 và 7); (5 và 11); (5 và 12);

• (6 và 7); (6 và 11);

• (7 và 11); (7 và 12);

• (11 và 12).

Ta vẽ đồ thị G có 8 đỉnh A₂, A₃, A₄, A₅, A₆, A₇, A₁₁, A₁₂ lần lượt biểu diễn tám số 2; 3; 4; 5; 6; 7; 11; 12 trong tập hợp số V.

Hai đỉnh được nối bằng một cạnh nếu hai số mà chúng biểu diễn nguyên tố cùng nhau.

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