▶BÀI ❶. MỘT VÀI KHÁI NIỆM CƠ BẢN VỀ LÝ THUYẾT ĐỒ THỊ
Ⓐ. Tóm tắt kiến thức
❶. Đồ thị
a) Khái niệm đồ thị
Một đồ thị là một tập hợp hữu hạn các điềm (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.
* Chú ý. Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng, mà bản chất là đổ thị có bao nhiêu đĩnh, bao nhiêu cạnh và đïnh nào được nối với đỉnh nào.
* Ta thường kí hiệu là tập hợp các đỉnh và là tập hợp các cạnh của đồ thị , và viết .
* Cạnh nối hai đỉnh và thường được kí hiệu là hoặc , và khi đó và gọi là hai đỉnh kề nhau. Nếu hai đầu mút của cạnh trùng nhau tại đỉnh thì ta gọi cạnh ấy là một khuyên, kí hiệu là CC.
* Hình 2.1 cho ta một đồ thị có 4 đỉnh là và 5 cạnh là và .
b) Đơn đồ thị và đa đồ thị
* Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là một đơn đồ thị.
Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối bằng nhiều cạnh, gọi là một đa đồ thị.
* Chú ý. Trong cuốn sách này, khi chỉ nói từ đồ thị thì ta hiểu là đơn đồ thị. Khi nào cần xét đa đồ thị thì ta sẽ nói rõ.
c) Đồ thị đầy đủ
* Một đồ thị là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó đều được nối bằng một cạnh.
* Nhận xét. Một đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh của nó đều là kề nhau. Một đồ thị đầy đủ hoàn toàn được xác định bởi số đỉnh của nó. Đồ thị đầy đủ có đỉnh thường được kí hiệu là .
 
 
 
 
 
❷. Bậc của đồ thị
* Một đỉnh của đồ thị được gọi là đỉnh bậc nếu nó là đầu mút của cạnh.
* Chú ý. Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đình treo.
* Trong đồ thi ở Hình 2.5, là đỉnh bậc là đỉnh treo, là đỉnh cô lập.
* Định lí (gọi là Đinh II bắt tay)
Trong mọi đồ thị , tổng tất cả các bậc của các đỉnh là một số chăn và bằng hai lần tổng tất cả các cạnh của .
* Hệ quả. Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.
❸. ĐƯỜNG ĐI VÀ CHU TRÌNH
a) Khái niệm đường đi và chu trình
* Trong một đồ thị , một dãy cạnh nối tiếp (hai cạnh nối tiếp là hai cạnh có chung một đầu mút) . gọi là một đường đi nối với , kí hiệu là .
* Điểm gọi là đầu đường, điểm gọi là cuối đường.
* Một đường đi khép kín (đầu đường trùng với cuối đường) gọi là một chu trình.
* Một đường đi (chu trình) qua cạnh gọi là một đường đi (chu trình) có độ dài .
* Một đường đï (hay chu trình) là sơ cấp nếu nó không đi qua đỉnh nào hai lần trở lên.
* Một đường đi (chu trình) là đơn giản nếu nó không đi qua cạnh nào hai lần trở lên.
b) Tính liên thông của đồ thị
* Hai đỉnh và của một đồ thị gọi là liên thông nếu có một đường đi nối và .
* Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh của là liên thông.
* Một cạnh của đồ thị gọi là một cầu nếu khi bỏ cạnh thì hai đỉnh và không còn liên thông nữa.
* Mỗi đồ thị không liên thông đều được chia thành một số đồ thị (gọi là đồ thị con của G) liên thông, rời nhau, mỗi đồ thị con đó gọi là một thành phần liên thông của .
* Một đồ thị đỉnh, mỗi đỉnh có bậc ít nhất bằng , là đồ thị liên thông.
 
 
 
 
 
