Tham khảo tài liệu 'giáo trình toán ứng dụng trong tin học part 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Ill - Đổ THỊ EULER VÀ Đổ THỊ HAMILTON Trong mục này chúng ta sẽ nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Dưới đây nếu không có giải thích bổ sung thuật ngữ đổ thị được dùng để chỉ chung đa đổ thị vô hướng và có hướng và thuật ngữ cạnh sẽ dùng để chỉ chung cạnh của đồ thị vô hướng cũng như cung cùa đổ thị có hướng. . Đồ thị Euler ĐỊNH NGHĨA 1 Chu trình đơn trừng G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Đường đi đơn trong G đi qua môi cạnh của nó một lẩn được gọi là đường Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler vá gọi là đồ thị nửa Euler nếu nổ có đường đi Euler. Rõ ràng mọi đồ thị Euler luôn là nửa Euler nhưng điều ngược lại không luôn đúng. Ví dụ 1. Đồ thị Gị trong hình là đồ thị Euler vì nó có chu trình Euler a e c d e b a. Đổ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a c d e b d a b vì thê G3 là đồ thị nửa Euler. Đồ thị G2 không có chu trình cũng như đường Euler. G G2 G3 Hình 4 Ỉ7 Đồ thị Gị Ví dụ 2 Đồ thị H2 trong hình là đồ thị Euler vì nó có chu trình Euler a b c d e a. Đồ thị H3 không có chu trình Euler nhưng nó có đường di Euler c a b c d b vì thế H3 là đồ thị nửa Euler. Đổ thị Hj không có chu trình cũng như đường đi Euler. a b ---- ---- ---- a b Hình . Đồ H3 141 Điều kiện cần và đủ để một đồ thị là đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thỆ Những cái cầu ở thành phố Konigsberg có thể diễn tả bằng đồ thị trong hình . Định lý 1 Euler Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Hình Để chứng minh định lý trước hết ta chứng minh bổ đề Bổ đề Nếu bậc của mồi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình. Chứng minh Nếu G có cạnh lặp thì khẳng định của bổ đề là hiển nhiên. Vì vậy giả sử G là đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây
