Bài 8. Một vài khái niệm cơ bản

Hoạt động 1

Có bốn bạn học sinh khối 11 là An, Bình, Cường và Dung, trong đó: An là bạn của Bình và Cường, nhưng không là bạn của Dung; Dung là bạn của Cường, nhưng không là bạn của Bình; Bình là bạn của Cường.

a) Hãy biểu diễn mỗi bạn An, Bình, Cường, Dung bằng một điểm trên mặt phẳng và dùng chữ cái đầu (in hoa) trong tên của họ để đặt tên cho các điểm này.

b) Nếu hai người là bạn của nhau, hãy nối các điểm biểu diễn tương ứng bằng một đoạn thẳng (hay đoạn đường cong).

c) Từ hình vẽ thu được ở HĐ1b, hãy cho biết: ai có nhiều bạn nhất và ai có ít bạn nhất?

Phương pháp giải:

Vẽ hình theo yêu cầu đề bài

Lời giải chi tiết:

a) Lần lượt biểu diễn mỗi bạn An, Bình, Cường, Dung bằng các điểm A, B, C, D trên mặt phẳng (hình vẽ).

b) Nếu hai người là bạn của nhau, nối các điểm biểu diễn tương ứng (hình vẽ).

 c) Từ hình vẽ thu được, ta thấy Cường có nhiều bạn nhất vì từ điểm C đều có đoạn thẳng nối tới cả 3 điểm A, B, D và Dung có ít bạn nhất vì từ điểm D chỉ có 1 đoạn thẳng nối đến điểm C.

Luyện tập 1

Bảng F của giải vô địch bóng đá thế giới World Cup 2018 gồm bốn đội: Đức, Hàn Quốc, Mexico và Thuỵ Điển. Biểu diễn các đội này bằng các điểm phân biệt kí hiệu lần lượt là D, H, M, T (vẽ sao cho không có ba điểm nào thẳng hàng để dễ quan sát) và nếu hai đội nào đấu với nhau thì ta nối hai điểm tương ứng bằng một đoạn thẳng, ta sẽ được một đồ thị G.

Viết tập hợp các đỉnh và tập hợp các cạnh của đồ thị G.

Phương pháp giải:

Đồ thị G là hình bao gồm:

- Tập hợp hữu hạn các điểm, mỗi điểm gọi là một đỉnh của đồ thị.

- Tập hợp các đoạn (cong hoặc thẳng), mỗi đoạn nối 2 đỉnh gọi là cạnh của đồ thị.

Lời giải chi tiết:

Trong một bảng đấu, các đội sẽ thi đấu vòng tròn, có nghĩa là mỗi một đội sẽ lần lượt thi đấu với ba đội còn lại. Do đó, từ mỗi điểm D, H, M, T, ta vẽ các đoạn thẳng đến các điểm còn lại ta được đồ thị G như hình vẽ dưới đây.

Khi đó ta có: V(G) = {D; H; M; T}.

E(G) = {DH; DT; DM; HT; HM; MT}.

Hoạt động 2

Xét đồ thị cho trong Hình 2.2.

a) Đồ thị trên có khuyên không?

b) Có hai đỉnh nào của đồ thị được nối với nhau bằng nhiều hơn một cạnh không?

Phương pháp giải:

Nếu hai đầu mút của cạnh trùng nhau tại đỉnh M thì ta gọi cạnh ấy là một khuyên, kí hiệu MM.

Lời giải chi tiết:

a) Đồ thị trên không có khuyên vì không có cạnh nào có hai đầu mút trùng nhau tại một đỉnh.

b) Không có hai đỉnh nào của đồ thị được nối với nhau bằng nhiều hơn một cạnh

Luyện tập 2

Vẽ đồ thị G với các đỉnh và các cạnh như sau:

V(G) = {U, W, X, Z} và E(G) = {UW, WX, WZ, XZ}.

G có phải là một đơn đồ thị không?

Phương pháp giải:

Đồ thị G được gọi là đồ thị đơn nếu với mỗi cặp đỉnh của đồ thị chỉ có không quá một cạnh nối chúng và không có đỉnh nào nối với chính nó bởi một cạnh của đồ thị.

Lời giải chi tiết:

G là một đơn đồ thị, do hai đỉnh bất kì đều nối với nhau bởi không quá một cạnh.

Hoạt động 3

Xét đồ thị nhận được trong Luyện tập 1. Có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chúng không?

Phương pháp giải:

Quan sát hình vẽ để trả lời

Lời giải chi tiết:

Quan sát đồ thị có được từ Luyện tập 1, ta thấy không có bất kì cặp đỉnh nào của đồ thị mà không có cạnh nối chúng với nhau hay mỗi cặp đỉnh của đồ thị đều được nối với nhau bằng một cạnh.

Luyện tập 3

Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.

Phương pháp giải:

Đồ thị G là hình bao gồm:

