Title Chuyên đề 37_ _Lời giải_TLN.docx ✅

CHUYÊN ĐỀ 37_ĐƯỜNG EULER VÀ ĐƯỜNG ĐI HAMILTON. BÀI TOÁN TỐI ƯU VỀ ĐƯỜNG ĐI NGẮN NHẤT A. KIẾN THỨC CƠ BẢN CẦN NẮM 1. ĐƯỜNG ĐI EULER a) Khái niệm đường đi Euler  Cho một đa đồ thị .  Một đường đi đơn giản từ đỉnh đến đỉnh và chứa mọi cạnh của được gọi là một đường đi Euler từ đến .  Một chu trình đơn giản chứa mọi cạnh của được gọi là một chu trinh Euler của .  Định lí 1 (Euler) Một đa đồ thị có một chu trình Euler khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chã̃n.  Định lí 2 Một đa đồ thị có một đường đi Euler từ đến khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chẵn, chỉ trừ và có bậc lẻ.  Chú ý. Hai định lí trên cũng đúng cho trường hợp là đơn đồ thị. 2. ĐƯỜNG ĐI HAMILTON  Một đường đi sơ cấp từ đỉnh đến đỉnh và qua mọi đỉnh của đồ thị được gọi là một đường đi Hamilton từ đến .  Một chu trình sơ cấp chứa mọi đỉnh của được gọi là một chu trình Hamilton của .  Định lí 3 (Ore)