ĐỒ THị EULER VÀ ĐỒ THị HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị. | Giáo án môn Lý Thuyết Đô Thị Chương 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát Đa đồ thị vô hướng hoặc có hướng thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị. Đồ thị Euler Đỉnh nghĩa 1 Cho đồ thị G V E Đường đi đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Chu trình đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Ví dụ 1 Xét dồ thị vô hướng cho bởi hình sau Hình Đường đi a b f a e b a d e c b là đường đi Euler Đường đi a f b c e d a e b a là đường Euler và cũng là chu trình Euler. Đường đi a b c e d a e b a f b a không phai là chu trình Euler và cũng không phải là đường Euler Ví dụ 2 Xét đồ thị có hướng cho bởi hình sau Hình Hình 44 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị Đường v4 v3 v2 v4 v1 v5 v2 là đường đi Euler Chu trình v1 v5 v2 v4 v3 v2 v4 v1 không phải là chu trình Euler và cũng không là đường đi Euler. Chú ý Đường đi Euler và chu trình Euler cũng có thể được định nghĩa như sau Đường đi chu trình trong đồ thị G là đường đi chu trình Euler nếu nó đi qua tất cả các cạnh của đồ thị và mỗi cạnh đi qua đúng một lần. Định nghĩa 2 Đồ thị G V E được gọi là đồ thị Euler nếu như nó có chu trình Euler và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Ví dụ 3 Đồ thị cho trong ví dụ 1 là đồ thị Euler còn đồ thị cho trong ví dụ 2 là đồ thị nữa Euler. Định lý 1 định lý Euler Một đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi mỗi đỉnh của nó đều có bậc chẵn. Điều kiện cần và đủ để một đồ thị liên thông có chu trình Euler là tất cả các đỉnh của nó đều có bậc chẵn . Chứng minh Điều kiên cần Một đồ thị liên thông có chu trình Euler thì mỗi bậc của nó đều có bậc chẵn. Thật vậy giả sử chu trình Euler của đồ thị bắt đầu từ đỉnh v1 và tiếp .