- Tập hợp hữu hạn các điểm, mỗi điểm gọi là một đỉnh của đồ thị.

- Tập hợp các đoạn (cong hoặc thẳng), mỗi đoạn nối 2 đỉnh gọi là cạnh của đồ thị.

Lời giải chi tiết:

+) Đồ thị đầy đủ có 5 đỉnh:

+) Đồ thị đầy đủ có 6 đỉnh:

Hoạt động 4

Cho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của: 0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.

Phương pháp giải:

Dựa vào hình 2.5 để làm

Lời giải chi tiết:

Đỉnh là đầu mút của 0 cạnh là đỉnh G.

Đỉnh là đầu mút của 1 cạnh là đỉnh F.

Các đỉnh là đầu mút của 2 cạnh là các đỉnh A, B.

Các đỉnh là đầu mút của 3 cạnh là các đỉnh C, D, E.

Luyện tập 4

Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.

Phương pháp giải:

Trong một đồ thị, tổng tất cả bậc của đỉnh là một số chẵn và bằng hai lần số cạnh của đồ thị

Lời giải chi tiết:

Giả sử có đồ thị thỏa mãn yêu cầu bài toán. Gọi x là số đỉnh bậc 3 của đồ thị.

Khi đó, ta có số đỉnh bậc 4 là: $12-x.$

Tổng số bậc của các đỉnh là: $3x+4\left(12-x\right).$

Vì đồ thị có 28 cạnh nên theo Định lí bắt tay thì đồ thị có tổng số bậc là $28.2=56.$

Do đó, ta có phương trình , tức là . Phương trình này không có nghiệm là số tự nhiên, do đó không tồn tại đồ thị thỏa mãn điều kiện đề bài.

Hoạt động 5

Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh, với điều kiện không đi qua cạnh nào quá một lần (có thể có cạnh không cần đi qua), hãy chỉ ra các cách để:

a) Đi từ đỉnh A đến đỉnh E.

b) Đi từ đỉnh A và lại quay về đỉnh A.

Phương pháp giải:

Quan sát hình 2.7 để làm

Lời giải chi tiết:

a) Để đi từ đỉnh A đến đỉnh E ta có thể di chuyển theo con đường từ A đến D rồi từ D đến E (hoặc cũng có thể chọn các con đường khác, chẳng hạn đi theo đường từ A đến B rồi từ B đến D và từ D đến E, ...)

b) Để đi từ đỉnh A và lại quay về đỉnh A ta có thể di chuyển theo con đường từ A đến D rồi từ D đến B và từ B quay lại A (tương tự cũng có thể chọn các con đường khác).

Luyện tập 5

Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm những chu trình sơ cấp xuất phát từ đỉnh A và có: độ dài 4; độ dài 5.

Phương pháp giải:

Một  đường đi (chu trình) qua n cạnh gọi là một đường đi (chu trình) có độ dài n.

Lời giải chi tiết:

Những chu trình sơ cấp có độ dài 4 xuất phát từ đỉnh A là: ABCDA, ABCEA, ABDCA, ABDEA, ABEDA, ABECA, ACBDA, ACBEA, ACDBA, ACDEA, ACEBA, ACEDA, ADBEA, ADBCA, ADCEA, ADCBA, ADEBA, ADECA, AEBDA, AEBCA, AECDA, AEDCA, AECBA, AEDBA.

Những chu trình sơ cấp có độ dài 5 xuất phát từ đỉnh A là: ABCDEA, ABCEDA, ABECDA, ABEDCA, ABDCEA, ABDECA, ACBEDA, ACBDEA, ACDEBA, ACDBEA, ACEDBA, ACEBDA, ADBECA, ADBCEA, ADCBEA, ADCEBA, ADECBA, ADEBCA, AECDBA, AECBDA, AEDCBA, AEDBCA, AEBCDA, AEBDCA.

Hoạt động 6

Nhận biết tính liên thông của đồ thị 

Trong đồ thị ở Hình 2.10, hãy:

a) Tìm một đường đi từ đỉnh A đến đỉnh E.

b) Có tồn tại một đường đi từ đỉnh A đến đỉnh F hay không?

Phương pháp giải:

Quan sát hình 2.10 để trả lời

Lời giải chi tiết:

a) Một đường đi từ đỉnh A đến đỉnh E là: ABCDE. 

b) Không tồn tại đường đi nào từ đỉnh A đến đỉnh F vì F là đỉnh cô lập.

Luyện tập 6

 Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một đường đi nối đỉnh 1 và đỉnh 6.

Phương pháp giải:

Một đồ thị được gọi là liên thông nếu hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi.

Lời giải chi tiết:

Đồ thị Hình 2.12 có 7 đỉnh, lấy 2 đỉnh bất kì của đồ thị, ta đều thấy có một đường đi nối hai điểm đó, do đó mọi cặp đỉnh của đồ thị này đều liên thông nên đồ thị này liên thông.