Chuyên đề Toán 11 KNTT Bài 8. Một vài khái niệm cơ bản có đáp án

Lời giải:

Những kiến thức ban đầu về lí thuyết đồ thị trong bài học này sẽ giúp chúng ta tìm được câu trả lời cho tình huống trên như sau:

Ta vẽ một đồ thị với 16 đỉnh tương ứng với 16 đại biểu tham dự hội nghị. Nếu hai đại biểu nào bắt tay nhau thì ta nối hai đỉnh tương ứng bằng một cạnh.

Theo số liệu mà đại biểu đếm số bắt tay cung cấp, ta có một đồ thị với 16 đỉnh, trong đó có 1 đỉnh bậc 0, 4 đỉnh bậc 4, 5 đỉnh bậc 5 và 6 đỉnh bậc 6.

Ở đây số đỉnh bậc 5 là 5, là một số lẻ. Điều này mâu thuẫn với hệ quả của Định lí bắt tay (Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn).

Vậy đại biểu đó đã đếm sai.

Lời giải:

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.

Lời giải:

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

Lời giải:

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.

Lời giải:

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.

Lời giải:

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.

Lời giải:

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

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

Lời giải:

Đỉ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.

Lời giải:

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(12 – x).

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 3x + 4(12 – x) = 56, tức là 8 + x = 0. 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.

Lời giải:

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

Lời giải:

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.

Lời giải:

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

b) Không tồn tại một đường đi từ đỉnh A đến đỉnh F.

Lời giải:

Đồ 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.

Lời giải:

Hình biểu diễn của đồ thị G như sau.

Đồ thị G là đơn đồ thị, nhưng không phải đồ thị đầy đủ.

Lời giải:

a) Đồ thị có 4 đỉnh và có đúng hai đỉnh cùng bậc và bậc là 1.

Ở đây, đỉnh A và C đều có bậc 1, trong khi đỉnh D có bậc 2, còn đỉnh B có bậc 0.

b) Đồ thị có 4 đỉnh và có đúng hai đỉnh cùng bậc và bậc là 2.

Ở đây, đỉnh B và C đều có bậc 2, trong khi đỉnh D có bậc 3, còn đỉnh A có bậc 1.

Lời giải:

Các đồ thị a) và c) là đồ thị con của đồ thị G vì mọi đỉnh và mọi cạnh của từng đồ thị a) và c) đều là đỉnh và cạnh của G.

Đồ thị b) không phải là đồ thị con của đồ thị G vì đồ thị b) chứa cạnh UW không phải là cạnh của G.

Lời giải:

Do đồ thị đầy đủ nên mỗi đỉnh được nối với n – 1 đỉnh khác, tức là số cạnh là n(n – 1) cạnh.

Tuy nhiên, do ở trên ta đã tính lặp một cạnh 2 lần, nên số cạnh thực tế của đồ thị là $\frac{{n\left( {n - 1} \right)}}{2}$.

Lời giải:

Ta thấy đồ thị đưa ra ở đề bài có 3 đỉnh bậc lẻ (3, 3 và 5), nên theo Hệ quả của Định lí bắt tay, không có đồ thị nào thỏa mãn điều kiện đưa ra.

Lời giải:

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

b) Ta thấy hai đỉnh bất kì của đồ thị đều liên thông (tức là đều có đường đi nối chúng), nên G liên thông.

c) Chu trình sơ cấp trong G là: AEHCFBGDA.