Ⓑ. Phân dạng toán cơ bản
⬩Dạng ❶: Tìm đỉnh và cạnh nối đỉnh của đồ thị
☞Các ví dụ minh họa
Câu 1: Đọc tên các đỉnh, các cạnh của đồ thị ở Hình c.
Lời giải
Ở đồ thị Hình c có:
+ Các đỉnh là: A, B, C, D.
+ Các cạnh là: AB, AC, AD, BA, BD, CA, CD.
Câu 2: 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?
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
Câu 3: Sử dụng sơ đồ ở Hình 1 để trả lời các câu hỏi dưới đây:
a) Từ thành phố A, hãng X có bao nhiêu đường bay đến năm thành phố còn lại?
b) Giữa sáu thành phố trên, có tất cả bao nhiêu đường bay của hãng X?
Lời giải
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.
Câu 4: Hãy chỉ ra các đỉnh, các cạnh, số đỉnh, số cạnh của mỗi đồ thị như Hình 12.
Lời giải
⦁ 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.
⬩Dạng ❷: Tìm bậc của đỉnh
☞Các ví dụ minh họa
Câu 5: 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.
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}.
Câu 6: Cho đồ thị G như Hình 5.
a) Chỉ ra các đỉnh, các cạnh, số đỉnh, số cạnh của G.
b) Chỉ ra các đỉnh kề đỉnh D, các đỉnh kề đỉnh B.
c) Đồ thị G có đỉnh cô lập không?
Lời giải
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.
Câu 7: Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?
Lời giải
Quan sát Hình 5a ta thấy d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 2 và d(E) = 3 nên B, E là các đỉnh bậc lẻ. Vậy có hai đỉnh bậc lẻ trong đồ thị ở Hình 5a.
Câu 8: Một mạng cục bộ có bảy máy tính 1; 2; 3; 4; 5; 6 và 7. Bảng 2 cho biết giữa mỗi cặp máy tính có kết nối trực tiếp với nhau hay không (dấu  là có kết nối, dấu  là không kết nối). Hãy vẽ đồ thị biểu diễn sự kết nối giữa các máy tính của mạng này.
Lời giải
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:
Câu 9: Cho đồ thị như Hình 13.
a) Chỉ ra bậc của các đỉnh của đồ thị.
b) Chỉ ra các đỉnh bậc lẻ của đồ thị.
c) Tính tổng tất cả các bậc của các đỉnh của đồ thị.
Lời giải
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.
⬩Dạng ❸: Tìm đường đi
☞Các ví dụ minh họa
Câu 10: Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Lời giải
Sử dụng điểm để biểu diễn vị trí thành phố, đoạn thẳng biểu diễn đường đi giữa hai thành phố, ta có mô hình như hình dưới đây.
Câu 11: 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?
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.
Câu 12: 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?
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.
Câu 13: Biết rằng G là đồ thị có 6 đỉnh, 8 cạnh và các đỉnh của nó có bậc 2 hoặc 4. Đồ thị có bao nhiêu đỉnh bậc 4? Hãy vẽ một đồ thị như vậy.
Lời giả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.
⬩Dạng ❹: Chứng minh tính chất đồ thị
☞Các ví dụ minh họa
Câu 14: 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?
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.
Câu 15: Cho hai ví dụ về đồ thị đơn.
Lời giải
Các đồ thị ở hai hình sau là đồ thị đơn.
Câu 16: Chứng minh rằng không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5. 
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.
Câu 17: 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.
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.
Ⓒ. Kỹ năng rèn luyện
Câu 18: Xét đồ thị. 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?
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.
Câu 19: Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.
Lời giải
+) Đồ thị đầy đủ có 5 đỉnh:
+) Đồ thị đầy đủ có 6 đỉnh:
Câu 20: 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.
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.
Câu 21: 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.
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).
Câu 22: 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.
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.
Câu 23: 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.
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.
Câu 24: Đồ thị ở Hình 6 biểu diễn năm ngôi làng A, B, C, D và E cùng các con đường giữa chúng (mỗi cạnh biểu diễn một con đường giữa hai ngôi làng). Biết rằng mỗi con đường ra, vào làng đều phải đi qua một cổng chào; hai con đường khác nhau thì ra, vào làng qua hai cổng chào khác nhau. Ngoài ra, các ngôi làng không còn cổng chào nào khác.
a) Ngôi làng nào có ít cổng chào nhất? Ngôi làng nào có nhiều cổng chào nhất?
b) Năm ngôi làng có tất cả bao nhiêu cổng chào?
Lời giải
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.
Câu 25: Cho đồ thị như Hình 11.
a) Hãy chỉ ra bậc của tất cả các đỉnh và tìm tổng của chúng.
b) Tìm tất cả các đỉnh kề với đỉnh B. Số đỉnh này có bằng bậc của đỉnh B không?
Lời giải
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.
Câu 26: Có hay không một đồ thị có ba đỉnh, trong đó hai đỉnh có bậc bằng 2 và một đỉnh có bậc bằng 3?
Lời giải
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ẻ.
Câu 27: Một đồ thị có bốn đỉnh có bậc lần lượt là 2; 3; 4; 3. Tính số cạnh của đồ thị và vẽ đồ thị này.
Lời giải
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=6122=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.
Câu 28: Có năm học sinh An, Bình, Mai, Quang, Xuân. Biết rằng An quen Bình, Bình quen Quang, An quen Mai, Mai quen Xuân, Xuân quen Quang. Các cặp không được liệt kê ở trên thì không quen nhau. Hãy vẽ đồ thị để thể hiện mối quan hệ quen nhau giữa các học sinh trên.
Lời giả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:
Câu 29: Cho tập hợp số V = {2; 3; 4; 5; 6; 7; 11; 12}. Hãy vẽ đồ thị có các đỉnh biểu diễn các phần tử của V, hai đỉnh kề nhau nếu hai số mà chúng biểu diễn nguyên tố cùng nhau (tức có ước chung lớn nhất bằng 1).
Lời giải
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 A2, A3, A4, A5, A6, A7, A11, A12 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:
Câu 30: Vẽ hình biểu diễn của đồ thị G với tập đỉnh V(G) = {1; 2; 3; 4; 5} và tập cạnh
E(G) = {12; 14; 23; 25; 34; 35}.
Đồ thị G có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ khô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 đủ.
Câu 31: Hãy vẽ một đồ thị có 4 đỉnh và:
a) có đúng hai đỉnh cùng bậc và bậc là 1;
b) có đúng hai đỉnh cùng bậc và bậc là 2.
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.
Câu 32: Một đồ thị con của đồ thị G là một đồ thị mà mọi đỉnh của nó đều là đỉnh của G và mọi cạnh của nó cũng là cạnh của G.
Những đồ thị nào trong các hình a), b), c) dưới đây là đồ thị con của đồ thị G?
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.
Câu 33: Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có n(n−1)2nn−12 cạnh.
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à n(n−1)2nn−12.
Câu 34: Cho đồ thị G như Hình 2.14.
a) Tìm một đường đi từ đỉnh A đến đỉnh B
b) G có liên thông không?
c) Trong G có chu trình sơ cấp nào không?
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.
Câu 35: Quan sát đồ thị ở Hình 4 và cho biết:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất bao nhiêu cạnh nối chúng;
b) Có hay không một đỉnh được nối với chính nó bởi một cạnh của đồ thị.  
Lời giải
Quan sát đồ thị Hình 4 ta thấy:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất một cạnh nối chúng.
b) Không có đỉnh nào được nối với chính nó bởi một cạnh của đồ thị.
Câu 36: Quan sát đồ thị ở Hình 6 và đếm số cạnh của đồ thị nhận đỉnh P làm đầu mút.
Lời giải
Các cạnh của đồ thị nhận đỉnh P làm đầu mút là PQ, PT, PS. Vậy có 3 cạnh của đồ thị nhận đỉnh P làm đầu mút.
Câu 37: Quan sát đồ thị Hình 7 và cho biết:
a) Tổng các bậc của năm đỉnh trong đồ thị đó;
b) Số cạnh của đồ thị đó;
c) Tổng các bậc của năm đỉnh trong đồ thị gấp bao nhiêu lần số cạnh của đồ thị đó.
Lời giải
Quan sát đồ thị Hình 7 ta thấy:
a) d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 4, d(E) = 1.
Do đó, tổng các bậc của năm đỉnh trong đồ thị đó là 2 + 3 + 2 + 4 + 1 = 12.
b) Số cạnh của đồ thị đó là 6.
c) Ta có: 6 . 2 = 12 nên tổng các bậc của năm đỉnh trong đồ thị gấp hai lần số cạnh của đồ thị đó.
Câu 38: Cho ví dụ về một đồ thị có số lẻ đỉnh bậc chẵn.
Lời giải
Đồ thị trên có 5 đỉnh A, B, C, D, E với d(A) = d(B) = d(C) = d(D) = d(E) = 2.
Câu 39: Quan sát đồ thị Hình 7 và cho biết:
a) Hai đỉnh A, B có được nối với nhau bằng một cạnh hay không;
b) Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có đặc điểm gì.
Lời giải
Quan sát đồ thị Hình 7 ta thấy:
a) Hai đỉnh A, B có được nối với nhau bằng một cạnh của đồ thị.
b) Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có những tính chất sau: không có cạnh nào xuất hiện hai lần, đỉnh cuối của cạnh bất kì là đỉnh đầu của cạnh tiếp theo và không có đỉnh nào được đi qua hai lần. Dãy các cạnh kế tiếp nhau AB, BC, CD, DE được gọi là một đường đi từ đỉnh A đến đỉnh E.
Câu 40: Trong đồ thị ở Hình 8, hãy tìm:
a) Một đường đi từ đỉnh A đến đỉnh F;
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối.
Lời giải
a) Một đường đi từ đỉnh A đến đỉnh F là ADE (hoặc có thể chọn ABCDF hoặc ABCEF).
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối là ECDFE (hoặc có thể chọn EFDCE).
Câu 41: Quan sát đồ thị Hình 8 và cho biết hai đỉnh bất kì của đồ thị có được nối với nhau bằng một đường đi hay không?
Lời giải
Quan sát đồ thị Hình 8 ta thấy hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi.
Câu 42: Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.
Lời giải
+) Ví dụ về đồ thị liên thông:
Ở hình trên, hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi. Vậy đồ thị đó là đồ thị liên thông.
+) Ví dụ về đồ thị không liên thông:
Ở hình trên, mỗi đỉnh thuộc khối bên trên đều không thể nối được với mỗi đỉnh thuộc khối bên dưới bằng một đường đi. Vậy đồ thị đó là đồ thị không liên thông.
▶BÀI ❷. ĐƯỜNG EULER VÀ ĐƯỜNG ĐI HAMILTON
Ⓐ. Tóm tắt kiến thức
❶. ĐƯỜNG ĐI EULER
a) Khái niệm đường đi Euler
* Cho một đa đồ thị .
* Một đường đi đơn giản từ đỉnh đến đỉnh và chứa mọi cạnh của được gọi là một đường đi Euler từ đến .
* Một chu trình đơn giản chứa mọi cạnh của được gọi là một chu trinh Euler của .
* Định lí 1 (Euler)
* Một đa đồ thị có một chu trình Euler khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chã̃n.
* Định lí 2
* Một đa đồ thị có một đường đi Euler từ đến khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chăn, chỉ trừ và có bậc lẻ.
* Chú ý. Hai định lí trên cũng đúng cho trường hợp là đơn đồ thị.
❷. ĐƯỜNG ĐI HAMILTON
* Một đường đi sơ cấp từ đỉnh đến đỉnh và qua mọi đỉnh của đồ thị được gọi là một đường đi Hamilton từ đến .
* Một chu trình sơ cấp chứa mọi đỉnh của được gọi là một chu trình Hamilton của .
* Định lí 3 (Ore)
* Nếu là đơn đồ thị có đỉnh và mổi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn thì có một chu trình Hamilton.
* Hệ quả (Định lí Dirac). Nếu G là đơn đồ thị có đỉnh và mổi đỉnh có bậc không
* Định lí 4
* Nếu đơn đồ thị có đỉnh và mỗi đỉnh có bậc không nhỏ hơn thì có một đường đi Hamilton.
* Chú ý. Trong một số trường hợp đơn giản, ta có thề tìm đường đi (chu trình Hamilton) của G hoặc chứng minh G không có đường đi (chu trình Hamilton) dựa vào nhận xét sau: Đường đi (chu trình) Hamilton phải đi qua các cạnh có đầu mút tại những đỉnh có bậc 2.
 
 
 
 
 
