Title 10. FULL CHU DE 10-LY THUYET DO THI .pdf ✅

• Giáo viên:................. 2 ZALO 0774860155 WORD XINH DUONG HUNG CHUYÊN ĐỀ LÝ THUYẾT ĐỒ THỊ TOÁN ⓫  CHUYÊN ĐỀ: LÝ THUYẾT ĐỒ THỊ ▶BÀI ❶. MỘT VÀI KHÁI NIỆM CƠ BẢN VỀ LÝ THUYẾT ĐỒ THỊ A. 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.

• Giáo viên:................. 4 ZALO 0774860155 WORD XINH DUONG HUNG CHUYÊN ĐỀ LÝ THUYẾT ĐỒ THỊ TOÁN ⓫ B. 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. 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? 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? 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.