Ví dụ về đồ thị có trọng số: Có 4 trạm xe bus A, B, C, D được nối với nhau theo những con đường AB, BC, CD, DA với độ dài lần lượt là 3 km, 2 km, 5 km, 6 km. Ta có đồ thị mô tả tình huống trên như sau.

Hãy cho ví dụ về đồ thị có trọng số. (ảnh 1)

Câu 4/11

Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất.

Xem đáp án

Lời giải

Để tìm quãng đường đi ngắn nhất trên đồ thị có trọng số, ta áp dụng thuật toán láng giềng gần nhất để tìm tất cả các chu trình xuất phát từ một đỉnh ban đầu, đi qua các đỉnh khác và trở về đỉnh ban đầu sao cho tổng độ dài các cạnh của chu trình đó là ngắn nhất. Sau đó, ta so sánh độ dài của tất cả các chu trình “tốt nhất” vừa tìm được để tìm ra chu trình có tổng độ dài các cạnh là ngắn nhất. Việc giải cụ thể Hoạt động 2 trang 46, ta cùng xem chi tiết ở Luyện tập 2 trang 46.

Câu 5/11

Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.

Xem đáp án

Lời giải

Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2. (ảnh 1)

Dễ thấy đồ thị Hình 24 có chu trình Hamilton.

+) Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát A, ta có:

Từ A, đỉnh gần nhất là B, AB = 3 km;

Từ B, đỉnh chưa đến gần nhất là C, BC = 5 km;

Từ C, đỉnh chưa đến gần nhất là D, CD = 5 km;

Từ D, đỉnh chưa đến gần nhất là E, DE = 9 km;

Từ E, đỉnh chưa đến gần nhất là F, EF = 6 km;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, FA = 4 km.

Tổng quãng đường theo chu trình ABCDEFA là: 3 + 5 + 5 + 9 + 6 + 4 = 32 (km).

Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:

Đỉnh bắt đầu	Chu trình	Tổng chiều dài (km)
A	ABCDEFA	32
B	BAFEDCB	32
C	CBAFEDC	32
C	CDEFABC	32
D	DCBAFED	32
E	EFABCDE	32
F	FABCDEF	32

Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.

Câu 6/11

Hexane C₆H₁₄ có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó.

Xem đáp án

Lời giải

Năm đồng phân của hexane C₆H₁₄ là:

CH₃ – CH₂ – CH₂ – CH₂ – CH₂ – CH₃

Hexane C6H14 có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó. (ảnh 1)

Các đồ thị ở hình dưới đây tương ứng minh họa biểu diễn năm đồng phân của hexane C₆H₁₄. Trong đó các nguyên tử C, CH, CH₂, CH₃ tạo nên các đỉnh của đồ thị, còn các liên kết CH₃ – CH₂, CH₂ – CH₂, CH₂ – CH₃, CH₃ – CH, CH – CH₃, CH – CH₂, CH₂ – C, C – CH₃, CH₂ – CH, CH – CH tạo nên các cạnh của đồ thị.