onthicaptoc.com Cac dang Bai tap Ly thuyet do thi on thi TN THPT
▶BÀI ❶. MỘT VÀI KHÁI NIỆM CƠ BẢN VỀ LÝ THUYẾT ĐỒ THỊ
-6839064135Ⓐ. 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 V(G) là tập hợp các đỉnh và E(G) là tập hợp các cạnh của đồ thị G, và viết G=(V,E). Cạnh nối hai đỉnh A và B thường được kí hiệu là AB hoặc BA, và khi đó A và B gọi là hai đỉnh kề nhau. Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C 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à A,B,C,D và 5 cạnh là AB,AC,AD,BC và CC.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ó n đỉnh thường được kí hiệu là Kn. ❶. Đồ 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 V(G) là tập hợp các đỉnh và E(G) là tập hợp các cạnh của đồ thị G, và viết G=(V,E). Cạnh nối hai đỉnh A và B thường được kí hiệu là AB hoặc BA, và khi đó A và B gọi là hai đỉnh kề nhau. Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C 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à A,B,C,D và 5 cạnh là AB,AC,AD,BC và CC.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ó n đỉnh thường được kí hiệu là Kn.
❷. Bậc của đồ thịMột đỉnh của đồ thị được gọi là đỉnh bậc n nếu nó là đầu mút của n 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, D là đỉnh bậc 3,F là đỉnh treo, G là đỉnh cô lập.Định lí (gọi là Đinh II bắt tay)Trong mọi đồ thị G, 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 G.Hệ quả. Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.❸. ĐƯỜNG ĐI VÀ CHU TRÌNHa) Khái niệm đường đi và chu trìnhTrong một đồ thị G, 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) AB,BC,CD,…. MN,NP gọi là một đường đi nối A với P, kí hiệu là ABCD…MNP. Điểm A gọi là đầu đường, điểm P 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 n cạnh gọi là một đường đi (chu trình) có độ dài n.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 A và B của một đồ thị gọi là liên thông nếu có một đường đi nối A và B.Một đồ thị G được gọi là liên thông nếu mọi cặp đỉnh của G là liên thông.Một cạnh CD của đồ thị G gọi là một cầu nếu khi bỏ cạnh CD thì hai đỉnh C và D không còn liên thông nữa.Mỗi đồ thị G 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 G. Một đồ thị 2n đỉnh, mỗi đỉnh có bậc ít nhất bằng n, là đồ thị liên thông. ❷. Bậc của đồ thịMột đỉnh của đồ thị được gọi là đỉnh bậc n nếu nó là đầu mút của n 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, D là đỉnh bậc 3,F là đỉnh treo, G là đỉnh cô lập.Định lí (gọi là Đinh II bắt tay)Trong mọi đồ thị G, 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 G.Hệ quả. Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.❸. ĐƯỜNG ĐI VÀ CHU TRÌNHa) Khái niệm đường đi và chu trìnhTrong một đồ thị G, 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) AB,BC,CD,…. MN,NP gọi là một đường đi nối A với P, kí hiệu là ABCD…MNP. Điểm A gọi là đầu đường, điểm P 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 n cạnh gọi là một đường đi (chu trình) có độ dài n.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 A và B của một đồ thị gọi là liên thông nếu có một đường đi nối A và B.Một đồ thị G được gọi là liên thông nếu mọi cặp đỉnh của G là liên thông.Một cạnh CD của đồ thị G gọi là một cầu nếu khi bỏ cạnh CD thì hai đỉnh C và D không còn liên thông nữa.Mỗi đồ thị G 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 G. Một đồ thị 2n đỉnh, mỗi đỉnh có bậc ít nhất bằng n, là đồ thị liên thông.
-79318195085
Ⓑ. 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ẽ).
▶bài ❶. một vài khái niệm cơ bản về lý thuyết đồ thị