Ⓑ. Phân dạng toán cơ bản
⬩Dạng ❶: Đường đi Euler
☞Các ví dụ minh họa
Câu 1: Quan sát đồ thị ở Hình 10 và đường đi CABDCB, cho biết:
a) Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không?
b) Đường đi trên đi qua mỗi cạnh bao nhiêu lần? 
Lời giải
Quan sát đồ thị ở Hình 10 ta thấy:
a) Đường đi CABDCB đi qua tất cả các cạnh của đồ thị.
b) Đường đi trên đi qua mỗi cạnh đúng một lần.
Câu 2: Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.
Lời giải
Hình 11a có đường đi Euler BEDBADCA và đường đi Euler BEDCADBA.
Câu 3: Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler.
Lời giải:
Ta có d(A) = 3, d(B) = 3 nên đồ thị ở Hình 11a có đỉnh bậc lẻ, do đó theo định lí Euler, đồ thị ở Hình 11a không có chu trình Euler.
Câu 4: Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần.
Lời giải
Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 ta thấy đường đi đó đi qua tất cả các đỉnh của đồ thị hay và mỗi đỉnh đi qua đúng một lần.
Câu 5: Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.
Lời giải
Ta có thể vẽ mỗi hình trên Hình 2.16 bằng một nét liền.
- Đối với Hình 2.16 a), ta có thể vẽ một nét liền theo thứ tự 123451.
- Đối với Hình 2.16 b), ta có thể vẽ một nét liền theo thứ tự ABCDAEFB.
Câu 6: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.
Lời giải
- Đồ thị Hình 2.19a có đường đi Euler từ A đến B vì đồ thị này liên thông và các đỉnh A, B có bậc 3 (bậc lẻ), còn các đỉnh C, D, E đều có bậc 2 (bậc chẵn). Một đường đi Euler của đồ thị này là ACBDAEB.
- Đồ thị Hình 2.19b không có đường đi Euler vì đồ thị này có bốn đỉnh bậc lẻ (ở đây là bậc bằng 3).
Câu 7: Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Lời giải
Ta có d(A) = d(B) = d(C) = d(D) = 4 và d(E) = d(F) = 3.
Suy ra đồ thị H có đúng 2 đỉnh bậc lẻ là E, F.
Do đó đồ thị H có đường đi Euler.
Chẳng hạn, bắt đầu từ đỉnh E, ta có thể đi theo đường đi Euler: EAabADcdDFCBEF.
Lời giải
a) Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = d(E) = 4.
Vậy đồ thị G có chu trình Euler vì các đỉnh của đồ thị G đều có bậc chẵn.
Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: ABECAEDCBDA.
b) Đồ thị H:
Ta có d(A) = d(D) = 4; d(B) = d(C) = 3; d(E) = 2.
Vậy đồ thị H không có chu trình Euler vì hai đỉnh B, C có bậc lẻ.
Câu 8: Hãy giải đáp câu hỏi của người dân Königsberg (còn gọi là bài toán Bảy cây cầu).
Lời giải
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.
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.
⬩Dạng ❷: Tìm đường đi Hamilton
☞Các ví dụ minh họa
Câu 9: Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15.
Lời giải
Quan sát đồ thị Hình 15, ta thấy rằng hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị này là EACDB và ECDBA.
Câu 10: Hãy chỉ ra rằng mỗi đồ thị sau đây có chu trình Hamilton.
Lời giải
⦁ Hình 21a:
Đồ thị ở Hình 21a có các đỉnh A, F có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, FD, FC trong đồ thị ở Hình 21a.
Do đó h không thể đi qua các cạnh BD, DC.
Nếu xóa đi hai cạnh này thì đỉnh B, C trở thành có bậc 2.
Vì vậy h phải đi qua cạnh BC.
Khi đó ta được chu trình Hamilton h: ADFCBA.
⦁ Hình 21b:
Đồ thị ở Hình 21b có các đỉnh F, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh FE, FB, IA, IC.
Do đó ta được chu trình Hamilton h: AICBFEDA (hoặc AICDEFBA).
Vậy cả hai đồ thị đã cho đều có chu trình Hamilton.
Câu 11: Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?
Lời giải
Đồ thị ở Hình 22 có các đỉnh B, K có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi các các cạnh AB, BC, AK, KI.
Do đó h không thể đi qua các cạnh AI, AD, AD, AE.
Nếu xóa đi bốn cạnh trên thì các đỉnh A, D trở thành bậc 2.
Suy ra h phải đi qua các cạnh AB, AK, DC, DF.
Do đó h không thể đi qua các cạnh CE, CF.
Nếu xóa đi thêm hai cạnh trên thì đỉnh E trở thành bậc 2.
Suy ra h phải đi qua các cạnh EI, EF.
Vì vậy ta được chu trình Hamilton h: ABCDFEIKA.
Vậy có cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch.
⬩Dạng ❸: Chứng minh tính chất đồ thị Hamilton
☞Các ví dụ minh họa
Câu 12: Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton. 
Lời giải
Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn 5252 . Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.
Câu 13: Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.

onthicaptoc.com Cac dang Bai tap Ly thuyet do thi on thi TN THPT