CHÀO MỪNG

TẤT CẢ CÁC EM

ĐẾN VỚI TIẾT HỌC!

KHỞI ĐỘNG

Trình bày khái niệm: Đường đi Euler và Đường đi Hamilton?

CHUYÊN ĐỀ 2: LÀM QUEN VỚI

MỘT VÀI KHÁI NIỆM CỦA

LÍ THUYẾT ĐỒ THỊ

BÀI TẬP CUỐI CHUYÊN ĐỀ 2

HOẠT ĐỘNG

LUYỆN TẬP

Bài 2.19 (SGK-tr50) Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:

Giải

a) Tập hợp các đỉnh

Tập hợp các cạnh

b) Tập hợp các đỉnh

Bài 2.20 (SGK-tr50) Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau: V= {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}. Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Giải

là một đơn đồ thị nhưng không phải là đò thị đầy đủ (vì, chẳng hạn, không có cạnh nào nói với hai đỉnh 1 và 8).

Bài 2.24 (SGK-tr50) Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.

Giải

Ví dụ về 5 đường đi từ S đến Y: STZY;STZWXY;STZXY;SVTZY;SVUTZY

Bài 2.25 (SGK-tr50) Kiểm tra xem các điều kiện của định lí Ore có thoả mãn với các đồ thị trên Hình 2.39 không.

Giải

a) Đồ thị có 5 đỉnh, trong đó có đỉnh A bậc 4, các đỉnh còn lại đều là bậc 3. Tức là đồ thị thỏa mãn điều kiện của Định lí Ore.

b) Đồ thị có 5 đỉnh, trong đó có hai đỉnh B,E bậc 3, các đỉnh còn lại đều là bậc 2. Tức là đồ thị không thỏa mãn điều kiện của định lí Ore.

Bài 2.26 (SGK-tr51) Tìm một chu trình Euler trong đồ thị trên Hình 2.40.

Giải

Một chu trình Euler cần tìm là .

HOẠT ĐỘNG

VẬN DỤNG

Bài 2.21 (SGK-tr50) 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 6.

Giải

Gọi là số đỉnh bậc 3 của đồ thị

Khi đó số đỉnh bậc 6 của đồ thị là:

Tổng số bậc của các đỉnh là:

Do đồ thị có 28 cạnh nên ta có:

Do đồ thị có 28 cạnh nên ta có: , tức là . 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.

Bài 2.22 (SGK-tr50) Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh có cùng bậc.

Giải

Giả sử là một đơn đồ thị với đỉnh

Vì là một đơn đồ thị nên mỗi đỉnh được nối với tối đa đỉnh khác (do hai đỉnh chỉ được nối với nhau bằng nhiều nhất một cạnh).

Do đó, mỗi đỉnh có số bậc tối đa là

Ta thấy có đỉnh, mà có loại bậc, nên tồn tại ít nhất hai đỉnh có cùng bậc với nhau.

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