Giáo án điện tử chuyên đề Toán 11 cánh diều Bài 1: Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton

VUI MỪNG CHÀO ĐÓN CÁC EM QUAY TRỞ LẠI VỚI MÔN HỌC!

KHỞI ĐỘNG

Bài toán Bảy cây cầu của Euler (hay Bảy cây cầu ở Königsberg)

Thành phố Königsberg nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và nối với đất liền bởi bảy cây cầu. 

Người dân có thắc mắc: “Có đường đi nào cho phép một người đi qua cả bảy cây cầu, mà mỗi cây cầu chỉ đi qua một lần?”.

Năm 1741, Euler đã trình bày lời giải cho Bài toán Bảy cây cầu ở Königsberg và đưa ra lời giải tổng quát cho dạng bài toán này, bất kể số lượng vùng đất cũng như số lượng cây cầu.

Bằng cách loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm và thay mỗi cây cầu nối hai vùng đất bằng một đoạn nối hai điểm, Euler đã nhận được mô hình sau đây:

CHUYÊN ĐỀ II: LÀM QUEN VỚI MỘT VÀI YẾU TỐ CỦA LÍ THUYẾT ĐỒ THỊ

BÀI 1: MỘT VÀI YẾU TỐ CỦA LÍ THUYẾT ĐỒ THỊ. ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON

NỘI DUNG BÀI HỌC

...........................................

KẾT LUẬN

Đồ thị được gọi là đồ thị đơn nếu 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 được nối với chính nó bởi một cạnh của đồ thị.

Ví dụ 2:

Trong các đồ thị ở Hình 5, đồ thị nào là đồ thị đơn?

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 (Hình 5c).

Luyện tập 2:

Cho hai ví dụ về đồ thị đơn.

Ví dụ

Quy ước: Nếu không nói gì thêm, từ nay về sau các đồ thị đều được giả thiết là đồ thị đơn.

   2. Bậc của đỉnh

HĐ3:

Quan sát đồ thị ở Hình 6 và đếm số cạnh của đồ thị nhận đỉnh làm đầu mút.

Nhận xét:

Có 3 cạnh của đồ thị nhận đỉnh làm đầu mút. Ta nói bậc của đỉnh bằng 3, kí hiệu là .

KẾT LUẬN

Bậc của một đỉnh trong đồ thị là số cạnh của đô thị nhận đỉnh làm đầu mút, kí hiệu là .

Chú ý: Một đỉnh của đồ thị có bậc nếu đỉnh đó là đầu mút của cạnh.

Ví dụ 3:

Trong đồ thị ở Hình 6, hãy tìm những đỉnh có:

a) Bậc lẻ;                                    b) Bậc chẵn.

Giải

Do , , , , nên:

a) là các đỉnh bậc lẻ;

b) là các đỉnh bậc chẵn.

Luyện tập 3:

Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?

Các đỉnh bậc lẻ của đồ thị là: (đều có bậc 3).

HĐ4:

Quan sát đồ thị ở Hình 7 và cho biết:

1. Tổng các bậc của năm đỉnh trong đồ thị đó;
2. Số cạnh của đồ thị đó;
3. 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ị đó.

ĐỊNH LÍ

Trong một đồ thị, 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ị đó.

Ví dụ 4:

Chứng minh rằng trong một đồ thị, số đỉnh có bậc lẻ là một số chẵn.

Giải

Theo định lí trên, 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à số chẵn.

Vậy số đỉnh bậc lẻ là số chẵn.

Luyện tập 4:

Cho ví dụ về một đồ thị có số lẻ đỉnh bậc chẵn. 

Ví dụ

Các đỉnh bậc chẵn là: .

   3. Đường đi trên đồ thị

HĐ5:

Quan sát đồ thị ở Hình 7 và cho biết:

a) Hai đỉnh 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 có đặc điểm gì.

Giải

a) Hai đỉnh có được nối với nhau bằng một cạnh.

b) Dãy các cạnh kế tiếp nhau có đặc điểm: không có cạnh nòa 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, không có đỉnh nào được đi qua hai lần. 

NHẬN XÉT

Hai đỉnh được nối với nhau bằng một cạnh của đồ thị. Ta nói hai đỉnh là kề nhau hay là láng giềng của nhau.

--------------- Còn tiếp ---------------