bài 10 chuyên đề toán

đồ thị có trọng số là đồ thị thế nào?

• là một đồ thị không liên thông

• là một đồ thị liên thông và mỗi cạnh được gắn với một số dương, gọi là trọng số

• là một đồ thị liên thông và mỗi cạnh được gắn với một số âm, gọi là trọng số

Tìm đường đi ngắn nhất nối từ A đến F

Tất cả các đỉnh của đồ thị đều là bậc......

Khi đó đồ thị có chu trình Euler chính là đường đi yêu cầu

• chẵn

• lẻ

VD2: Tìm một chu trình Euler xuất phát từ điểm A

• ADCBACDEADB

• ABCAECDEADA

• ABCBECDEADA

• không có đáp án đúng

KIỂM TRA BÀI CŨ: tìm chu trình Euler

• ABECDEA

• ABCEDEA

• ABECD

• ABECAE